How to solve this geometric+arithmetic recurrence

Question

I've been stuck on this recurrence closed form question for a while now:

$S(n)=9S(n-1)+4n, n > 1$

$S(1) = 4$

After expanding a couple iterations to find a pattern, I came up with this:

$4*9^{n-1}+4*(n*\sum_{k=0}^{n-2}9^k-\sum_{k=0}^{n-2}k*9^k)$

$=4*9^{n-1}+4*(n*\frac{9^{n-1}-1}{9-1}-\sum_{k=0}^{n-2}k*9^k)$

However, I can't seem to get further than than that in simplifying it in terms of n. Can anyone point me in the right direction or show me how best to simplify this recurrence?

Answer 1

$$S_n=9S_{n-1}+4 n$$ Let $S_n=T_n+k n$ and replace $$T_n+k n=9T_{n-1}+9k(n-1)+4n$$ I f we want to get rid of the $n$ $$kn=9k(n-1)+4n \implies k=-\frac 12$$ Now, the problem is simple.

Answer 2

The observed pattern is fine. We have \begin{align*} S(n)&=4\cdot 9^{n-1}+4\left(n\frac{9^{n-1}-1}{9-1}-\sum_{k=0}^{n-2}k\,9^k\right)\\ &=\frac{1}{2}9^{n-1}\left(n+8\right)-\frac{1}{2}n-4\sum_{k=1}^{n-2}k\,9^{k}\tag{1} \end{align*} In (1) we have collected terms and we start the index $k$ with $1$, since the term with $k=0$ is zero. In order to get a closed form of $\sum_{k=1}^{n-2}k\,9^{k}$ by elementary means we can use the trick to write $k=\sum_{j=1}^k 1$ and then rearrange the sums to obtain geometric sums which admit a closed form.

We obtain \begin{align*} \color{blue}{\sum_{k=1}^{n-2}k\,9^k}&=\sum_{k=1}^{n-2}\left(\sum_{j=1}^k1\right)9^k=\sum_{k=1}^{n-2}\sum_{j=1}^k9^k\\ &=\sum_{1\leq j\leq k\leq n-2}9^k=\sum_{j=1}^{n-2}\sum_{k=j}^{n-2}9^k\tag{2}\\ &=\sum_{j=1}^{n-2}\frac{9^{n-1}-9^j}{9-1}\tag{3}\\ &=\frac{1}{8}9^{n-1}\sum_{j=1}^{n-2}1-\frac{1}{8}\sum_{j=1}^{n-2}9^j\tag{4}\\ &\,\,\color{blue}{=\frac{1}{64}9^{n-1}(8n-17)+\frac{9}{64}}\tag{5}\\ \end{align*}

Comment:

• In (2) we write the index region conveniently to better see how we to rearrange the sums.

• In (3) we apply the geometric summation formula to the inner sum.

• In (4) we split the sum and factor out terms.

• In (5) we apply the geometric summation formula again.

Combining (1) and (5) we obtain for $n\geq 1$: \begin{align*} \color{blue}{S(n)}&=\frac{1}{2}9^{n-1}\left(n+8\right)-\frac{1}{2}n-\frac{1}{16}9^{n-1}(8n-17)-\frac{9}{16}\\ &\,\,\color{blue}{=\frac{1}{16}\left(9^{n+1}-8n-9\right)} \end{align*}