Homework 2: On complex roots for annihilator equations

September 23rd, 2008

Many of you have asked me what to do when we get complex roots to the annihilator equations resulting from solving a recurrence. My answers to date have been very unsatisfying: basically I said to ignore them. This is in fact wrong (!). Here’s an explanation why, with a solution for what you need to do.

Suppose we’re solving some recurrence and get a collection of roots that includes some complex numbers. In particular, let’s say we’re solving an (ahem) 3rd order recurrence, and we get three roots, a, b, and c. The first thing to note is that complex roots occur in conjugate pairs (I’ll leave you to ponder why that is). So if a is the real root of this equation, and b and c are the complex roots, we can write b = re^{\iota\theta}, c = re^{-\iota\theta}.

By the standard argument, we know that the recurrence solution is of the form
T(n) = s_1 a^n + s_2 b^n + s_3 c^n
where s_1, s_2, and s_3 are constants.

Now since T(n) only takes real values, the complex numbers need to “cancel out” the imaginary parts, which can only happen if s_2 = s_3 = s (why?). In this case, we can simplify the second and third terms as
s(b^n + c^n) = sr^n(e^{\iota n\theta} + e^{-\iota n\theta}) = sr^n\cos(n\theta) \le s r^n

Finally, this gives us
T(n) \le s_1 a^n + s r^n, which we can now solve for s_1 and s in the usual way.

What does this mean overall ? It means that if you get complex roots, then find the absolute value (the absolute value of a complex number a + \iota b is \sqrt{a^2 + b^2}), and then continue as before.

This entry was posted on Tuesday, September 23rd, 2008 at 3:05 pm and is filed under news.

Leave a Reply