Finding the explicit formula for a recursive sequence, using power series

Question

The Task is to find the explicit expression for the given recursive sequence with the help of power series.

Given: $a_{0}=0,\ a_{1}=1 \quad$ and $\quad a_{n}=5\cdot a_{n-1} -6\cdot a_{n-2}\quad $ for $\quad n \geq 2$

My Idea: despite the fact, i feel completly lost, about this problem, i thought i could be possible, to somehow build the formula for a power series-expression, then building the first derivative in order to find the explicit formula due to integrating.

finding $f(x) = a_{n}$ somehow like that:

$\int\limits_{0}^{x} \left( \sum\limits_{n=0}^{\infty}a_{n}\cdot x^{n} \right)^{\prime}\ =\ f(x)$

But i don't even know, if that is possible and how.. what do you think?

Answer 1

Use Wilf's "generatingfunctionology" techniques. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and write: $$ a_{n + 2} = 5 a_{n + 1} - 6 a_n $$ Multiplying by $z^n$ and add over $n \ge 0$. This gives: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 5 \frac{A(z) - a_0}{z} - 6 A(z) $$ Solve this for $A(z)$: $$ A(z) = \frac{z}{1 - 5 z + 6 z^2} = \frac{1}{1 - 3 z} - \frac{1}{1 - 2 z} $$ This is just two geometric series: $$ a_n = 3^n - 2^n $$

Answer 2

Hint: For linear homogeneous recurrence relations with constant coefficients you can try a solution of the form $a_n=r^n$. If you put it into your recurrence, you get $r^2=5r-6$ This has two roots, $r_1,r_2$ and your general solution is $a_n=br_1^n+cr_2^n$. If you use your initial conditions you can evaluate $b,c$

Answer 3

The characteristic equation is $$r^2-5r+6=0$$ and its roots are $r_1=2$ and $r_2=3$ hence $$a_n=\alpha (2)^n+\beta (3)^n$$ We find $\alpha$ and $\beta$ by $a_0$ and $a_1$.