Recurrence challenge!

Bacterius

Well-known member
MHB Math Helper
[JUSTIFY]Just an easy one to start off with, find a non-recursive formula for the $n$th term of the following linear homogeneous recurrence:

$$a_0 = 2, ~ ~ a_1 = -2, ~ ~ a_n = -2 a_{n - 1} + 2 a_{n - 2} ~ ~ \text{for} ~ n \geq 2$$[/JUSTIFY]
[HR][/HR]
Hint:
You can use generating functions to solve this problem.

MarkFL

Staff member
The characteristic roots are:

$$\displaystyle r=-1\pm\sqrt{3}$$

and so the closed form is:

$$\displaystyle a_n=k_1(-1+\sqrt{3})^n+k_2(-1-\sqrt{3})^n$$

Using the given initial values, we may write:

$$\displaystyle a_0=k_1+k_2=2$$

$$\displaystyle a_1=k_1(-1+\sqrt{3})+k_2(-1-\sqrt{3})=-(k_1+k_2)+\sqrt{3}(k_1-k_2)=-2+\sqrt{3}(k_1-k_2)=-2$$

Thus:

$$\displaystyle k_1=k_2=1$$

and so the closed form is:

$$\displaystyle a_n=(-1+\sqrt{3})^n+(-1-\sqrt{3})^n$$

Bacterius

Well-known member
MHB Math Helper
But how did you work out those characteristic roots? Show your working

(I don't actually know what characteristic roots are - are they that easy to derive? I approached this with generating functions myself)

MarkFL

Staff member
The associated auxiliary equation is:

$$\displaystyle r^2+2r-2=0$$

Use of the quadratic equation gives the characteristic roots.

We essentially assume a solution of the form:

$$\displaystyle a_n=r^n$$ where $$\displaystyle r\ne0$$

and so substitution into the recursion gives:

$$\displaystyle r^n=-2r^{n-1}+2r^{n-2}$$

Dividing through by $$\displaystyle r^{n-2}$$ and rearranging in standard quadratic form gives the characteristic or auxiliary equation above.

Bacterius

Well-known member
MHB Math Helper
[JUSTIFY]Let $a(z) = \sum_{i = 0}^\infty a_i z^i = a_0 + a_1 z + a_2 z^2 + \cdots$ be a generating function such that $a_n$ corresponds to said recurrence. Consider:

$$a(z) + 2 z a(z) - 2 z^2 a(z)$$
The reason we do this is because when we multiply $a(z)$ by $z$, we increment every exponent in the generating function by $1$, and then $a_1$ is paired with $z^2$, $a_2$ is paired with $z^3$, and so on. So we see that the sum above is just the recurrence relation, encoded into a sum of generating functions. Let's write down the first few terms of these three different generating functions:

$$\begin{array}{|c|cccl|} \hline a(z) &a_0 &a_1 z &a_2 z^2 &\cdots \\ 2 z a(z) &~ &2 a_0 z &2 a_1 z^2 &\cdots \\ -2 z^2 a(z) &~ &~ &- 2 a_0 z^2 &\cdots \\ \hline \text{Sum} &a_0 &(a_1 + 2a_0) z &0 &\cdots \\ \hline \end{array}$$
We note the resulting coefficients for $z^2, z^3, \cdots$ are zero, since $a_n = -2 a_{n - 1} + 2 a_{n - 2}$ for $n \geq 2$. It follows that:

$$a(z) + 2 z a(z) - 2 z^2 a(z) = a_0 + (a_1 + 2 a_0) z$$
Rearranging, we obtain:

$$a(z) \left ( 1 + 2 z - 2 z^2 \right ) = a_0 + (a_1 + 2 a_0) z$$
Now we may plug in the initial values $a_0 = 2$, $a_1 = -2$ into the equation:

$$a(z) \left ( 1 + 2 z - 2 z^2 \right ) = 2 + 2 z$$
To finally obtain an expression for $a(z)$, our original generating function:

$$a(z) = \frac{2 + 2z}{1 + 2 z - 2 z^2}$$
By partial fraction decomposition, we can deduce that:

$$a(z) = \frac{\alpha}{\alpha + 2z} + \frac{\beta}{\beta - 2z} = \frac{1}{1 + \frac{2}{\alpha} z} + \frac{1}{1 - \frac{2}{\beta} z}$$
Where $\alpha = \sqrt{3} - 1$ and $\beta = \sqrt{3} + 1$. We can then use the theorem that:

$$\frac{1}{1 - nz} = \sum_{i = 0}^\infty n^i z^i$$
This yields:

$$a(z) = \sum_{i = 0}^\infty \left ( - \frac{2}{\alpha} \right )^i z^i + \sum_{i = 0}^\infty \left ( \frac{2}{\beta} \right )^i z^i = \sum_{i = 0}^\infty \left [ \left ( - \frac{2}{\alpha} \right )^i + \left ( \frac{2}{\beta} \right )^i \right ] z^i$$
And we can then just read off the coefficient of $z^i$ to evaluate the recurrence at $a_i$. We conclude:

$$a_n = \left ( - \frac{2}{\alpha} \right )^n + \left ( \frac{2}{\beta} \right )^n = \left ( - \frac{2}{\sqrt{3} - 1} \right )^n + \left ( \frac{2}{\sqrt{3} + 1} \right )^n$$
Which, after simplifying the fractions, becomes:

$$a_n = \left ( - \sqrt{3} - 1 \right )^n + \left ( \sqrt{3} - 1 \right )^n$$
[/JUSTIFY]