1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's a linear recurrence, we can easily find closed form of $C_n$. $\endgroup$ – Jakobian Oct 17 '18 at 19:56
  • $\begingroup$ Have you learned about recurrence relations? $\endgroup$ – saulspatz Oct 17 '18 at 19:59
  • $\begingroup$ 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. $\endgroup$ – math783625 Oct 17 '18 at 20:00
  • 3
    $\begingroup$ 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. $\endgroup$ – lulu Oct 17 '18 at 20:06
  • $\begingroup$ @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. $\endgroup$ – saulspatz Oct 17 '18 at 20:10
2
$\begingroup$

The comment of @lulu is most apposite. The equations are a mess, but once I caught my mistakes, the symbolic calculator worked like a charm. It’s perfectly standard recurrence-fu, and here it is:

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.