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?

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

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


$${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) ! \ }$$


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

  • $\begingroup$ 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 :) $\endgroup$ – R.C Dec 4 '17 at 14:59
  • $\begingroup$ Wow! You did something constructive with my remark! This is very cool! +1 $\endgroup$ – 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)$.

  • $\begingroup$ 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? $\endgroup$ – R.C Dec 4 '17 at 14:24
  • $\begingroup$ That's just a standard series you get from differentiating $\sum x^n$ twice. $\endgroup$ – marty cohen Dec 4 '17 at 18:52
  • $\begingroup$ 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. $\endgroup$ – R.C Dec 5 '17 at 1:54

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.