# Solving Recurrences via Characteristic Polynomial with Imaginary Roots

In algorithm analysis you often have to solve recurrences. In addition to Master Theorem, substitution and iteration methods, there is one using characteristic polynomials.

Say I have concluded that a characteristic polynomial $x^2 - 2x + 2$ has imaginary roots, namely $x_1 = 1+i$ and $x_2 =1-i$. Then I cannot use

$\qquad c_1\cdot x_1^n + c_2\cdot x_2^n$

to obtain the solution, right? How should I proceed in this case?

• Welcome! Note that you can use LaTeX by $...$. Mar 31, 2012 at 10:38
• I am confused. I am sure you mean the method using characteristc polynomials, not equations. What is $j$? The solutions of the equation you give are not imaginary, but merely irrational. What do you mean by "apply the [polynomial]"? Mar 31, 2012 at 10:40
• He's adopted the physicist's habit of misspelling $i$. Mar 31, 2012 at 11:41
• Of course, you can actually. First, the solution satisfies the reoccurrence. Second, the solution space is of dimension 2. Apr 3, 2012 at 5:23

## 1 Answer

Yes, the solution is in fact $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$ determined by the base cases. If the bases cases are real, then (by induction) all the complex terms in $T(n)$ will cancel, for all integer $n$.

For example, consider the recurrence $T(n) = 2T(n-1) - 2T(n-2)$, with base cases $T(0)=0$ and $T(1)=2$. The characteristic polynomial of this recurrence is $x^2-2x+2$, so the solution is $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$. Plugging in base cases gives us $$T(0) = \alpha(1+i)^0 + \beta(1-i)^0 = \alpha+\beta = 0\\ T(1) = \alpha(1+i)^1 + \beta(1-i)^1 = (\alpha+\beta) + (\alpha-\beta)i = 2$$ which implies $$\alpha + \beta = 0 \\ \alpha - \beta = -2i$$ which implies $\alpha = -i$ and $\beta = i$. So the solution is $$T(n) = i\cdot ((1-i)^n - (1+i)^n).$$

This function oscillates between $\sqrt{2}^n$ and $-\sqrt{2}^n$ with a "period" of 4. In particular, we have $T(4n) = 0$ for all $n$, because $(1-i)^4 = (1+i)^4 = -4$ (and because I chose the base case $T(0)$ carefully).

• I seem to remember that imaginary roots of the characteristic polynomial (which are, if I remember correctly, the sequence's generating function's dominating singularities) imply negative elements somewhere. Is that true? If so, it is safe to say you should never encounter this case in algorithm analysis. Mar 31, 2012 at 12:23
• Not necessarily. If the roots of the characteristic function are $2$, $1+i$, and $1-i$, for example, the function will oscillate around $\alpha 2^n$ for some $\alpha$, but (with appropriate base cases) it will always be positive. Mar 31, 2012 at 13:24