Exercise 6

Given a homogeneous linear recurrence relation $f(n)=a_{n}f(n-1)+\dots+a_{n-k}f(n-k)$, let $r_{1}$, …, $r_{k}$ be the roots of the associated polynomial. Prove that each function $f_{r_{i}}(n)=r_{k}^{n}$ satisfies the recurrence (without initial conditions).