A question I have been stuck on for quite a while is the following

Find the general solution to the recurrence relation

$$a_n = ba_{n-1} - b^2a_{n-2}$$

Where $b \gt 0$ is a constant.

I don't understand how the general solution can be found with $b$ and $b^2$ in the relation.

Any help or advice would be greatly appreciated.


Using $a_n = t^n$ I found the quadratic equation $t^2 - bt + b^2$

Which then comes to:

$$\frac{b \pm \sqrt{-4b^2 + b}}{2}$$

Therefore I have complex roots as $-4b^2 + b$ will be a negative number.

How do I continue from this point?


Using $a_n = b^nc_n$ I came to $c_n = c_{n-1} - c_{n-2}$. Substituting $t^n$ for $c_n$ I get the quadratic $t^2 - t + t$. Which solves to:

$$ \frac{1 \pm i\sqrt{3}}{2} $$

$\Rightarrow D = \frac{1}{2}\sqrt{1 + 2\sqrt{3}}$ and $tan\theta = \frac{1}{\sqrt{3}}$

$\Rightarrow a_n = \left(\frac{\sqrt{1 + 2\sqrt{3}}}{2}\right)(Acos(n\theta) + Bsin(n\theta))$

  • $\begingroup$ What if you consider $c_n$ such as $a_n=b^nc_n$ ? $\endgroup$ – Claude Leibovici Aug 27 '14 at 9:24
  • $\begingroup$ Sorry I'm not really sure where to go from your point. I was just wondering would making it a quadratic do much? Something like $t^2 - bt - b^2$ ? i.e. $a_n = t^n$ $\endgroup$ – PurityLake Aug 27 '14 at 9:34
  • 1
    $\begingroup$ No. Using $a_n=b^nc_n$ just removes the $b$ terms and then $c_n = c_{n-1} +nc_{n-2}$ but you still have the problem of the general term (I did not find it). With the $c_n$, it could be more manageable (I hope). $\endgroup$ – Claude Leibovici Aug 27 '14 at 10:03
  • $\begingroup$ Sorry I mistakenly added an $n$ after $b^2$ I apologize $\endgroup$ – PurityLake Aug 27 '14 at 10:15
  • $\begingroup$ This makes the problem much more simple. Do you remember Fibonacci and Lucas numbers ? $\endgroup$ – Claude Leibovici Aug 27 '14 at 10:18

When you have $a_n=ba_{n-1}+b^2a_{n-2}$, you can see $$b^\color{red}{0}\cdot a_\color{blue}{n}=b^\color{red}{1}\cdot a_{\color{blue}{n-1}}-b^\color{red}{2}\cdot a_{\color{blue}{n-2}}$$ where $0+n=1+(n-1)=2+(n-2)$.

In such case, dividing the both sides by $b^n$ gives you $$\frac{a_n}{b^n}=\frac{a_{n-1}}{b^{n-1}}+\frac{a_{n-2}}{b^{n-2}}\iff c_n=c_{n-1}-c_{n-2}$$ where $c_n=a_n/b^n$.

Solving $t^2=t-1$ gives us $t=\frac{1-\sqrt 3i}{2}(=\alpha), \frac{1+\sqrt 3i}{2}(=\beta)$.

Hence, we have $$c_{n+1}-\alpha c_n=\beta (c_n-\alpha c_{n-1})=\cdots =\beta^n(c_1-\alpha c_0),$$ $$c_{n+1}-\beta c_n=\alpha (c_n-\beta c_{n-1})=\cdots =\alpha^n(c_1-\beta c_0).$$ Substracting the latter from the former gives you $$\frac{a_n}{b^n}=c_n=\frac{\beta^n-\alpha^n}{\beta-\alpha}c_1+\frac{\alpha\beta(\alpha^{n-1}-\beta^{n-1})}{\beta-\alpha}c_0.$$


Rewrite the recurrence as $a_{n+2} = b a_{n+1} + b^2 a_n$ and use Generating function. This is slower, but more fundamental: $ G(z) = \sum_{k=0}^{\infty} a_k z^k$. You'll need to do a bit of algebra after this. On the LHS you'll have $G(z)$, on the RHS $\sum_{k=0}^{\infty} \varphi(k) z^k$. Now equate the coefficients at $z^n$ and this will be your result.

  • $\begingroup$ That math is severly beyond me I'm sorry $\endgroup$ – PurityLake Aug 27 '14 at 10:38

The approach suggested by Alex appears the correct way to go.

The other answers assume that $\frac{a_{n+1}}{a_n} = a$

I do not see how such an assumption is made from the given question.

PS: I should have added this as a comment rather than an answer, but I do not have enough credits to post a comment. Apologies.

  • $\begingroup$ That is not true. If you compute $a_{n+1}/a_n$ for my final answer you will see it is not equal to a constant. This is because it's a superposition of two functions (which on their own indeed satisfy the property you mention). $\endgroup$ – SPK.z Aug 29 '14 at 8:24

If I'm correct you made a small error in your quadratic equation. Substituting $a_n=t^n$ gives: $$t^n=bt^{n-1}+b^2t^{n-2}\quad\Longrightarrow\quad t^2-bt-b^2=0.$$ This equation has two roots: $t_1=\varphi b$ and $t_2=\psi b$, where: $$\varphi=\frac{1+\sqrt{5}}{2}, \qquad\psi=\frac{1-\sqrt{5}}{2}.$$ The solution is now given by a combination of these two solutions: $$a_n = \alpha t_1 + \beta t_2 = \alpha(\varphi b)^n + \beta(\psi b)^n = \left(\alpha\varphi^n+\beta\psi^n\right)b^n.$$ Finally, $\alpha$ and $\beta$ depend on the choices for $a_0$ and $a_1$. Choose $\alpha$ and $\beta$ such that the solution gives the correct values for $a_0$ and $a_1$, so: $$\alpha + \beta = a_0, \qquad \left(\alpha\varphi+\beta\psi\right)b=a_1.$$ Solving this set of equation leads to: $$\alpha=\frac{a_1-a_0\psi b}{(\varphi-\psi)b}, \qquad \beta=\frac{a_0\varphi b-a_1}{(\varphi-\psi)b}.$$ The expression for $a_n$ together with the expressions for $\varphi,\psi,\alpha$ and $\beta$ constitute the solution.


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.