1
$\begingroup$

I tasked with solving the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ given the initial conditions $a_0 = 1, a_1 = 4$. I do not know how to begin here. However, I know that $$a_2 = 14,$$ $$a_3 = 46,$$ $$a_4 = 146,$$ $$a_5 = 454.$$ What is the pattern here?

Edit: I have explicit instructions to use generating functions, and then extract the coefficients using the GF.

$\endgroup$
1
  • $\begingroup$ Start by assuming that a solution is of the form $a_n=r^n$ for some $r \in \Bbb{R}$. Then use that to get a quadratic equation in $r$. $\endgroup$ – Anurag A Apr 7 '19 at 20:36
2
$\begingroup$

It seem that $a_{n+1}= 3a_n$ for $n\geq 1$ and thus the sequance is geometric....

Prove by induction: Base $n=1,2$ is obivuosly.

Induction step: $n,n-1\to n+1$:

$$ a_{n+1} = 5a_n-6a_{n-1} = 15a_{n-1}-18a_{n-2} = 3(5a_{n-1}-6a_{n-2})= 3a_n$$

$\endgroup$
5
  • 1
    $\begingroup$ Yey, I go over 50K $\endgroup$ – Aqua Apr 7 '19 at 20:41
  • $\begingroup$ Could you please explain how you wrote $5a_n - 6a_{n-1}=15a_{n-1}-18a_{n-2}$? $\endgroup$ – s0ulr3aper07 Apr 7 '19 at 21:04
  • $\begingroup$ by induction hypothetis $a_n = 3a_{n-1}$ and $a_{n-1}=3a_{n-2}$ $\endgroup$ – Aqua Apr 7 '19 at 21:05
  • $\begingroup$ This is of no help to you? $\endgroup$ – Aqua Apr 7 '19 at 21:39
  • $\begingroup$ @MariaMazur It might be worth checking the OP's edit. It seems he forgot one restriction of the problem: he needs to use generating functions to solve this (probably a textbook exercise). :( $\endgroup$ – Eevee Trainer Apr 7 '19 at 23:41
0
$\begingroup$

If you want generating functions, define $A(z) = \sum_{n \ge 0} a_n z^n$, write:

$\begin{align*} a_{n + 2} &= 5 a_{n + 1} - 6 a_n \\ \sum_{n \ge 0} a_{n + 2} z^n &= 5 \sum_{n \ge 0} a_{n + 1} z^n - 6 \sum_{n \ge 0} a_n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 5 \frac{A(z) - a_0}{z} - 6 A(z) \end{align*}$

Use the values for $a_0, a_1$, solve as partial fractions:

$\begin{align*} A(z) &= \frac{2}{1 - 3 z} - \frac{1}{1 - 2 z} \\ a_n &= [z^n] A(z) \\ &= 2 \cdot 3^n - 2^n \end{align*}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.