Solving this non-homogenous recurrence relation I'm tasked with solving the following recurrence relation,
$$f(n) = n^2 + f(n-1)$$
for $f(1) = 1$. In my class I have only learned how to solve homogenous relations with the characteristic equation method and so have no intuition for non-homogenous relations. Could I have any hints?
 A: The idea is the same as non-homogeneous differential equations: the relation is linear in $f$, so any solution can be written as the sum $f=g+h$ of a solution to $g(n)-g(n-1)=0$ and a particular solution to $h(n)-h(n-1)=n^2$.
The particular solution is normally found by guessing and substituting in to find undetermined coefficients: for polynomials the right thing to try is a polynomial of slightly higher degree (e.g. in this case, $(n+1)^3-n^3=3n^2+3n+1$, so try $h(n)=an^3+bn^2+cn+d$).
A: Let $$g(n) = f(n) - f(n-1)$$$$g(n) = n^2$$
Let $$h(n) = g(n) - g(n-1)$$$$h(n) = n^2 - (n-1)^2$$$$h(n)=(n-(n-1))(n+(n-1))$$$$h(n)=(n-n+1)(n+n-1)=2n-1$$
Let $$i(n)=h(n)-h(n-1)$$$$i(n)=2n-1-(2(n-1)-1)$$$$i(n)=2n-1-2n+3 = 2$$
Let $$j(n)=i(n)-i(n-1)$$$$j(n)=2-2=0$$
From this point,$$i(n)-i(n-1)=0$$
$$h(n)-h(n-1)-(h(n-1)-h(n-2))=0$$
$$h(n)-2h(n-1)+h(n-2)=0$$
$$g(n)-g(n-1)-2(g(n-1)-g(n-2))+g(n-2)-g(n-3)=0$$
$$g(n)-3g(n-1)+3g(n-2)-g(n-3)=0$$
$$f(n)-f(n-1)-3(f(n-1)-f(n-2))+3(f(n-2)-f(n-3))-(f(n-3)-f(n-4))=0$$
$$f(n)-4f(n-1)+6f(n-2)-4f(n-3)+f(n-4)=0$$
And then we can solve by linear homogeneous recurrence relation now.
