# 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?

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).

• I like seeing that it ends with a simple linear ODE. Thanks for the hint! Jun 9 '15 at 15:52
• Note: I made a correction to the indices in the final differential equation (the $1$ should have been an $x$). Jun 9 '15 at 15:54

$$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$.

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}$$

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}