Algebra theory - Recurrence relations
What are Recurrence relations?
When we express next term of a sequence in terms of one or more previous terms.
For e.g. the Fibonacci series: \(a_n = a_{n-1} + a_{n-2}\)
A recurrence relation is also called implicit definition of the sequence.
If we can somehow express the general term\(a_n\) free of previous terms, that makes it explicit.
For e.g. for an A.P. we can express \(n^{th}\) term as:
\(a_n = a_{n-1} + d\) which is implicit
or as:
\(a_n = a_1 + (n - 1)d\) which is explicit.
Classifications of Recurrence relations
1. Homogeneous vs non-homogeneous:
Homogeneous means the recurrence relation doesn't have an independent term.
For e.g.
\(a_n = 2a_{n-1} + 3a_{n-2}\) is Homogeneous.
But \(a_n = 2a_{n-1} + 3a_{n-2} + 7n\) is not because it has \(7n\) which is independent of the recurrent terms.
2. Linear vs. non-linear:
If none of the recurrence terms is multiplied by any other recurrence term including itself then it's Linear else it's not.
For e.g.
\(a_n = 2a_{n-1} + 3a_{n-2}\) is Linear.
But \(a_n = 2a_{n-1}.3a_{n-3} + 3a_{n-2}\) is not.
Also \(a_n^{2} = 2a_{n-1}^{2} + 1 \) is not linear but it can be made linear if we define \(b_n = a_n^2\) and rewrite it as \(b_n = 2b_{n-1} + 1\).
3. Degree(Order) of recurrence relations:
Degree = Order = Difference in index of max and min term.
For e.g. \(a_n = 2a_{n-1} + 3a_{n-2}\) has Degree = Order = 2.
For e.g. \(a_n = 2a_{n-1} + 3\) has Degree = Order = 1. And hence it is First Order or First Degree.
4. Constant vs Variable Coefficients:
For e.g. \(a_n = 2a_{n-1} + 3a_{n-2}\) has constant coefficients
But \(a_n = n\cdot a_{n-1} + 3a_{n-2}\) has variable coefficients
Solving First Order Linear Recurrence Relation in General Form:
Here is the general form:
$$ \begin{align*} a_n &= f(n)\cdot a_{n-1} + g(n) \\ \end{align*} $$
Now
$$ \begin{align*} P_n &= f(1)\cdot f(2)\ldots f(n)\\ \end{align*} $$ Note that here we are starting from f(1) but you can start from any index 'k'. But all the terms from f(k) to f(n) should be non-zero and well-defined. Now divide the original equation by \(P(n)\) on both sides.
\[ \frac{a_n}{P(n)} = \frac{a_{n-1}}{P(n-1)} + \frac{g(n)}{P(n)} \]
Note how we got P(n-1) on R.H.S.
f(n) gets cancelled from P(n) leaving behind P(n-1).
Leading to a telescoping sum when you define \( V_n = \frac{a_n}{P(n)} \).
Now we can write:
$$ \begin{align*} V_2 - V_1 &= \frac{g(2)}{P(2)} \\ V_3 - V_2 &= \frac{g(3)}{P(3)} \\ \vdots \\ V_n - V_{n-1} &= \frac{g(n)}{P(n)} \end{align*} $$ Adding all: $$ \begin{align*} V_n - V_1 &= \frac{g(2)}{P(2)} + \ldots \frac{g(n)}{P(n)} \\ \end{align*} $$ Once we simplify this we will get: \(a_n\).
Example 1: Given the recurrence: \[ a_n = 2a_{n-1} + n, \quad \text{for } n \geq 2, \quad a_1 = 1 \] This is a first-order linear non-homogeneous recurrence of the form: \[ a_n = f(n)\cdot a_{n-1} + g(n) \] with \( f(n) = 2 \), \( g(n) = n \).
Step 1: Define Integrating Factor
Let the integrating factor be: \[ P(n) = \prod_{k=2}^{n} f(k) = \prod_{k=2}^{n} 2 = 2^{n-1} \] Now divide both sides of the recurrence by \( P(n) \): \[ \frac{a_n}{2^{n-1}} = \frac{a_{n-1}}{2^{n-2}} + \frac{n}{2^{n-1}} \] Let: \[ V_n = \frac{a_n}{2^{n-1}} \Rightarrow V_n = V_{n-1} + \frac{n}{2^{n-1}} \] Step 2: Telescoping Sum
This recurrence for \( V_n \) telescopes: \[ V_n = V_1 + \sum_{k=2}^{n} \frac{k}{2^{k-1}} \] We compute \( V_1 \) using the initial value \( a_1 = 1 \): \[ V_1 = \frac{a_1}{2^{1-1}} = \frac{1}{1} = 1 \] So: \[ V_n = 1 + \sum_{k=2}^{n} \frac{k}{2^{k-1}} \] Step 3: Simplify the Sum
Define the sum: \[ S_n = \sum_{k=2}^{n} \frac{k}{2^{k-1}} = 2 \sum_{k=2}^{n} \frac{k}{2^k} = 2 \left( \sum_{k=1}^{n} \frac{k}{2^k} - \frac{1}{2} \right) \] Use the known formula(Or see the examples here): \[ \sum_{k=1}^{n} \frac{k}{2^k} = 2 - \frac{n+2}{2^n} \] So: \[ S_n = 2 \left( 2 - \frac{n+2}{2^n} - \frac{1}{2} \right) = 2 \left( \frac{3}{2} - \frac{n+2}{2^n} \right) = 3 - \frac{2(n+2)}{2^n} \] {Step 4: Final Formula} \[ a_n = 2^{n-1} \cdot V_n = 2^{n-1} \left(1 + S_n \right) = 2^{n-1} \left( 1 + 3 - \frac{2(n+2)}{2^n} \right) = 2^{n-1} \left( 4 - \frac{2(n+2)}{2^n} \right) \] Simplify: \[ a_n = 2^{n+1} - (n + 2) \] {Final Answer} \[ \boxed{a_n = 2^{n+1} - (n + 2)} \]
Example 2:
Similarly, following the same method for
\(a_n = (n-1)a_{n-1} + 1\)
You will get:
\[ a_n = (n-1)! + \frac{(n-1)!}{1!} + \frac{(n-1)!}{2!} + \cdots + \frac{(n-1)!}{(n-1)!} \]
So far we have seen how to solve for a general first order linear recurrence relation.
But for specific cases there are faster/simpler methods.
Case 1:
First-order, linear, homogeneous:
\(a_n = f(n)a_{n-1}\) Here you can simply do: $$ \begin{align*} \frac{a_2}{a_1} &= f(2) \\ \frac{a_3}{a_2} &= f(3) \\ \vdots \\ \frac{a_n}{a_{n-1}} &= f(n) \end{align*} $$ Multiply all to get:
$$ \begin{align*} a_n &= a_1 f(2)f(3)\ldots f(n) \end{align*} $$
Example 1:
\(a_n = n\cdot a_{n-1}\) , \(a_1 = 1\)
Here simplifying using above method you will get:
\(a_n = n!\)
Example 2:
\(log(a_n) - log(a_{n-1}) = log(n-1) - log(n+1)\) , \(a_1 = 1\)
Here once you get rid of log and follow the method above, you will get:
\(a_n = \frac{2}{n\cdot (n+1)}\)
Case 2:
First-order, linear, non-homogeneous with constant coefficients and constant independent term:
For e.g.
\(a_n = C_1\cdot a_{n-1} + C_{2}\)
is a linear, non-homogeneous, first-order with constant coefficients and constant independent term.
Here we first convert into a homogeneous relation and use the approach we used in case 1 earlier.
$$ \begin{align*} a_n &= b_n + k \\ b_n + k &= C_1\cdot (b_{n-1} + k) + C_2 \\ b_n &= -k + C_1\cdot k + C_2 + C_1\cdot b_{n-1} \\ k &= \frac{C_2}{1 - C_1} \end{align*} $$ Defining 'k' likes this gives us:
\(b_n = C_1\cdot b_{n-1}\) and now we can use Case 1 approach.
Example 1:
\(a_n = 3a_{n-1} + 2\), \(a_1 = 4\)
Gives: \(a_n = 5\cdot 3^{n-1} - 1\)
Example 2:
\(a_n = 2a_{n-1} + 1\), \(a_1 = 2\)
Gives: \(a_n = 3\cdot 2^{n-1} - 1\)
Example 3:
\(a_n^2 = \frac{1-a_{n-1}^2}{4} + 4\), \(a_1 = 1\)
Here we first make it linear by doing this:
\(b_n + k = a_n^2\)
And then solving this gives:
\(a_n = \sqrt{\frac{16}{5} - \frac{11}{5} \left( -\frac{1}{4} \right)^{n-1}}\)
When we express next term of a sequence in terms of one or more previous terms.
For e.g. the Fibonacci series: \(a_n = a_{n-1} + a_{n-2}\)
A recurrence relation is also called implicit definition of the sequence.
If we can somehow express the general term\(a_n\) free of previous terms, that makes it explicit.
For e.g. for an A.P. we can express \(n^{th}\) term as:
\(a_n = a_{n-1} + d\) which is implicit
or as:
\(a_n = a_1 + (n - 1)d\) which is explicit.
Classifications of Recurrence relations
1. Homogeneous vs non-homogeneous:
Homogeneous means the recurrence relation doesn't have an independent term.
For e.g.
\(a_n = 2a_{n-1} + 3a_{n-2}\) is Homogeneous.
But \(a_n = 2a_{n-1} + 3a_{n-2} + 7n\) is not because it has \(7n\) which is independent of the recurrent terms.
2. Linear vs. non-linear:
If none of the recurrence terms is multiplied by any other recurrence term including itself then it's Linear else it's not.
For e.g.
\(a_n = 2a_{n-1} + 3a_{n-2}\) is Linear.
But \(a_n = 2a_{n-1}.3a_{n-3} + 3a_{n-2}\) is not.
Also \(a_n^{2} = 2a_{n-1}^{2} + 1 \) is not linear but it can be made linear if we define \(b_n = a_n^2\) and rewrite it as \(b_n = 2b_{n-1} + 1\).
3. Degree(Order) of recurrence relations:
Degree = Order = Difference in index of max and min term.
For e.g. \(a_n = 2a_{n-1} + 3a_{n-2}\) has Degree = Order = 2.
For e.g. \(a_n = 2a_{n-1} + 3\) has Degree = Order = 1. And hence it is First Order or First Degree.
4. Constant vs Variable Coefficients:
For e.g. \(a_n = 2a_{n-1} + 3a_{n-2}\) has constant coefficients
But \(a_n = n\cdot a_{n-1} + 3a_{n-2}\) has variable coefficients
Solving First Order Linear Recurrence Relation in General Form:
Here is the general form:
$$ \begin{align*} a_n &= f(n)\cdot a_{n-1} + g(n) \\ \end{align*} $$
Now
$$ \begin{align*} P_n &= f(1)\cdot f(2)\ldots f(n)\\ \end{align*} $$ Note that here we are starting from f(1) but you can start from any index 'k'. But all the terms from f(k) to f(n) should be non-zero and well-defined. Now divide the original equation by \(P(n)\) on both sides.
\[ \frac{a_n}{P(n)} = \frac{a_{n-1}}{P(n-1)} + \frac{g(n)}{P(n)} \]
Note how we got P(n-1) on R.H.S.
f(n) gets cancelled from P(n) leaving behind P(n-1).
Leading to a telescoping sum when you define \( V_n = \frac{a_n}{P(n)} \).
Now we can write:
$$ \begin{align*} V_2 - V_1 &= \frac{g(2)}{P(2)} \\ V_3 - V_2 &= \frac{g(3)}{P(3)} \\ \vdots \\ V_n - V_{n-1} &= \frac{g(n)}{P(n)} \end{align*} $$ Adding all: $$ \begin{align*} V_n - V_1 &= \frac{g(2)}{P(2)} + \ldots \frac{g(n)}{P(n)} \\ \end{align*} $$ Once we simplify this we will get: \(a_n\).
Example 1: Given the recurrence: \[ a_n = 2a_{n-1} + n, \quad \text{for } n \geq 2, \quad a_1 = 1 \] This is a first-order linear non-homogeneous recurrence of the form: \[ a_n = f(n)\cdot a_{n-1} + g(n) \] with \( f(n) = 2 \), \( g(n) = n \).
Step 1: Define Integrating Factor
Let the integrating factor be: \[ P(n) = \prod_{k=2}^{n} f(k) = \prod_{k=2}^{n} 2 = 2^{n-1} \] Now divide both sides of the recurrence by \( P(n) \): \[ \frac{a_n}{2^{n-1}} = \frac{a_{n-1}}{2^{n-2}} + \frac{n}{2^{n-1}} \] Let: \[ V_n = \frac{a_n}{2^{n-1}} \Rightarrow V_n = V_{n-1} + \frac{n}{2^{n-1}} \] Step 2: Telescoping Sum
This recurrence for \( V_n \) telescopes: \[ V_n = V_1 + \sum_{k=2}^{n} \frac{k}{2^{k-1}} \] We compute \( V_1 \) using the initial value \( a_1 = 1 \): \[ V_1 = \frac{a_1}{2^{1-1}} = \frac{1}{1} = 1 \] So: \[ V_n = 1 + \sum_{k=2}^{n} \frac{k}{2^{k-1}} \] Step 3: Simplify the Sum
Define the sum: \[ S_n = \sum_{k=2}^{n} \frac{k}{2^{k-1}} = 2 \sum_{k=2}^{n} \frac{k}{2^k} = 2 \left( \sum_{k=1}^{n} \frac{k}{2^k} - \frac{1}{2} \right) \] Use the known formula(Or see the examples here): \[ \sum_{k=1}^{n} \frac{k}{2^k} = 2 - \frac{n+2}{2^n} \] So: \[ S_n = 2 \left( 2 - \frac{n+2}{2^n} - \frac{1}{2} \right) = 2 \left( \frac{3}{2} - \frac{n+2}{2^n} \right) = 3 - \frac{2(n+2)}{2^n} \] {Step 4: Final Formula} \[ a_n = 2^{n-1} \cdot V_n = 2^{n-1} \left(1 + S_n \right) = 2^{n-1} \left( 1 + 3 - \frac{2(n+2)}{2^n} \right) = 2^{n-1} \left( 4 - \frac{2(n+2)}{2^n} \right) \] Simplify: \[ a_n = 2^{n+1} - (n + 2) \] {Final Answer} \[ \boxed{a_n = 2^{n+1} - (n + 2)} \]
Example 2:
Similarly, following the same method for
\(a_n = (n-1)a_{n-1} + 1\)
You will get:
\[ a_n = (n-1)! + \frac{(n-1)!}{1!} + \frac{(n-1)!}{2!} + \cdots + \frac{(n-1)!}{(n-1)!} \]
So far we have seen how to solve for a general first order linear recurrence relation.
But for specific cases there are faster/simpler methods.
Case 1:
First-order, linear, homogeneous:
\(a_n = f(n)a_{n-1}\) Here you can simply do: $$ \begin{align*} \frac{a_2}{a_1} &= f(2) \\ \frac{a_3}{a_2} &= f(3) \\ \vdots \\ \frac{a_n}{a_{n-1}} &= f(n) \end{align*} $$ Multiply all to get:
$$ \begin{align*} a_n &= a_1 f(2)f(3)\ldots f(n) \end{align*} $$
Example 1:
\(a_n = n\cdot a_{n-1}\) , \(a_1 = 1\)
Here simplifying using above method you will get:
\(a_n = n!\)
Example 2:
\(log(a_n) - log(a_{n-1}) = log(n-1) - log(n+1)\) , \(a_1 = 1\)
Here once you get rid of log and follow the method above, you will get:
\(a_n = \frac{2}{n\cdot (n+1)}\)
Case 2:
First-order, linear, non-homogeneous with constant coefficients and constant independent term:
For e.g.
\(a_n = C_1\cdot a_{n-1} + C_{2}\)
is a linear, non-homogeneous, first-order with constant coefficients and constant independent term.
Here we first convert into a homogeneous relation and use the approach we used in case 1 earlier.
$$ \begin{align*} a_n &= b_n + k \\ b_n + k &= C_1\cdot (b_{n-1} + k) + C_2 \\ b_n &= -k + C_1\cdot k + C_2 + C_1\cdot b_{n-1} \\ k &= \frac{C_2}{1 - C_1} \end{align*} $$ Defining 'k' likes this gives us:
\(b_n = C_1\cdot b_{n-1}\) and now we can use Case 1 approach.
Example 1:
\(a_n = 3a_{n-1} + 2\), \(a_1 = 4\)
Gives: \(a_n = 5\cdot 3^{n-1} - 1\)
Example 2:
\(a_n = 2a_{n-1} + 1\), \(a_1 = 2\)
Gives: \(a_n = 3\cdot 2^{n-1} - 1\)
Example 3:
\(a_n^2 = \frac{1-a_{n-1}^2}{4} + 4\), \(a_1 = 1\)
Here we first make it linear by doing this:
\(b_n + k = a_n^2\)
And then solving this gives:
\(a_n = \sqrt{\frac{16}{5} - \frac{11}{5} \left( -\frac{1}{4} \right)^{n-1}}\)
Comments
Post a Comment