# Solving a second-order recurrence relation with complex characteristic roots in polar form.

I am self-studying this topic from a textbook and am stuck with trying work through one example.

Suppose we are solving the recurrence equation, $$u_n = 2u_{n-1} - 2u_{n-2}$$.

This has the characteristic equation $$r^2 - 2r + 2 = 0$$, which has two characteristic complex roots $$1\pm i$$. (assume this is correct)

The complex roots can be written in three forms (modulus = $$\sqrt{2}$$, arguments = $$\pm\frac{\pi}{4}$$).

\begin{align*} \text{Rectangular: }&1 \pm i \\ \text{Polar: }&\sqrt{2}\left(\cos\frac{\pi}{4} \pm i\sin\frac{\pi}{4}\right) \\ \text{Exponential: }&\sqrt{2}e^{\pm\frac{\pi i}{4}} \end{align*}

The general solution to this recurrence relation with two roots is: $$u_n = A(\text{root}_1)^n + B(\text{root}_2)^n$$, where $$A$$ and $$B$$ are arbitrary constants (assume this is correct).

I imagine the complex roots can be used in any of their three forms in the general solution, but am having particular trouble with the polar form.

\begin{align*} u_n &= A\left(\sqrt{2}\left(\cos \frac{\pi}{4} + i\sin \frac{\pi}{4}\right)\right)^n + B\left(\sqrt{2}\left(\cos \frac{\pi}{4} - i\sin \frac{\pi}{4}\right)\right)^n && \\ &= A (\sqrt{2})^n\left( \cos\frac{n\pi}{4} + i\sin\frac{n\pi}{4} \right) + B (\sqrt{2})^n\left( \cos\frac{n\pi}{4} - i\sin\frac{n\pi}{4} \right) && \text{Using De Moivre's theorem} \\ &= (\sqrt{2})^n\left( (A+B)\cos\frac{n\pi}{4} + (A-B)i\sin\frac{n\pi}{4} \right) && \text{Switching A\pm B for other arbitrary constants} \\ &= (\sqrt{2})^n\left( C\cos\frac{n\pi}{4} + D\begingroup\color{red}i\endgroup\sin\frac{n\pi}{4} \right) \end{align*}

I am not sure where I went wrong, but this result does not agree with the result in the textbook I am studying from, in that the imaginary number (colored in red) is absent from the textbook result. I might have thought that is a texbook error, but it explicitly draws attention to the fact that using the general solution in polar form includes only real numbers!

The textbook example does not show the derivation in steps and seems to assume this is straightforward. Also it does not explicitly show that complex roots in exponential form can be used (can they?).

• @sikfeng yes, corrected. Jun 15, 2020 at 14:00

The sequence you have found is a generalization of the Fibonacci sequence. Referring to a previous answer I have posted here, the general solution can be expressed as

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{af_0}{2} \frac{\alpha^n+\beta^n}{\alpha+\beta}$$

where $$\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$$ and $$f_{0,1}$$ are the initial conditions. Here, I find that $$\alpha,\beta=1\pm i$$. Notice that when $$\alpha,\beta$$ are complex conjugates

\begin{align} & \frac{{{\alpha }^{n}}-{{\beta }^{n}}}{\alpha -\beta }=\frac{{{r}^{n}}\left( {{e}^{in\theta }}-{{e}^{in\theta }} \right)}{r\left( {{e}^{i\theta }}-{{e}^{i\theta }} \right)}=\frac{{{r}^{n}}\sin n\theta }{r\sin \theta } \\ & \frac{{{\alpha }^{n}}+{{\beta }^{n}}}{\alpha +\beta }=\frac{{{r}^{n}}\left( {{e}^{in\theta }}+{{e}^{in\theta }} \right)}{r\left( {{e}^{i\theta }}+{{e}^{i\theta }} \right)}=\frac{{{r}^{n}}\cos n\theta }{r\cos \theta } \\ \end{align}

where $$\alpha,\beta=re^{\pm i\theta}$$. Following through with the substitutions you end up with

$$f_n=\sqrt{2}^n\bigg[(f_1-f_0)\sin\frac{n\pi}{4}+f_0\cos\frac{n\pi}{4}\bigg]$$

Solving the characteristic polynomial is just a way of providing linearly independent solutions... In fact, both the real and imaginary parts will be solutions to your equation. So, the general solution will be in fact $$(\sqrt{2})^n (C \cos \frac{n \pi}{4} + D \sin \frac{n \pi}{4}).$$ Very simply speaking, you have space of dimension 2, and you come up with two linearly independent vectors, which will of course form a basis.

• Your answer is too advanced for me to follow. Could you explain why the two complex roots in polar form cannot be plugged into $u_n = A(\text{root}_1)^n + B(\text{root}_2)^n$? This appears valid when the complex roots are in rectangular form. Jun 15, 2020 at 14:05