# Solving recurrences whose characteristic equations have complex roots

In my Discrete Mathematics lecture notes, there is a section regarding solutions for linear recurrences whose characteristic polynomials have complex roots. There is a particular statement which I am struggling to understand, and I will explain it as succinctly as possible.

Suppose we have a recurrence relation $$a_k=\begin{cases}c_0 & \text{if k=1,}\\ c_1 & \text{if k=2,}\\ c_3a_{k-1}+c_4a_{k-2}+f(k) & \text{if k\geq3,}\end{cases}$$ where $f(k)$ is a polynomial of degree $d$ (this, I don't think, is a particularly helpful piece of information for my question, but is here for completeness).

Also suppose that the characteristic equation $$\lambda^k-c_3\lambda^{k-1}-c_4\lambda^{k-2}=0$$ of the homogeneous part of the recurrence $(a_k=c_3a_{k-1}+c_4a_{k-2})$ has complex roots $r_1, r_2$, where $r_1=\alpha+\beta i$ and $r_2=\gamma+\delta i$.

Then, for the homogeneous case, we want to find a solution of the form $$\alpha_1r_1^k+\alpha_2r_2^k,$$ where $\alpha_1, \alpha_2\in\mathbb{C}.$

What I haven't yet understood is a statement that the above is equivalent to finding a solution of the form $$\beta_1(r_1^k+r_2^k)+i\cdot\beta_2(r_1^k-r_2^k),$$ where $\beta_1, \beta_2 \in\mathbb{R}$.

Why exactly is this the case?

I suppose that the recurrence has real coefficients. Then you know more in that with $r_1=α+βi$ you get $r_2=α-βi=\bar r_1$.

Update: Then from the reality of the first two sequence elements one gets $α_1+α_2=\bar α_1+\bar α_2$ and $α_1·r+α_2·\bar r=\bar α_1·\bar r+\bar α_2\bar r$ which can be summarized as \begin{alignat}{4} &(α_1-\bar α_2)&&+(α_2-\bar α_1)&&=0\\ &(α_1-\bar α_2)·r&&+(α_2-\bar α_1)·\bar r&&=0\\ \end{alignat} and since $r\ne \bar r$ this homogeneous system only has the zero solution $α_1-\bar α_2=0$, $α_2-\bar α_1=0$ so that $α_1=α$ and $α_2=\bar α$.

Thus any real solution has the form $$a_k=αr^k+\bar α\bar r^k=2Re(αr^k)=2Re(α)Re(r^k)-Im(α)Im(r^k) \\=Re(α)(r^k+\bar r^k)+iIm(α)(r^k-\bar r^k)$$

• I apologise for the late response. Assuming that, where you have written $\overline{a}$, you mean $\overline{\alpha}$, why is it that the coefficients at conjugate roots are also conjugate? I.e., why is it that, WLOG, the coefficients of $r, \overline{r}$ are $\alpha, \overline{\alpha}$? Apr 23, 2015 at 8:59
• Because the $a_k$ are real. $a_k=\bar a_k=\bar α_1\bar r^k+\bar α_2 r^k$ for all $k$ leads to the identification $α_2=\bar α_1$ and $α_1=\bar α_2$. Since the complex coefficients have two real degrees of freedom, one loses nothing in flexibility. Apr 23, 2015 at 9:04
• I have tried to show that $a_k=\alpha_1r^k+\alpha_2\overline{r}^k=\overline{\alpha}_1\overline{r}^k + \overline{\alpha}_2r^k=\overline{a}_k$ for all $k$ leads to the identification $\alpha_2=\overline{\alpha}_1$ and $\alpha_1=\overline{\alpha}_2$, but have not yet managed. Please could you explain why this is so? Apr 23, 2015 at 9:59

There are two things to show:

A) Given any $\beta_1$ and $\beta_2$, there exist $\alpha_1$ and $\alpha_2$ such that $$\beta_1(x+y)+\beta_2(x-y)=\alpha_1x+\alpha_2y,\tag{1}$$ for all $x$ and $y$, and

B) Given any $\alpha_1$ and $\alpha_2$, there exist $\beta_1$ and $\beta_2$ such that $$\beta_1(x+y)+\beta_2(x-y)=\alpha_1x+\alpha_2y.\tag{2}$$ for all $x$ and $y$. Note that A) is easy. Expand the left-hand side of (1), and we see that $\alpha_1=\beta_1+\beta_2$ and $\alpha_2=\beta_1-\beta_2$.

For B), again expand the left-hand side of (2). We want $\beta_1+\beta_2=\alpha_1$ and $\beta_1-\beta_2=\alpha_2$. Solve this system for $\beta_1$ and $\beta_2$. We get $\beta_1=\frac{\alpha_1+\alpha_2}{2}$ and $\beta_2=\frac{\alpha_1-\alpha_2}{2}$.

• I apologise for this late response. Unfortunately, I made a slight error when writing the question. Please see the above edit. Apr 23, 2015 at 9:51