According to my textbook and this Wikipedia article, a recurrence relation of the form $$ b_0 a_n + b_1 a_{n-1} + \cdots + b_k a_{n-k} = 0 $$ (EDIT: where $ b_0 \neq 0 $) has the following set of solutions (assuming $ r_1, r_2,\cdots r_p $ are the non-zero distinct roots of the characteristic polynomial and $ r'_1, r'_2, \cdots r'_q $ are non-zero roots that appear $ s_1, \cdots s_q $ times respectively):
$$ a_n = c_1 r_1^n + c_2 r_2^n + \cdots c_k r_k ^ n + k_{11} {r'_1}^n + k_{12} n {r'_1}^n + \cdots k_{1 s_1} n^{s_1} {r'_1}^n + \cdots + k_{q s_q} n^{s_q} {r'_q}^n $$
My question is, how does one prove the formula above? What I've managed to show is that if all roots are distinct, then $ u_n = c_1 r_1^n + c_2 r_2^n + \cdots c_k r_k ^ n $ is a solution to the recurrence relation.