Can this recurrence relation be solved with generating functions? I have this recurrence relation,
$$a_{n+1}=\frac{n+2}{n}a_n$$
with $a_1=1$.
I've already solved this using a substitution approach by letting $a_n=\dfrac{(n+1)!}{(n-1)!}b_n$. This means $a_{n+1}=\dfrac{(n+2)!}{n!}b_{n+1}$, and so
$$\begin{align*}
\frac{(n+2)!}{n!}b_{n+1}&=\frac{n+2}{n}\frac{(n+1)!}{(n-1)!}b_n\\
b_{n+1}&=b_n\\
\sum_{n=1}^{k-1}(b_{n+1}-b_n)&=0\\
b_k&=b_1\\
b_k&=\frac{(1-1)!}{(1+1)!}a_1\\
b_k&=\frac{1}{2}
\end{align*}$$
Finally, $a_n=\dfrac{n(n+1)}{2}$.
I'm wondering if there's a way to use generating functions to solve this relation? I've been having trouble working with the $\dfrac{2}{n}a_n$ term. Are there only certain cases of relations for which generating functions are useful?
 A: Hint: Let
$$
f(x)=\sum_{n=1}^\infty\frac{a_n}{n}x^n
$$
Then, formally,
$$
f'(x)=\sum_{n=1}^\infty a_nx^{n-1}
$$
Now, consider $2xf(x)+x^2f'(x)$:
$$
2xf(x)+x^2f'(x)=2x\sum_{n=1}^\infty\frac{a_n}{n}x^n+x^2\sum_{n=1}^\infty a_nx^{n-1}=\sum_{n=1}^\infty \left(\frac{2a_n}{n}+a_n\right)x^{n+1}
$$
Since $a_1=1$, we have
$$
x+2xf(x)+x^2f'(x)=f(x)
$$
so, one must solve the differential equation
$$
x+2xy+x^2y'=y.
$$
(This is assuming that I got my indices right).
A: Perhaps easier than Michael Burr's method is to start with:
$$
n a_{n + 1} = (n + 2) a_n
$$
Define $A(z) = \sum_{n \ge 0} a_n z^n$, and remember:
$\begin{align}
\sum_{n \ge 0} a_{n + 1} z^n
  &= \frac{A(z) - a_0}{z} \\
\sum_{n \ge 0} n a_n z^n
  &= z \frac{\mathrm{d}}{\mathrm{d} z} A(z)
\end{align}$
Taking the recurrence, multiplying by $z^n$, adding over $n \ge 0$ and using the above:
$$
z \frac{\mathrm{d}}{\mathrm{d} z} \frac{A(z) - a_0}{z}
  = z \frac{\mathrm{d}}{\mathrm{d} z} A(z) + 2 A(z)
$$
Simplifying this gives an ODE, with initial condition $A(0) = a_0$.
A: Induction is easier, but to use generating functions let's assume that
$$
f(x)=\sum_{n=1}^\infty a_nx^n
$$
Then
$$
\begin{align}
\sum_{n=1}^\infty na_{n+1}x^n
&=x\left(\frac{f(x)}x\right)'\\
&=f'(x)-\frac{f(x)}x
\end{align}
$$
and
$$
\begin{align}
\sum_{n=1}^\infty(n+2)a_nx^n
&=\frac1x\left(f(x)x^2\right)'\\
&=2f(x)+xf'(x)
\end{align}
$$
Equating these functions gives
$$
(1-x)f'(x)=\left(2+\frac1x\right)f(x)
$$
Therefore, dividing both sides by $(1-x)f(x)$ and integrating, we get
$$
\begin{align}
\log(f(x))
&=\int\frac{2x+1}{x(1-x)}\,\mathrm{d}x\\
&=\int\left(\frac1x+\frac3{1-x}\right)\,\mathrm{d}x\\
&=\log\left(\frac x{(1-x)^3}\right)+C
\end{align}
$$
So that if $a_1=1$,
$$
\begin{align}
f(x)
&=\frac{x}{(1-x)^3}\\
&=\sum_{n=1}^\infty(-1)^{n-1}\binom{-3}{n-1}x^n\\
&=\sum_{n=1}^\infty\binom{n+1}{n-1}x^n\\
&=\sum_{n=1}^\infty\binom{n+1}{2}x^n\\
\end{align}
$$
Therefore,
$$
a_n=\binom{n+1}{2}
$$
A: This is a linear recurrence of the first order. So you can divide by the summing factor:
$$
\prod_{1 \le k \le n} \frac{k + 2}{k}
  = \frac{(k + 2)!}{1 \cdot 2 \cdot k!}
  = \frac{(k + 1) (k + 2)}{2}
$$
Really any constant multiple of this will do, take $(n + 1) (n + 2)$:
$$
\frac{a_{n + 1}}{(n + 1) (n + 2)} - \frac{a_{n}}{n (n + 1)} = 0
$$
This just means that the fraction is constant, i.e.:
$\begin{align}
\frac{a_n}{n (n + 1)}
  &= \frac{a_1}{1 \cdot 2} \\
a_n
  &= a_1 \cdot \frac{n (n + 1)}{2}
\end{align}$
