Solving A Linear Recurrence Relation With Complex Roots

Question

Question:

For the given linear homogeneous difference equation, find the general solution:

$$y_{n+2} + y_{n+1} + y_n = 0$$

With the initial conditions of:

$$y(0)=\sqrt3, y(1) = 0$$

Attempted Answer:

I approached the problem normally as one would except by solving the auxiliary equation which yields:

$$m^2 + m + 1 = 0$$ $$\implies m = \frac{-1}{2} \pm \frac{i\sqrt3}{2}$$

Now the general solution is of form:

$$y_n = A \left(\frac{-1}{2} - \frac{i\sqrt3}{2}\right)^n + B \left(\frac{-1}{2} + \frac{i\sqrt3}{2}\right)^n $$

Here is the part where I get stuck when I substitute the initial conditions to form a system of equations:

$$A + B = \sqrt{3}$$ $$A \left(\frac{-1}{2} - \frac{i\sqrt3}{2}\right) + B \left(\frac{-1}{2} + \frac{i\sqrt3}{2}\right) = 0$$

Now to make my life easier (which it really didn't), I decided to take a 'shortcut' and rewrite the 2nd equation as the sum of an imaginary and real part:

$$\frac{-1}{2}(A + B) + i\frac{\sqrt3}{2}(-A + B) = 0 + 0i$$

Since the real part on the LHS must equal the real part on the RHS, and the same applies for the imaginary part, we obtain:

$$\frac{-1}{2}(A + B) = 0$$ $$\frac{\sqrt3}{2}(-A + B) = 0$$

So the above implies that $A = B = -B$ which can only be true if $A = B = 0$. However if that is the case, then the first equation in the system of equations ($A + B = \sqrt{3}$) implies that 0 = $\sqrt{3}$.

I know that there is a mistake somewhere in the logic of my reasoning (I think perhaps when I equated each real and imaginary part of the LHS to the RHS) but I don't know why and where exactly. Please point out my mistake.

Answer 1

What happens when the roots of the characteristic polynomial are complex is that the solutions have a periodic component.

Your case is $y_n = a \left(\frac{-1}{2} - \frac{i\sqrt3}{2}\right)^n + b \left(\frac{-1}{2} + \frac{i\sqrt3}{2}\right)^n =a r^n + bs^n $. Note that $r+s = -1$ and $r-s = -i\sqrt{3}$.

If $y_0 = u$ and $y_1 = v$, then $a+b = u$ and $ar+bs = v$. Since $b = u-a$, $v = ar+(u-a)s =a(r-s)+us $, so $a =\frac{v-us}{r-s} $ and $b =u-a =u-\frac{v-us}{r-s} =\frac{u(r-s)-v+us}{r-s} =\frac{ur-v}{r-s} $.

In your case, $u=\sqrt{3}, v = 0, r=\frac{-1}{2} - \frac{i\sqrt3}{2}, s=\frac{-1}{2} + \frac{i\sqrt3}{2}, r-s=-i\sqrt{3} $, so $a =\frac{v-us}{r-s} =\frac{-\sqrt{3}(\frac{-1}{2} + \frac{i\sqrt3}{2})}{-i\sqrt{3}} =-i(\frac{-1}{2} + \frac{i\sqrt3}{2}) =\frac{i}{2} + \frac{\sqrt3}{2} $ and $b =u-a =\frac{\sqrt3}{2}-\frac{i}{2} $.

(We are getting close.)

We have $y_n =ar^n+bs^n $.

By the magic of assigned problems, $|r| = |s| = 1$. $r = e^{-2i\pi/3} $, so $r^n =e^{-2ni\pi/3} =\cos(-2n\pi/3)+i\sin(-2n\pi/3) =\cos(2n\pi/3)-i\sin(2n\pi/3) $. Similarly, $s = e^{2i\pi/3} $, so $s^n =e^{2in\pi/3} =\cos(2n\pi/3)+i\sin(2n\pi/3) $.

Also $a =e^{i\pi/6} $ and $b =e^{-i\pi/6} $.

Therefore (finally!)

$\begin{align*} y_n &=ar^n+bs^n\\ &=e^{i\pi/6}e^{-2in\pi/3}+e^{-i\pi/6}e^{2in\pi/3}\\ &=e^{\pi i(1/6-2n/3)}+e^{\pi i(-1/6+2n/3)}\\ &=\cos(\pi (1/6-2n/3))+i\sin(\pi (1/6-2n/3)) +\cos(\pi (-1/6+2n/3))+i\sin(\pi (-1/6+2n/3))\\ &=\cos(\pi (1/6-2n/3))+\cos(\pi (-1/6+2n/3)) +i(\sin(\pi (1/6-2n/3))+\sin(\pi (-1/6+2n/3)))\\ &=2\cos(\pi (1/6-2n/3)) \qquad\text{since } \cos(-x)=\cos(x) \text{ and }\sin(x) = -\sin(-x)\\ \end{align*} $

You can get explicit values for values of $n$ mod 6, but this shows how the result is periodic.

A check is that the result is real, with no imaginary part. This has to hold, since the initial values and the recurrence coefficients are all real.

Answer 2

Your $A$ and $B$ have to be complex. Your system is equivalent to $$A+B=\sqrt 3\\-(A+B)/2-(A-B)\frac{i\sqrt 3}{2}=0,$$ which gives you $$A-B = i\\A+B=\sqrt3$$ and now it is to solve.

Answer 3

Use generating functions. Define $A(z) = \sum_{n \ge 0} y_n z^n$, multiṕly your recurrence by $z^n$, sum over $n \ge 0$ and recognize some sums:

$\begin{align} \frac{A(z) - y_0 -y_1 z}{z^2} + \frac{A(z) - y_0}{z} + A(z) &= 0 \\ \frac{A(z) - \sqrt{3}}{z^2} + \frac{A(z) - \sqrt{3}}{z} + A(z) &= 0 \end{align}$

Solving for $A(z)$:

$\begin{align} A(z) &= \frac{(1 + z) \sqrt{3}}{1 + z + z^2} \\ &= \frac{1 - z^2}{1 - z^3} \sqrt{3} \end{align}$

We need:

$\begin{align} [z^n] A(z) &= [z^n] \frac{1 - z^2}{1 - z^3} \sqrt{3} \\ &= \sqrt{3} [z^n] (1 - z^2) \sum_{k \ge 0} z^{3 k} \\ &= \sqrt{3} \left( [z^n] \sum_{k \ge 0} z^{3 k} - [z^{n - 2}] \sum_{k \ge 0} z^{3 k} \right) \\ &= \begin{cases} \sqrt{3} & \text{if \(n \equiv 0 \pmod{3}\)} \\ - \sqrt{3} & \text{if \(n \equiv 1 \pmod{3} \wedge n \ge 2\)} \\ 0 & \text{otherwise} \end{cases} \end{align}$