Non-recursive formula for the $n$th term of a linear homogeneous recurrence

[Nono713]

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

---

Hint:

Spoiler

You can use generating functions to solve this problem.

 

[MarkFL]

Spoiler

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

 

[Nono713]

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]

Spoiler

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.

 

[Nono713]

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