# 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 $...$. – Raphael Mar 31 '12 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]"? – Raphael Mar 31 '12 at 10:40
• He's adopted the physicist's habit of misspelling $i$. – JeffE Mar 31 '12 at 11:41
• Of course, you can actually. First, the solution satisfies the reoccurrence. Second, the solution space is of dimension 2. – Strin Apr 3 '12 at 5:23

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).
• 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. – JeffE Mar 31 '12 at 13:24