Question 1033742
Just to make a CORRECTION:  I believe the formula you want to be proved is

{{{u[n+1] = 5^n+(-1)^n}}}

This is what we proceed to prove.
---------------------------------------------------------------------------
Proof by induction:
If n = 3, the recurrence formula gives {{{u[3] = 4*u[2]+ 5*u[1] = 16+10 = 26}}}.
Incidentally, the formula {{{u[3] = 5^2+(-1)^2 = 25+1 = 26}}} checks out.

Now assume that, up to a certain natural number k, {{{u[k] = 5^(k-1)+(-1)^(k-1)}}} is true.

We show that  {{{u[k+1] = 5^k+(-1)^k}}}.

Now {{{u[k+1] = 4u[k] +5u[k-1]}}}

==> {{{u[k+1] = 4(5^(k-1)+(-1)^(k-1)) + 5(5^(k-2)+(-1)^(k-2))}}}

= {{{u[k+1] = 4*5^(k-1)+ 4*(-1)^(k-1) + 5*5^(k-2)+  5*(-1)^(k-2)}}}
={{{4*5^(k-1)- 4*(-1)^(k-2) + 5^(k-1)+  5*(-1)^(k-2)}}}
={{{5^k + (-1)^(k-2)}}}
={{{5^k + (-1)^k}}}, since {{{(-1)^2 = 1}}}.

Therefore, {{{u[k+1] =  5^k + (-1)^k}}}, and the theorem is proved by induction.