Can this recurrence relation be solved with generating functions?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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