2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – Caleb Owusu-Yianoma Apr 23 '15 at 8:59
  • $\begingroup$ 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. $\endgroup$ – Lutz Lehmann Apr 23 '15 at 9:04
  • $\begingroup$ 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? $\endgroup$ – Caleb Owusu-Yianoma Apr 23 '15 at 9:59
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I apologise for this late response. Unfortunately, I made a slight error when writing the question. Please see the above edit. $\endgroup$ – Caleb Owusu-Yianoma Apr 23 '15 at 9:51

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.