How to solve nonhomgenous recurrence relation? I'm studying this topic in advance and I'm working on textbook problems. The problem is simple :

Solve the following recurrence relation
a) $a(n+1)-a(n)=2n+3$, $n$ is greater than or equal to $0$ and $a(0)=1$
b) $a(n+1)-a(n)=3n^2-n$, $n$ is greater than or equal to $0$ and $a(0)=3$

The answer in the back of the text says:

a) $a(n)=(n+1)^2$, $n$ greater than or equal to $0$
b) $a(n)=3+n(n-1)^2$, $n$ greater than or equal to $0$

I'm new to this topic and I want to know a efficient way to solve this problem. It is also good if you explain only one of them but step by step explanation to answer would be very much appreciated.
 A: Recurrences of the form
$$ a_{n+1} = a_n + f(n) $$
are so common that they have a specialized notation, namely
$$ a_n = a_0 + \sum_{k=0}^{n-1} f(k) $$
Note that this is not a solution, merely a different notation for the same problem -- if you write out the formal meaning of what the $\sum$ notation stands for, you get exactly the original recurrence back.
However, you probably already know some techniques for dealing with finite sum; for example the first one
$$ a_n = 1 + \sum_{k=0}^{n-1} 2k + 3 $$
is just the sum of a finite arithmetic sequence, which equals the number of terms times the average of the first and last term (Gauss's trick), so we get
$$ a_n = 1 + n\frac{2\cdot 0 + 3 + 2(n-1) + 3}{2} = n^2 + 2n + 1$$
which you may be able to recognize as the square of $n+1$.

In the second recurrence you have $g(n)=\sum_k f(k)$ where $f$ is a second-degree polynomial. What I do with such things is to remember that $g$ in that case is always a polynomial one degree higher, and then I find its coefficients by expanding $g(n+1)=g(n)+f(n)$, simplifying, and then equating terms of the same degree in $n$.
Somewhere there's probably a nice canned formula that allows one to compute the coefficients of $g$ directly from those of $f$, but I don't care to go around remembering it -- it's not that often I have to sum polynomial progressions.
A: Here is a general technique for linear recurrence relations. You start by solving the homogeneous equation

$$ a(n+1)-a(n) = 0 $$

by assuming $a(n)=r^n$ and plugging back in the above equation which gives the characteristic equation
$$ r-1=0 \implies r=1 $$
which yields the solution $a_h(n)=c_1$. 
The second step is to find a particular solution for the equation

$$ a(n+1)-a(n) = 2n+3  \longrightarrow (2)$$ 

by assuming 
$$ a_p(n)= An^2+Bn+C $$
and plugging back in $(2)$ to determine the constants $A,B,C$ to get 
$$ a_p(n) = n^2+2n. $$
So the general solution is given by

$$ a(n) = a_h(n) + a_p(n) = c_1 + n^2+2n. $$

To determine $c_1$ we exploit the initial condition $a(0)=1$ to get the final answer

$$ a(n)=1+2n+n^2 = (n+1)^2. $$

A: Given
$$
a(n+1)-a(n)=f(n)\tag{1}
$$
we can sum $(1)$ and get a telescoping series
$$
\begin{align}
\sum_{k=0}^{n-1}f(k)
&=\sum_{k=0}^{n-1}[a(k+1)-a(k)]\\
&=\sum_{k=1}^na(k)-\sum_{k=0}^{n-1}a(k)\\
&=a(n)+\sum_{k=1}^{n-1}a(k)-\sum_{k=1}^{n-1}a(k)-a_0\\[9pt]
&=a(n)-a(0)\tag{2}
\end{align}
$$
This sum is called a telescoping series because
$$
\begin{align}
&\sum_{k=0}^{n-1}[a(k+1)-a(k)]\\
&=[a_n\overbrace{-a_{n-1}]+[a_{n-1}}^{\text{cancel}}\overbrace{-a_{n-2}]+[a_{n-2}}^{\text{cancel}}\overbrace{-a_{n-3}]+\dots+[a_2}^{\text{cancel ... cancel}}\overbrace{-a_1]+[a_1}^{\text{cancel}}-a_0]\\[9pt]
&=a_n-a_0\tag{3}
\end{align}
$$
That is, the paired adjacent terms cancel and the whole sum collapses, just like a telescope being put away.
Equation $(2)$ says
$$
a_n=a_0+\sum_{k=0}^{n-1}f(k)\tag{4}
$$
Thus, if we know how to sum $f(k)$, then we can solve $(1)$.
There are many posts showing how to sum polynomials, so I will just quote a few:
$$
\begin{align}
\sum_{k=0}^{n-1}1&=n\\
\sum_{k=0}^{n-1}k&=\frac{n(n-1)}2\\
\sum_{k=0}^{n-1}k^2&=\frac{(2n-1)(n-1)n}6\\
\end{align}\tag{5}
$$
Equations $(4)$ and $(5)$ should enable you to solve the problems you are given.
