Solving recurrence relation, $a_n=6a_{n-1} - 5a_{n-2} + 1$

Question

I'm trying to solve this recurrence relation:

$$ a_n = \begin{cases} 0 & \mbox{for } n = 0 \\ 5 & \mbox{for } n = 1 \\ 6a_{n-1} - 5a_{n-2} + 1 & \mbox{for } n > 1 \end{cases} $$

I calculated generator function as: $$ A = \frac{31x - 24x^2}{1 - 6x + 5x^2} + \frac{x^3}{(1-x)(1-6x+5x^2)} = \frac{31x - 24x^2}{(x-1)(x-5)} + \frac{x^3}{(1-x)(x-1)(x-5)} $$

(I'm not sure if that's right)

and its partial fractions decomposition looks like: $$ A = \left(\frac{-7}{4} \cdot \frac{1}{x-1} - \frac{445}{4} \cdot \frac{1}{x-5}\right) + \left( \frac{39}{16} \cdot \frac{1}{x-5} + \frac{3}{4} \cdot \frac{1}{(x-1)^2} - \frac{375}{16} \cdot \frac{1}{x-5} \right) $$ (again - I'm not sure if it's ok)

I'm stuck here... From solutions I know that I should get: $$ a_n = \frac{-21}{16} - \frac{1}{4}n + \frac{21}{16}5^n $$

but I have no idea how it's solved... I hope somebody can help me (I spend more than 3h trying to solve this myself...)

Brian M. Scott · Accepted Answer · 2013-05-13T19:17:19.783

2

I did not check your work, so I’ll outline what you need to do to finish. You have something of the form

$$A(x)=\frac{a}{1-x}+\frac{b}{5-x}+\frac{c}{(1-x)^2}=\frac{a}{1-x}+\frac{b/5}{1-\frac{x}5}+\frac{c}{(1-x)^2}\;.$$

Expand these three terms into power series:

$$\begin{align*} A(x)&=a\sum_{n\ge 0}x^n+\frac{b}5\sum_{n\ge 0}\left(\frac{x}5\right)^n+c\sum_{n\ge 0}(n+1)x^n\\\\ &=\sum_{n\ge 0}\left(a+\frac{b}{5^{n+1}}+c(n+1)\right)x^n\;. \end{align*}$$

Now you can read off the coefficient of $x^n$.

Added: I’ve now had a chance to check your work, and it appears to be a bit off. I’ll use my preferred approach, which begins by assuming that $a_n=0$ for all $n<0$. Then the recurrence can be written

$$a_n=6a_{n-1}-5a_{n-2}+1-[n=0]+4[n=1]\;,$$

for all $n\ge 0$, where the last two terms contain Iverson brackets and are added to make the recurrence give the correct values to $a_0$ and $a_1$. Now multiply through by $x^n$ and sum over $n\ge 0$:

$$\begin{align*} \sum_{n\ge 0}a_nx^n&=\sum_{n\ge 0}\Big(6a_{n-1}-5a_{n-2}+1-[n=0]+4[n=1]\Big)x^n\\\\ &=6x\sum_{n\ge 0}a_{n-1}x^{n-1}-5x^2\sum_{n\ge 0}a_{n-2}x^{n-2}+\sum_{n\ge 0}x^n-1+4x\;. \end{align*}$$

Since $A(x)=\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}a_{n-1}x^{n-1}=\sum_{n\ge 0}a_{n-2}x^{n-2}$ (remember the blanket assumption that $a_n=0$ for $n<0$), we have

$$A(x)=6xA(x)-5x^2A(x)+\frac1{1-x}-1+4x\;,$$

and hence

$$A(x)=\frac1{(1-x)^2(5-x)}+\frac{4x-1}{(1-x)(5-x)}\;.$$

I’ll leave the partial fraction decomposition to you, at least for now.

edited May 13 '13 at 19:17

answered May 13 '13 at 18:56

Brian M. Scott

616,228

it seems very close, but part $\frac{b}{5^{n+1}}$ doesn't "fit", 5 shouldn't be in the deminator I suppose – justanotherengstud May 13 '13 at 19:02
@justanotherengstud: Part of the problem, at least, is that your generating function is wrong; I’ve now had a chance to check that. – Brian M. Scott May 13 '13 at 19:06
can you help me with finding the correct one? or at leats pointing out where I might be making a mistake? – justanotherengstud May 13 '13 at 19:10
@justanotherengstud: I’m editing my answer now, but it will take a few minutes. – Brian M. Scott May 13 '13 at 19:11
Thanks! You use different "style" than my prof, but thanks to you I learned something new. Have a great day! :) – justanotherengstud May 13 '13 at 19:27
@justanotherengstud: You’re welcome, and the same to you! – Brian M. Scott May 13 '13 at 19:31

score 2 · Answer 2 · answered May 13 '13 at 19:22

$$a_0 =0,a_1=5,a_n=6a_{n-1} - 5a_{n-2} + 1, n > 1$$

$$f(x)=\sum_{n=0}^{\infty}a_nx^n=5x+\sum_{n=2}^{\infty}a_nx^n=$$

$$=5x+\sum_{n=2}^{\infty}(6a_{n-1} - 5a_{n-2} + 1)x^n=$$

$$=5x+6\sum_{n=2}^{\infty}a_{n-1}x^n-5\sum_{n=2}^{\infty}a_{n-2}x^n+\sum_{n=2}^{\infty}x^n=$$

$$=5x+6x\sum_{n=2}^{\infty}a_{n-1}x^{n-1}-5x^2\sum_{n=2}^{\infty}a_{n-2}x^{n-2}+\frac{x^2}{1-x}=$$

$$=5x+6xf(x)-5x^2f(x)+\frac{x^2}{1-x}$$ from above follow that g.f. is

$$f(x)=\frac{5x+\frac{x^2}{1-x}}{5x^2-6x+1}=\frac{5x-4x^2}{(1-x)(5x^2-5x-(x-1))}=$$ $$=\frac{x(5-4x)}{(1-x)(5x(x-1)-(x-1))}=\frac{x(5-4x)}{(1-x)(x-1)(5x-1)}$$

Thank's, your answer was really helpful for me! :) – justanotherengstud May 13 '13 at 19:27 — justanotherengstud, May 13 '13 at 19:27

score 1 · Answer 3 · answered May 13 '13 at 18:56

Let's write your recurrence relation for $n$ and $n+1$:

$a_{n}-6a_{n-1}+5a_{n-2}-1=0$

$a_{n+1}-6a_{n }+5a_{n-1}-1=0$

Now we subtract one from another: $a_{n+1}-7a_{n }+11a_{n-1}-5a_{n-2}=0$ (relation 2)

Then, from Theorem on wiki we build a characteristic polynomial $x^3-7x^2+11x-5 $ with roots $1,1,5$. Hence, by that theorem, the solution of our recurrence relation (2) is $c_1 1^n+ c_2n1^n+c_3 5^n$. All you have to do now is to find those constants $c_i$ from initial conditions and from the fact that it should satisfy your initial recurrence relation.

Thanks! I appreciate different approach, I didn't even think about that way. — justanotherengstud, May 13 '13 at 19:28

score 1 · Answer 4 · answered May 14 '13 at 21:02

Use Wilf's technique from "generatingfunctionology". Define $A(z) = \sum_{n \ge 0} a_n z^n$, and write: $$ a_{n + 2} = 6 a_{n + 1} - 5 a_n + 1 \qquad a_0 = 0, a_1 = 5 $$ Multiply by $z^n$ and add for $n \ge 0$, which gives: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 6 \frac{A(z) - a_0}{z} - 5 A(z) + \frac{1}{1 - z} $$ Solving for $A(z)$ gives: $$ A(z) = \frac{5 z - 4 z^2}{1 - 7 z + 11 z^2 - 5 z^3} = \frac{21}{16} \cdot \frac{1}{1 - 5 z} - \frac{17}{16} \cdot \frac{1}{1 - z} - \frac{1}{4} \cdot \frac{1}{(1 - z)^2} $$ Remember the expansions: $$ (1 - u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} (-u)^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} u^k $$ (the binomial coefficient is just an $m-1$-degree polynomial in $k$) and you are all set: $$ a_n = \frac{21}{16} \cdot 5^n - \frac{17}{16} - \frac{1}{4} \binom{n + 1}{1} = \frac{21 \cdot 5^n - 4 n - 21}{16} $$

Maxima's help with the algebra is gratefully acknowledged.

Solving recurrence relation, $a_n=6a_{n-1} - 5a_{n-2} + 1$

4 Answers4