Expressing a recurrence relation as a polynomial 
Let us define $u_0 = 0, u_1 = 1$ and for $n \geq 0$, $u_{n+2} = au_{n+1}+bu_n$, $a$ and $b$ being positive integers. Express $u_n$ as a polynomial in $a$ and $b$. Prove the result: Given that $b$ is prime, prove that $b$ divides $a(u_b-1)$.

How do we deal with the case that the characteristic equation has a double root? We can deal with the other case by just solving the recurrence, but how should we do it in the general case?

Let's see if we find a pattern.
\begin{align}
u_0&=0\\
u_1&=1\\
u_2&=au_1+bu_0=a\\
u_3&=au_2+bu_1=a^2+b\\
u_4&=au_3+bu_2=a(a^2+b)+ab=a^3+2ab\\
u_5&=au_4+bu_3=a(a^3+2ab)+b(a^2+b)=a^4+3a^2b+b^2
\end{align}
It seems reasonable to assert that, for $n\ge2$,
$$
u_n=a^{n-1}+bf_n(a,b)
$$
where $f_n(a,b)$ is a polynomial in $a$ and $b$. This can be proved by induction (do it).
Finally we have
$$
a(u_b-1)=a(a^{b-1}+bf_b(a,b)-1)=(a^b-a)+bf_b(a,b)
$$
Can you prove this is divisible by $b$, when $b$ is prime?
