Solving recurrences whose characteristic equations have complex roots

976 Views Asked by At

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?

2

There are 2 best solutions below

1
On

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

3
On

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