Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been trying to solve the recurrence:

\begin{align*} a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3}, \end{align*}

where $a_0=5$, via generating functions with little success. My progress until now is this:

Let $A(x)=\sum_{n=0} ^{\infty} a_nx^n$. By multiplying both sides of our recurrence relation by $x^n$ and summing over $n$ from $0$ to $\infty$, we see that \begin{align} \sum_{n=0} ^{\infty} a_{n+1} x^n = \frac{2}{3}\sum_{n=0} ^{\infty} (n+1)a_nx^n + \sum_{n=0} ^{\infty} (n+1)!x^n. \end{align} Using our definition of $A(x)$ we can rewrite the left hand side as \begin{align*} \sum_{n=0} ^{\infty} a_{n+1} x^n=\frac{A(x)-a_0}{x}. \end{align*} Such manipulations of the right hand side have been difficult because of the coefficients of the power series.

Is there anyway to proceed from here, or are generating functions not suited to solve such a recurrence?

share|improve this question
Hint: Use exponential generating function, instead of an ordinary generating function. –  Sasha Apr 23 '12 at 14:09
Sorry about posting the full answer, I did not spot your request for hints only. I will try to be more attentive. –  Sasha Apr 23 '12 at 15:41
@sasha That is fine. Once you had suggested the exponential generating function, I worked out the rest of the problem on my own, and your full solution helped me to verify that I had proceeded correctly. Thank you. –  Holdsworth88 Apr 23 '12 at 16:15
add comment

3 Answers 3

up vote 13 down vote accepted

Exponential generating function of sequence $\{a_n\}$ is $f(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}$. Rewriting the recurrence equation as $$ \frac{a_{n+1}}{n+1} = \frac{2}{3} a_n + \frac{5}{3} n! $$ Now multiplying both sides by $\frac{x^n}{n!}$ and using recurrence relation for factorial: $$ a_{n+1} \frac{x^n}{(n+1)!} = \frac{2}{3} a_n \frac{x^n}{n!} + \frac{5}{3} x^n $$ Summing from $n=0$ to infinity: $$ \frac{1}{x} \sum_{n=1}^\infty a_n \frac{x^n}{n!} = \frac{2}{3} \sum_{n=0}^\infty a_n \frac{x_n}{n!} + \frac{5}{3} \sum_{n=0}^\infty x^n $$ or $$ \frac{1}{x} \left( f(x) - a_0 \right) = \frac{2}{3} f(x) + \frac{5}{3} \frac{1}{1-x} $$ Solving for $f(x)$ we readily get: $$ f(x) = \frac{5}{1-x} = \sum_{n=0}^\infty (5 \cdot n!) \frac{x^n}{n!} $$ Thus the solution is $a_n = 5 \cdot n!$.

share|improve this answer
It might be best to more clearly parenthesize or separate out the argument to the factorial at the end; I read that multiple times as $(5n)!$ rather than $5\cdot(n!)$... –  Steven Stadnicki Apr 30 '13 at 20:39
add comment

A first order linear non-homogeneous recurrence: $$ a_{n + 1} - c_n a_n = f_n $$ can be reduced to a telescoping sum by dividing by the summing factor $s_n = \prod_{0 \le k \le n} c_n$: $$ \begin{align*} \frac{a_{n + 1}}{s_n} - \frac{a_n}{s_{n - 1}} &= \frac{f_n}{s_n} \\ \sum_{0 \le n \le m - 1} \frac{a_{n + 1}}{s_n} - \frac{a_n}{s_{n - 1}} &= \sum_{0 \le n \le m - 1} \frac{f_n}{s_n} \\ \frac{a_m}{s_{m - 1}} - \frac{a_0}{1} &= \sum_{0 \le n \le m - 1} \frac{f_n}{s_n} \end{align*} $$ It is easier to go through this dance each time. Here the summing factor is: $$ \prod_{0 \le k \le n} \frac{2}{3}(n + 1) = \left( \frac {2}{3} \right)^{n + 1} (n + 1)! $$ Dividing through by this gives: $$ \begin{align*} \frac{a_{n + 1}}{(2 / 3)^{n + 1} (n + 1)!} - \frac{a_n}{(2/3)^n n!} &= \frac{5}{3 (2 / 3)^{n + 1}} \\ \frac{a_n}{(2/3)^n n!} - \frac{a_0}{1} &= \frac{5}{3} \sum_{0 \le k \le n - 1} (3/2)^{k + 1} \\ \frac{a_n}{(2/3)^n n!} &= 5 + \frac{5}{3} \cdot \frac{3}{2} \cdot \frac{(3/2)^n - 1}{3/2 - 1} \\ &= 5 + 5 \left( (3/2)^n - 1 \right) \\ a_n &= 5 n! \end{align*} $$

share|improve this answer
add comment

Generating functions are kind of overkill here: introducing $b_n=\frac{a_n}{n!}$, one sees that the recursion on $(a_n)_n$ translates as $b_{n+1}=\frac23b_n+\frac53$.

This is an affine recursion hence one knows that to center the recursion at its fixed point, if such a fixed point exists, will make it linear. Here the fixed point solves $b=\frac23b+\frac53$, that is, $b=5$. And, surprise, one gets the linear relation $b_{n+1}-5=\frac23(b_n-5)$ for every $n\geqslant0$.

Iterating this yields $b_n-5=\left(\frac23\right)^n(b_0-5)$, that is, $\frac{a_n}{n!}-5=\left(\frac23\right)^n(a_0-5)$. If $a_0=5$, the RHS is zero hence $a_n=5\cdot n!$ for every $n\geqslant0$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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