# Thread: Finding the generating function of a recurrence

1. ## Finding the generating function of a recurrence

a_n = 5a_(n-1) - 6a_(n-2) for n>=2, a_0 = 1 and a_1 = c

I got A(x) = 1 + (c+5)x / 1-5x+6x^2 and this is wrong.

Help?

2. Originally Posted by DaRush19
a_n = 5a_(n-1) - 6a_(n-2) for n>=2, a_0 = 1 and a_1 = c

I got A(x) = 1 + (c+5)x / 1-5x+6x^2 and this is wrong.

Help?
$\displaystyle G(x)=\frac{1+(c-5)x}{1-5x+6x^2}$

3. Hello, DaRush19!

Your function does not proeduce: $\displaystyle a_1 \,=\, c$

$\displaystyle a_n \;=\; 5a_{n-1} - 6a_{n-2}\quad\text{for }n\geq 2,\;\; a_0 \,=\, 1,\;\;a_1 \,=\, c$
I don't know what method you used . . .

We have: .$\displaystyle a(n) \;=\;5\cdot a(n\text{-}1) - 6\cdot a(n\text{-}2)$

Let $\displaystyle X^n \:=\:a(n)$ . . . That is, assume $\displaystyle a(n)$ is an exponential function.

Then we have: .$\displaystyle X^n \;=\;5X^{n-1} - 6X^{n-2} \quad\Rightarrow\quad X^n - 5X^{n-1} + 6X^{n-2} \;=\;0$

Divide by $\displaystyle X^{n-2}\!:\quad X^2 - 5X + 6 \:=\:0 \quad\Rightarrow \quad (X - 2)(X - 3) \:=\:0 \quad\Rightarrow\quad X \:=\:2,3$

Form a linear combination of these roots: .$\displaystyle a(n) \;=\;2^n\!\cdot\!A + 3^n\!\cdot\!B$

From the first two values, we have: . $\displaystyle \begin{array}{ccccc}a(0) &=& A + B &=& 1 \\ a(1) &=& 2A + 3B &=& c \end{array}$

Solve the system of equations: .$\displaystyle \begin{array}{c}A \;=\;3-c \\ B \;=\;c-2 \end{array}$

. . Therefore: .$\displaystyle a(n) \;=\;(3-c)\!\cdot\!2^n + (c-2)\!\cdot\!3^n$

4. Originally Posted by ynj
$\displaystyle G(x)=\frac{1+(c-5)x}{1-5x+6x^2}$
Could you write down your working out for me please? That is indeed the correct answer, thanks!

5. Actually I've got it. It was a ridiculous sign error.
Thank you both for you help, much appreciated!