I'm trying to come up with a proof for this theorem:

Let $c_1$ and $c_2$ be real numbers with $c_2 != 0$. Suppose that $r^2 - c_1 r - c_2 = 0$ has only one root, $r_0$. A sequence $\{a_n\}$ is a solution of the recurrence relation $a_n = c_1 a_{n-1} + c_2 a_{n-2}$. If and only if $a_n$ = $a_1r^n_0$ + $a_2nr^n_0$, for $n = 0,1,2...$ where $\alpha_1$ and $\alpha_2$ are constants.

(I'm trying to also make the $a_n$ sequence above have the subscript of n-1 and n-2, respectively, not subtracted from the whole equation, if someone can tell me how to edit that!) Thank you!

My answer so far..not sure if this is right

Proof: Suppose $a_n$ = $a_1r_0^n$ + $a_2r_0^n$. By definition, $r_0$ is the only root of $r^2 - c_1 r - c_2$, so $r_0^2 = c_1 r_0 + c_2$. Moreover, since it's the only root, it's also a root of the derivative, so $2r_0 = c_1$. Then:

$$c_1a_{n-1} + c_2a_{n-2} = c_1[\alpha_1r_0^{n-1} + \alpha_2(n-1)r_0^{n-1}] + c_2[\alpha_1 r_0^{n-2} + \alpha_2 (n-2)r_0^{n-2}]$$ $$...$$ $$=\alpha_1r_0^n + \alpha_2nr_0^n + \alpha_2r_0^{n-1} [c_1 - 2r_0]$$ $$ = a_n$$

So, $a_n$ satisfies the recurrence relation. If $a_0$ = $C_0$ and $a_1 = C_1$, then $\alpha_1 = C_0$ and $C_1 = (\alpha_1 + \alpha_2)r_0$, so $\alpha_2 = \frac{C_1 - C_0r_0}{r_0}$

Since this is a unique solution, we are done.

  • $\begingroup$ How can a quadratic equation have only one root? $\endgroup$ – Ron Gordon Apr 15 '13 at 1:26
  • $\begingroup$ @RonGordon: $x^2+2x+1$ has only one root. $\endgroup$ – Glen O Apr 15 '13 at 1:32
  • $\begingroup$ We call that a double root and it is treated accordingly - there are two independent solutions to an equation with that characteristic equation. $\endgroup$ – Ron Gordon Apr 15 '13 at 1:33
  • 1
    $\begingroup$ @jtm22: There's a flaw in your theorem. The general solution to a second-order recurrence relation with a single root is of the form $a_n = (\alpha_1+n\alpha_2)r^n$. The extra "$n$" is important. $\endgroup$ – Glen O Apr 15 '13 at 1:33
  • 1
    $\begingroup$ Potato, potahto. The point is, it is a fallacy to say that a quadratic has only one root. Better to say that you are looking for a double, repeated,..., whatever, root. $\endgroup$ – Ron Gordon Apr 15 '13 at 1:39

Your Answer

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

Browse other questions tagged or ask your own question.