Recurrence equation solution? Can you help me with the solution of this recurrence equation?
$$
    f(n+2) = -2f(n) +3f(n+1) +n \quad\mid\quad f(1)=4 \quad\mid\quad f(2)=5
$$
Thank you.

suppose we define  $u(n) = f(n+1) - f(n).$  then we can rewrite 
$f(n+2) = -2f(n) + 3f(n+1) + n$ as $$u(n+1) = 2u(n) + n, u(1) = 1$$
we will loo for a particular solution in the form of  $u(n) =an+ b $ we need 
$an + a + b = 2an+ 2b + n$ is satisfied if $a = 2a+1, a+b = 2b$ which is satified if $a = b = -1$ and the homogeneous solution is $u = c2^n$ so the general solution is $$u(n) = 3*2^{n-1} - n - 1$$ which also satisfies the initial condition $u(1) = 1.$
now we need to solve $$f(n+1) - f(n) =   3*2^{n-1} - n - 1, f(1) = 4.$$ verify that $$f(n) =  3*2^{n-1} - \frac{1}{2}n^2 - n + \frac{5}{2}$$ is the solution.
