# linear homogeneous recurrences: $r$ is a solution if and only if $r^n$ is a solution

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

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

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.