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?
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).