# Find the formula for the sequence $(a_n)$ that satisfies the recurrence relation $a_n=(n+7)a_{n-1}+n^2$ with $a_0=1$

Find the formula for the sequence $(a_n)$ that satisfies the recurrence relation $a_n=(n+7)a_{n-1}+n^2$ with the initial condition $a_0=1$.

This is a non-linear nonhomogeneous recurrence relation. What I can think that may help solve this problem is using the idea of generating function.
Let $G(x)=\sum_{n=0}^{\infty}a_nx^n$. Then \begin{aligned} G(x)&=a_0+\sum_{n=1}^{\infty}a_nx^n\\ &=1+\sum_{n=1}^{\infty}\left((n+7)a_{n-1}+n^2\right)x^n\\ &=1+\sum_{n=1}^{\infty}\left((n+7)a_{n-1}x^n\right)+\sum_{n=1}^{\infty}(n^2x^n) \end{aligned} Then I was stuck here, because I couldn't change the two summations into forms of $G(x)$.
Anyone has brillant ideas?

• Does it help that the corresponding homogeneous recurrence is solved by $a_n=k(n+7)!$? – G Tony Jacobs Dec 4 '17 at 13:57
• @GTonyJacobs But it's not practical for you to guess a correct form of the particular solution. – R.C Dec 4 '17 at 14:18
• @R.C, that's why I phrased my comment as a question. :) – G Tony Jacobs Dec 4 '17 at 14:19
• @GTonyJacobs's idea leads to $$a_n = (n+7)!(1/7!+ \sum_{k=1}^n k^2/(k+7)!)$$ – Gribouillis Dec 4 '17 at 14:30
• @Gribouillis, can you give a detailed explanation how you reach this result in the answer section? – R.C Dec 4 '17 at 14:36

## 4 Answers

Following @GTonyJacobs remark about the homogeneous sequence, let us define (this is a discrete method of variation of the parameter)

$${a}_{n} = \left(n+7\right) ! \ {b}_{n}$$

We have

$$\left(n+7\right) ! \ {b}_{n} = \left(n+7\right) \left(n+6\right) ! \ {b}_{n-1}+{n}^{2}$$

hence

$${b}_{n}-{b}_{n-1} = \frac{{n}^{2}}{\left(n+7\right) ! \ }$$

It follows that

$${b}_{n} = {b}_{0}+\sum _{k = 1}^{n} \left({b}_{k}-{b}_{k-1}\right) = \frac{1}{7 ! \ }+\sum _{k = 1}^{n} \frac{{k}^{2}}{\left(k+7\right) ! \ }$$

hence

$${a}_{n} = \left(n+7\right) ! \ \left(\frac{1}{7 ! \ }+\sum _{k = 1}^{n} \frac{{k}^{2}}{\left(k+7\right) ! \ }\right)$$

• This is an extremely good method, analog to the method of variation of parameters in solving ODEs. But I'm still looking for solutions using generating functions :) – R.C Dec 4 '17 at 14:59
• Wow! You did something constructive with my remark! This is very cool! +1 – G Tony Jacobs Dec 4 '17 at 15:06

Since the solution of $$b_{n} = (n+7) b_{n-1},\quad b_0=1$$ is clearly given by $b_n=\frac{(n+7)!}{7!}$, it looks like a good idea to enforce the substitution $a_n=\frac{(n+7)!}{7!}A_n$, leading to $A_0=1$ and

$$A_n - A_{n-1} = \frac{7!n^2}{(7+n)!}.\tag{A}$$ By summing both sides of $(A)$ over $n=1,2,\ldots,N$ we get $$A_N = 1+\sum_{n=1}^{N}\frac{7!n^2}{(7+n)!}\tag{B}$$ and $$a_N = \frac{(N+7)!}{7!}+\sum_{n=1}^{N}\frac{(N+7)!n^2}{(n+7)!}.\tag{C}$$ In particular, for large values of $N$ we have $$a_N \approx (N+7)!\cdot\left(37e-\frac{21121}{210}\right). \tag{D}$$

Set $b_n=a_n+n-5$ to eliminate the term in $n^2$ and we get $b_n=(n+7)b_{n-1}+37$

Now set $b_n=(n+7)!c_n$ to get the difference formula $c_n-c_{n-1}=\dfrac{37}{(n+7)!}$

Sum the telescoping series and $c_n=c_0+37\sum\limits_{k=8}^{n+7}\dfrac 1{k!}$

With $a_0=1$ then $b_0=-4$ and $c_0=-\dfrac 4{7!}$ and after isolating the partial sum from $k=\{0..7\}$

$a_n=(n+7)!\left(37\sum\limits_{k=0}^{n+7}\dfrac 1{k!}-\dfrac{21121}{210}\right)+5-n$

We can eventually replace by $\sum\limits_{k=0}^{n+7}\dfrac 1{k!}=e\,\Gamma(n+8,1)$ the incomplete gamma function, explaining the equivalent given by Jack D'Aurizio.

$x^8G(x) =\sum_{n=0}^{\infty}a_nx^{n+8}$ so $(x^8G(x))' =\sum_{n=0}^{\infty}(n+8)a_nx^{n+7} =\sum_{n=1}^{\infty}(n+7)a_{n-1}x^{n+6} =x^6\sum_{n=1}^{\infty}(n+7)a_{n-1}x^{n}$.

From this you can set up a differential equation for $G(x)$.

• This is a good idea. What about the term $\sum_{n=1}^{\infty}n^2x^n$? From your method, I guess maybe Cauchy product will be used here? – R.C Dec 4 '17 at 14:24
• That's just a standard series you get from differentiating $\sum x^n$ twice. – marty cohen Dec 4 '17 at 18:52
• After I changed the original recurrence relation into a nonhomogeneous differential equation related to $G(x)$, I found it not easy to solve the differential equation since its coefficients were not constants. – R.C Dec 5 '17 at 1:54