<s>[INST] How to solve the non-homogeneous linear recurrence $ a_{n+1} - a_n = 2n+3 $, given that $a_0=1$? The problem: $ a_{n+1} - a_n = 2n+3 $, given that $a_0=1$
First I solved the associated homogeneous recurrence and got $a_n = A(1)^n = A$, where A is a constant, but I got stuck solving the rest. My final answer was $a_n=2n^2+n+1$ while my textbook has $a_n=n^2+2n+1$
Here is my work:
$ a_{n+1} - a_n = 2n+3 $
$pn=nd_1+d_2$ for all n
plug in and solve for $d_1$:
$(n+1)d_1+d_2-nd_1-d_2=2n+3$
$d_1=2n+3$
then solve for $d_2$:
$a_0=1=a_{n+1}-2n-3=(n+1)d_1+d_2-2n-3$
$d_2=1-n(2n+3)$
therefore
$p_n=nd_1+d_2 = 2n^2+n+4$ and $a_n=A+2n^2+n+4$
then solve for A:
$a_0=1=A +0+0+4$ so $A=-3$
therefore
$a_n=2n^2+n+1$
 [/INST] You got in trouble when you set up $p_n$. Since the forcing term is linear, we expect $p_n$ to be quadratic in $n$; $p_n=d_0n^2+d_1n+d_2$. Now we have
$$\begin{align*}
2n+3&=p_{n+1}-p_n\\
&=d_0(n+1)^2+d_1(n+1)+d_2-d_0n^2-d_1n-d_2\\
&=d_0(2n+1)+d_1\\
&=2d_0n+(d_0+d_1)\;.
\end{align*}$$
This has to hold for all $n$, so we must have $2=2d_0$ and $3=d_0+d_1$. Solving this system is easy: $d_0=1$, so $d_1=2$, and $p_n=n^2+2n+d_2$. Now we want $p_0=a_0=1$, so $d_2=1$, and 
$$p_n=n^2+2n+1\;.$$
Finally, $a_n=p_n+A=n^2+2n+1+A$, and setting $n=0$ shows that we must have $A=0$.
Alternatively, we could have left $d_2$ temporarily undetermined, writing $p_n=n^2+2n+d_2$, and observed that then
$$a_n=n^2+2n+d_2+A\;;$$
setting $n=0$ yields the conclusion that $d_2+A=1$ and hence $a_n=n^2+2n+1$. That is, it wasn’t actually necessary to solve separately for $d_2$ and $A$, since in the end we care only about their sum anyway.
</s>