3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.