Solving the recursion $3a_{n+1}=2(n+1)a_n+5(n+1)!$ via generating functions

Question

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?

Answer 1

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

Answer 2

Generating functions are definitely overkill here: considering $$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 is trivial and 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).$$ Since one assumes that $a_0=5$, the RHS is zero hence, for every $n\geqslant0$, $$a_n=5\cdot n!.$$

Answer 3

Being lazy and prove it by MI for fun.

Obviously, $a_0=5(0!)$, now assume $a_n=5n!$ for some natural number $n$, then

$$ \begin{aligned} 3 a_{n+1} &=2(n+1) 5 n !+5(n+1)_{0}^{1} \\ &=5 n !(2 n+2+n+1) \\ a_{n+1} &=5(n+1) ! \end{aligned} $$ proved.