$u_{0,1} = 1;u_2 = 3;u_{n}=3u_{n-1}-3u_{n-2}+u_{n-3}$ Prove that $u_n=n^2-n+1$ using induction

Question

$u_{0,1} = 1;$

$u_2 = 3;$

$u_{n}=3u_{n-1}-3u_{n-2}+u_{n-3}$

"Prove that $u_n=n^2-n+1$ using induction." Can anyone help? Always ending in recursion without solving it.

Answer 1

The tedious way would be to show that

$n^2-n+1=$

$3((n-1)^2-(n-1)+1)-3((n-2)^2-(n-2)+1)+(n-3)^2-(n-3)+1.$

Here is another way.

Define $a_n=u_{n+1}-u_n$ and $b_n=a_{n+1}-a_n$.

Then show $b_{n+1}-{b_n}=0,$ so $b_n=b_0=2$.

Then telescoping $a_n-a_0=\sum\limits_{i=1}^{n} (a_i-a_{i-1})=\sum\limits_{i=0}^{n-1}b_i=2n,$ so $a_n=2n$.

Finally, $u_n-u_0=\sum\limits_{i=1}^n(u_i-u_{i-1})=\sum_{i=0}^{n-1}a_i=(n-1)n,$ so $u_n=n^2-n+1$.