0
$\begingroup$

I am studying recurrence relations from the following slides. If you go to slide number 12. They state the following proposition:

$r$ is a solution of $r^k - c_1r^{k-1} - c_2r^{k-2} - \cdots - c_k = 0$ if and only if $r^n$ is a solution of $a_n = c_1a_{n-1} + c_2a_{n-2} + … + c_ka_{n-k}.$


Example:

Consider the characteristic equation $r^2 - 4r + 4 = 0$

\begin{align}r^2 - 4r + 4 &= 0 \\ (r - 2)^2 &= 0\\ \implies r &= 2\end{align}

So, $2^n$ satisfies the recurrence $F_n = 4F_{n-1} - 4F_{n-2}$.

$2^n = 4 \cdot 2^{n-1} - 4 \cdot 2^{n-2}$

$2^{n-2} ( 4 - 8 + 4) = 0$


Question

I really didn't understand the proposition. The example wasn't enough for me to get the idea. How is $r=2$ satisfying the equation. How is then $2^n$ satisfying $F_n$.

$\endgroup$
  • 1
    $\begingroup$ Can you clarify that it is $r^k$ rather than $r_k$ as shown in slides - this was confusing to me at first. $\endgroup$ – Chinny84 Mar 14 '17 at 15:18
1
$\begingroup$

I would start with the recursion relation we have $$ a_n = \sum_{i=1}^kc_ia_{n-i} $$ Now lets assume that we have $a_n = r^n$ where $r \neq 0$ then we have $$ r^n = \sum_{i=1}^kc_ir^{n-i} \implies 1 = \sum_{i=1}^kc_ir^{-i} $$ or multiply by $r^k$ to handle the pesky $r^{-i}$ $$ r^k = \sum_{i=1}^kc_ir^{k-i} $$ which is just your original statement.

Now, as long as we have this exponential form then we can have an equivalence of the relationship.

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