# Complex Recursion

Consider the recursive function $$C_n = C_{n-1} + iC_{n-2}$$, where $$C_1 = 1, C_2 = 1.$$ If $$C_{10}$$ is written in the form $$a+bi,$$ find $$b$$.

I solved this problem through brute force with a calculator. Is there an elegant solution method? I wasn't able to find any pattern in the terms, nor was I able to find a nice geometric solution.

• It's a linear recurrence, we can easily find closed form of $C_n$. – Jakobian Oct 17 '18 at 19:56
• Have you learned about recurrence relations? – saulspatz Oct 17 '18 at 19:59
• I've seen them briefly before in an intro combinatorics class, but I was under the impression that it wouldn't work in this case because we have imaginary coefficients. – math783625 Oct 17 '18 at 20:00
• Note; I'm not sure that the closed form solution helps all that much. The roots of the associated quadratic aren't very nice. Given that you only want $C_{10}$, I'd just do it recursively. – lulu Oct 17 '18 at 20:06
• @math783625 The math works fine with complex numbers, but that doesn't help much in this case. I wrote my comment before solving the equation. I agree with others comments that the exact solution is too messy to be useful. – saulspatz Oct 17 '18 at 20:10

You have a function $$n\mapsto C_n$$ that satisfies the stated recursion, and you make the educated guess that it’ll be a linear combination of exponentials, of which a basic one looks like $$n\mapsto T^n$$ for some value of $$T$$. The recurrence says $$T^{n+2}=T^{n+1}+iT$$, from which you immediately factor out $$T^n$$ to get the quadratic $$T^2-T-i=0$$. Roots of course are $$t=\frac{1+\sqrt{1+4i}}2\,,\qquad t'=1-t_1\,,$$ and you must absolutely not try to go numerical at this stage.
You expect that $$C_n=At^n+B(1-t)^n$$, and by trying this with $$C_0=1$$ and $$C_1=1$$, you get $$A=t/(2t-1)$$ and $$B=(t-1)/(2t-1)$$. This gives the closed-form description $$C_n=\frac{t^{n+1}}{2t-1}\>-\> \frac{(1-t)^{n+1}}{2t-1}\,.$$ Only now do you call in your symbolic calculator, and find that when $$n=10$$, you get, lo and behold, $$C_{10}=-12-25i$$.