<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] Let $f(z) = \sum_{n=0}^\infty a_n z^n$. Multiplying both sides of the recurrence by $z^n$ and summing over $n$ yields
$$\sum_{n=0}^\infty a_{n+1}z^n - \sum_{n=0}^\infty a_nz^n = \sum_{n=0}^\infty(2n+3)z^n $$
and hence
$$z^{-1}(f(z)-a_0) - f(z) = 2\sum_{n=0}^\infty (n+1)z^n + \sum_{n=0}^\infty z^n, $$ so that
$$f(z)(1-z) = 1 + \frac{2z}{(1-z)^2}+\frac z{1-z} $$
and
\begin{align}
f(z) &= \frac1{1-z}+\frac z{(1-z)^2} + \frac{2z}{(1-z)^3}\\
&= \frac{(1-z)^2+z(1-z)+2z}{(1-z)^3}\\
&= \frac{1 - 2z + z^2 + z -z^2 + 2z}{(1-z)^3}\\
&= \frac{1+z}{(1-z)^3}.
\end{align}
Expanding $f$ in a power series about $z=0$ yields
$$f(z) = \sum_{n=0}^\infty(n+1)^2 z^n, $$
so that $a_n=(n+1)^2, n\geqslant0$.
</s>