- Thread starter
- #1

- Jan 26, 2012

- 644

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

- Thread starter Bacterius
- Start date

- Thread starter
- #1

- Jan 26, 2012

- 644

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

- Admin
- #2

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

- Thread starter
- #3

- Jan 26, 2012

- 644

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

- Admin
- #4

\(\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.

- Thread starter
- #5

- Jan 26, 2012

- 644

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