Homework | Find the general solution to the recurrence relation

Question

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.

EDIT

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?

EDIT

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))$

Answer 1

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.$$

Answer 2

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.

Answer 3

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.

Answer 4

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.