# recurrence relation, linear, second order, homogeneous, constant coefficients, generating functions

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.

-
What do you know? What did you try? Where did you fail? To tell you the truth, I am a tad surprised that this most canonical example of application should cause any problem at all... – Did Dec 14 '11 at 13:05
Have you been taught recursion? Having a look at the way the Fibonacci Sequence works may possibly give some insight. – VisionIncision Dec 14 '11 at 13:12
Maybe looking at some of the similar questions could help: e.g. math.stackexchange.com/questions/75976 and math.stackexchange.com/questions/74706 (At least if you insist on using generating functions - different approach is in the answer which has been already posted.) – Martin Sleziak Dec 14 '11 at 13:13
If you are familiar with how to solve linear differential equations with constant coefficients then one can solve linear difference equations (recursions) in an exactly analogous way. – Joseph Malkevitch Dec 14 '11 at 14:50

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

-
Thanks Norbert, this was helpful :-) – Nikhil Mulley Dec 14 '11 at 13:24
Was it really helpful? Doing it for him, instead of letting him think about the hints in the comments? – GEdgar Dec 14 '11 at 13:49
Sometimes it is better to see a clear solution to understand the method than beat about the bush. – Norbert Dec 14 '11 at 13:56
There are also others than the OP that can benefit from this. – Eelvex Dec 14 '11 at 16:33
@Norbert, in principle you might be right, but in practice, is this what will happen? Considering that the OP, despite some explicit prodding, did not care to explain what they knew, what they tried nor where they failed... Call me cynical if you wish but I find hard to believe that your general remark applies in the present case. – Did Dec 14 '11 at 20:10

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).$$

-

\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$$

-
thanks for simplifying Sivaram. Likes :-) – Nikhil Mulley Dec 14 '11 at 19:26

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).$

-

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$$

-