How to solve this by using the generating functions? What is the possible solution for this?
recurrence relation $ a_n = 5a_{n-1} – 6a_{n-2}, n \ge 2,\text{ given }a_0 = 1, a_1 = 4.$
Thanks.
How to solve this by using the generating functions? What is the possible solution for this?
recurrence relation $ a_n = 5a_{n-1} – 6a_{n-2}, n \ge 2,\text{ given }a_0 = 1, a_1 = 4.$
Thanks.
Use ordinary generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write $ a_{n + 2} = 5 a_{n + 1} – 6 a_n $ Multiply by $z^n$, add over the valid indices ($n \ge 0$), recognize a few sums: $ \frac{A(z) - a_0 - a_1 z}{z^2} = 5 \frac{A(z) - a_0}{z} - 6 A(z) $ With the initial values you get, as partial fractions: $ A(z) = \frac{2}{1 - 3 z} - \frac{1}{1 - 2 z} $ This is just two geometric series, so: $ a_n = 2 \cdot 3^n - 2^n $
So that you can begin to see connections, we look at the same problem using generating functions. The details look somewhat harder than the characteristic equation method. In fact the procedure is quite mechanical, and is abstractly the same as the characteristic equation method.
Let $f(t)=a_0+a_1t+a_2t^2+a_3t^3+ \cdots + a_nt^n+ \cdots. \qquad\qquad(\ast)$ Note that we are looking at $(\ast)$ as a formal power series, as simply a carrier for the coefficients. (In fact it does converge if $|t|<1/3$.) We have $5tf(t)=5a_0t+5a_1t^2+5a_2t^3+\cdots +5a_{n-1}t^n+\cdots,$ $6t^2f(t)=6a_0t^2+6a_1t^3+6a_2t^4+\cdots+6a_{n-2}t^n+\cdots.$ Let $g(t)=f(t)-5tf(t)+6t^2f(t)$. Note that for $n \ge 2$, the coefficient of $t^n$ is equal to $a_n-5a_{n-1}+6a_{n-2}$, which is $0$. So $g(t)=a_0+a_1t-5a_0t$. Since $a_0=1$ and $a_1=4$, we have $g(t)=1-t$, and therefore $f(t)=\frac{1-t}{1-5t+6t^2}.$ Using the partial fractions procedure, which is not simply an integration trick, we find that $f(t)=\frac{-1}{1-2t} +\frac{2}{1-3t}.$ But the power series expansions of $\frac{1}{1-2t}$ and $\frac{1}{1-3t}$ are easy to write down, since $\frac{1}{1-x}=1+x+x^2+\cdots$. We conclude that the coefficient of $t^n$ in the expansion of $f(t)$ is given by $a_n=-(2^n)+2(3^n).$
This is just a straightforward usage of standard algorithm.
This relation has characteristic equation of the form $s^2=5s-6$. Its solutions are $s=2$, $s=3$. Thus, we obtain general solution $a_n=C_1 2^n+C_2 3^n$. Since $a_0=1$ and $a_1=4$ we have equations $ C_1 2^0+C_2 3^0=1 $ $ C_1 2^1+C_2 3^1=4 $ to determine coefficients $C_1$, $C_2$. Solution of this system is $C_1=-1$, $C_2=2$. Hence $ a_n=-2^n+2\cdot 3^n $
Another examples you can find here
$ \begin{align} a_n & = 5 a_{n-1} - 6 a_{n-2}\\ a_n - 3a_{n-1} & = 2 (a_{n-1} - 3 a_{n-2}) \end{align} $ Letting $T_n = a_n - 3a_{n-1}$ we get that $T_n = 2T_{n-1}$ and $T_1 = a_1 - 3a_0 = 1$. Hence, $T_n = 2T_{n-1} = 2^2 T_{n-2} = \cdots = 2^{n-1} T_1 = 2^{n-1}$ Hence, $ \begin{align} a_n - 3a_{n-1} & = 2^{n-1}\\ a_{n-1} - 3a_{n-2} & = 2^{n-2}\\ a_{n-2} - 3a_{n-3} & = 2^{n-3}\\ \vdots \\ a_2 - 3a_1 & = 2 \end{align} $ Multiply the second equation by $3$, the third equation by $3^2$, and in general the $k^{th}$ equation by $3^{k-1}$ and add them up to get, $ \begin{align} a_n - 3^{n-2} \times 3a_1 & = 2^{n-1} + 3 \times 2^{n-2} + 3^2 \times 2^{n-3} \cdots + 3^{n-2} \times 2\\ & = 2^{n-1} \times \left( 1 + \frac32 + \left(\frac32 \right)^2 + \cdots + \left( \frac32 \right)^{n-2} \right)\\ & = 2^{n-1} \left( \frac{\left(\frac32\right)^{n-1}-1}{\frac32-1} \right)\\ & = 2 \left( 3^{n-1} - 2^{n-1} \right)\\ a_n & = 2 \left( 3^{n-1} - 2^{n-1} \right) + 3^{n-1} a_1\\ & = 6 \times 3^{n-1} - 2^n \end{align} $ Hence, $a_n = 2 \times 3^n - 2^n$
Writing the recurrence in the form:
$a_n = 5a_{n-1} – 6a_{n-2} = a_{n + 2} - 5a_{n + 1} + 6a, n \ge 2$
one can immediately write down a differential equation for the exponential generating function:
$f'' - 5f' + 6f, f(0) = 1, f'(0) = 4.$
This differential equation has as its solution:
$-e^{2 x}+2 e^{3 x}$,
so the terms $a_n$ of the recurrence will be the coefficients of $\frac{1}{n!}$ in the Taylor series expansion of the above solution, i.e. $a_n=-(2^n)+2(3^n).$