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
  • 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
    Commented Mar 14, 2017 at 15:18

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .