3
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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... $\endgroup$
    – Did
    Dec 14, 2011 at 13:05
  • $\begingroup$ Have you been taught recursion? Having a look at the way the Fibonacci Sequence works may possibly give some insight. $\endgroup$
    – Jack H
    Dec 14, 2011 at 13:12
  • 1
    $\begingroup$ 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.) $\endgroup$ Dec 14, 2011 at 13:13
  • $\begingroup$ 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. $\endgroup$ Dec 14, 2011 at 14:50

5 Answers 5

10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Thanks Norbert, this was helpful :-) $\endgroup$ Dec 14, 2011 at 13:24
  • 5
    $\begingroup$ Was it really helpful? Doing it for him, instead of letting him think about the hints in the comments? $\endgroup$
    – GEdgar
    Dec 14, 2011 at 13:49
  • 2
    $\begingroup$ Sometimes it is better to see a clear solution to understand the method than beat about the bush. $\endgroup$
    – Norbert
    Dec 14, 2011 at 13:56
  • 1
    $\begingroup$ There are also others than the OP that can benefit from this. $\endgroup$
    – Eelvex
    Dec 14, 2011 at 16:33
  • 2
    $\begingroup$ @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. $\endgroup$
    – Did
    Dec 14, 2011 at 20:10
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thanks for simplifying Sivaram. Likes :-) $\endgroup$ Dec 14, 2011 at 19:26
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .