Linear recurrences
Task number: 3874
Find the formula (the analytical expression) for the \(n\)-th element of the sequence specified by the following recurrences:
Variant
\(a_0=1, a_{n+1}=a_n+1\)
Solution
Although the solution is obvious, we illustrate on this task the general procedure for solving recurrences.
We find the generating function for the sequence \((a_0,a_1,a_2,…)\) and get \(a(x)=xa(x)+\frac{1}{1-x}\).
The term \(xa(x)\) corresponds to the expression \(a_{n}\) on the right-hand side of the description of \(a_{n+1}\). The function \(\frac{1}{1-x} \) corresponds to the sequence of all ones, which corresponds to the addition of 1 on the right-hand side of the formula for \(a_{n+1}\).
The desired function is \(a(x)=\frac{1}{(1-x)^2}\) and it corresponds to the sequence \( (1{,}2,3,…)\).¨
Variant
\(a_0=1, a_{n+1}=2a_n+3\)
Solution
We compile a generating function for the sequence \((a_0,a_1,a_2,…)\) and we get \(a(x)=2xa(x)+\frac{3}{1-x}-2\).
The term \(2xa(x)\) corresponds to the expression of \(2a_{n}\) in the right-hand of the recurrence for \(a_{n+1}\). The function \(\frac{3}{1-x}-2\) corresponds to the sequence \((1{,}3,3{,}3,…)\), the elements of which are gradually added to the right-hand side of the recurrence for \(a_{n+1}\).
The final generating function is \(a(x)=\frac{1}{1-2x}\left(\frac{3}{1-x}-2\right)\).
In order to obtain the analytical expression, it is necessary to iteratively derive \(a(x)\), in other words, construct the corresponding Taylor series. For this, the decomposition of \(a(x)\) into partial fractions is used. In our case, in has the form \(\frac{\alpha}{1-\lambda_1x}+\frac{\beta}{1-\lambda_2x}\).
Note that the left summand of the decomposition is the generating function for \((\alpha,\alpha\lambda_1,\alpha\lambda_1^2,\alpha\lambda_1^3,…)\) and the right summand \((\beta,\beta\lambda_2,\beta\lambda_2^2,…)\) therefore the \(n\)-th element of the sequence can be immediately expressed as \(a_n=\alpha\lambda_1^n+\beta\lambda_2^n\).
By comparing the denominators in \(a(x)\) and in the searched decomposition we get \(\lambda_1=1\) and \(\lambda_2=2\).
The coefficients \(\alpha\) and \(\beta\) are calculated from a linear system of equations whose rows correspond to the equations for \(a_0\) and \(a_1\):
\(a_0=1=\alpha 1^0+\beta2^0=\alpha+\beta\\ a_1=5=\alpha 1^1+\beta2^1=\alpha+2\beta\)
hence \(\alpha=-3\) a \(\beta=4\).Answer
The sequence can be obtained by the formula \(a_n=2^{n+2}-3\).
Variant
\(a_0=a_1=1, a_{n+2}=a_{n+1}+6a_n\)
Hint
Comments to simplify the procedure in the general case:
Non-homogeneous recurrences of type \(a_n=q_1a_{n-1}+q_2a_{n-2}+…+q_ka_{n-k}+b\) yield in the generating function always the term \(\frac{b}{1-x}\). The presence of this term causes that some power of the root of the polynomial \(1-x\) always appears in the analytical expression (possibly with the appropriate multiplicity as in the previous variant). This root is denoted by \(\lambda_0=1 \) in the following tasks.
The other \(\lambda_1,…,\lambda_k\) are calculated from the homogeneous recurrence \(a_n=q_1a_{n-1}+q_2a_{n-2}+…+q_ka_{n-k}\) as roots of the so-called characteristic polynomial \(y^k-q_1y^{k-1}-q_2y^{k-2}-…-q_k\).
The explanation for this phenomena follows. If we look for a decomposition,
\(1-q_1x-q_2x^2-…-q_kx^k=(1-\lambda_1x)(1-\lambda_2x)…(1-\lambda_kx)\)
we can multiply the whole equation by \(y^k\) for \(y=\frac1x\) and get:
\(y^k-q_1y^{k-1}-q_2y^{k-2}-…-q_ky^0=(y-\lambda_1)(y-\lambda_2)…(y-\lambda_k)\).
Thus \(\lambda_i\) is a suitable coefficient in decomposition if and only if it is the root of the characteristic polynomial.
If \(\lambda_i \) is a root of multiplicity \(k\), then the decomposition into partial fractions contains factors with \((1-\lambda_i)^l\), for \(l=1,…,k\) in the denominators. Then, the analytical expression contains terms \(n^{l-1}\lambda_i^n\).
Solution
The charakteristic polynomial \(\lambda^2-\lambda-6 = (\lambda+2) (\lambda-3)\) has roots
\(\lambda_1=-2, \lambda_2=3\), tedy \(a_n=\alpha (-2)^n + \beta 3^n\).
We substitute for \(n=0{,}1\):
\( 1 = \alpha+\beta \\ 1 = -2\alpha+3\beta \)
and get \(\alpha=\frac{2}{5}, \beta=\frac{3}{5}\).
Answer
The sequence can be obtained by the formula \(a_n=\frac{2}{5} (-2)^n + \frac{3}{5}\; 3^n\).
Variant
\(a_0=a_1=1, a_{n+2}=a_{n+1}+6a_n-4\)
Solution
Due to the inhomogeneity of the difference equation, we add to the roots of the previous solution also the “root” \(\lambda_0=1\). We obtain \(a_n=\alpha (-2)^n + \beta 3^n+\gamma\).
From the rekurence de calculate \(a_2= 3\). Now for \(n=0{,}1,2\) we get the system:
\( 1= \alpha+\beta+\gamma \\ 1 = -2\alpha+3\beta+\gamma \\ 3 = 4\alpha+9\beta+\gamma \)
This system has solution \(\alpha=\frac{2}{15}, \beta=\frac{1}{5}, \gamma=\frac{2}{3}\).
Answer
The sequence can be obtained by the formula \(a_n=\frac{2}{15} (-2)^n + \frac{1}{5}\; 3^n+\frac{2}{3}\).
Variant
\(a_0=0, a_1=1, a_{n+2}=4(a_{n+1}-a_n)\)
Solution
Now the charakteristic polynomial \(\lambda^2-4\lambda+4=(\lambda-2)^2\) yields a root of multiplicity two \(\lambda_{1{,}2}=2\). In the decomposition into partial fractions, it is therefore necessary to add a fraction with a denominator in the second power. Thus, in the sequence a term of the form \(n\lambda^n\).
Thus \(a_n=\alpha 2^n+\beta n 2^n\). For \(n=0{,}1\) we obtain the system
\( 0=\alpha \\ 1=2\alpha+2\beta \)
with solution \(\alpha=0, \beta=\frac{1}{2}\).
Answer
The sequence can be obtained by the formula \(a_n=n\ 2^{n-1}\).
Variant
\(a_0=0, a_1=1, a_{n+2}=4(a_{n+1}-a_n)+1\)
Solution
Again, it suffices to add the root \(\lambda_0=1\), determine \(a_2=5\) and solve the system:
\( 0=\alpha+\gamma \\ 1=2\alpha+2\beta+\gamma \\ 5=4\alpha+8\beta+\gamma \)
It has solution \(\alpha=1, \beta=-1, \gamma=1\).
Answer
The sequence can be obtained by the formula \(a_n=1+(n-1)2^n\).
Variant
\(a_0=2, a_1=3, a_{n+2}=3a_n-2a_{n+1}\)
Answer
The sequence can be obtained by the formula \(a_n=\frac{9-(-3)^n}{4}\).
Variant
\(a_0=0, a_1=1, a_{n+2}=a_{n+1}+2a_n+2\)
Answer
The sequence can be obtained by the formula \(a_n=2^n-1\).
Variant
\(a_0=a_1=1, 5a_{n+2}=4a_{n+1}-a_n\)
Variant
\(a_0 = 4, a_1 = 3, a_n = a_{n-1} + 2 a_{n-2} + 3{\cdot} 2^n\) for \(n \geq 2\)
Hint
This is a more difficult option. Try to solve the recurrence by use of generating functions.
Answer
The sequence can be obtained by the formula \((2n + 1)2^n + 3\cdot(-1)^n\).
