0
$\begingroup$

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?).

$\endgroup$
1
  • $\begingroup$ @sikfeng yes, corrected. $\endgroup$ – Mihael Jun 15 '20 at 14:00
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Mihael Jun 15 '20 at 14:05
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.