Solve the recurrence

Question

$T(n) = 2$ if $n=0$

$T(n) = 9T(n-1)-56n +63$ if $n>=1$

Repeated substitution

$k=1$

$T(n) = 9T(n-1)-56n+63 $

$k =2$

$T(n) = 81T(n-2) -560n + 1134$

$k =3$

$T(n) = 729T(n-3) -5096n + 15309$

I cant find the pattern for the n term and the integer

For now i just have

T(n) = $9^k(n-k)$

Answer 1

First find a particular solution that satisfies $T(n)=9T(n-1)-56n+63$. Let the particular solution be

$$T(n)=An+B.$$

Then we have

$$An+B=9A(n-1)+9B-56n+63.$$

For this to hold for all $n$, we have $A=7$, $B=0$. Then find the general solution of $T(n)=9T(n-1)$, which is $T(n)=9^nC$. So the general solution for the problem is

$$T(n)=7n+9^nC.$$

To find $C$ we need the initial condition $T(1)=2$. So $C=-5/9$. The final solution is

$$T(n)=7n-5\times 9^{n-1}.$$

Answer 2

Let's apply generating functions. It's not always the easiest method, but it solidly works. From $$T_n=9T_{n-1}-56n+63$$ the generating function is $$f(x)=\sum\limits_{n=0}T_nx^n \tag{1}$$ $$f(x)=T_0+\sum\limits_{n=1}T_nx^n=T_0+\sum\limits_{n=1}\left(9T_{n-1}-56n+63\right)x^n=\\ T_0+9\sum\limits_{n=1}T_{n-1}x^n-56\sum\limits_{n=1}nx^n+63\sum\limits_{n=1}x^n=\\ T_0+9x\sum\limits_{n=1}T_{n-1}x^{n-1}-56x\sum\limits_{n=1}nx^{n-1}+63\sum\limits_{n=1}x^n=\\ T_0+9xf(x)-\frac{56x}{(1-x)^2}+\frac{63x}{1-x}$$ Or $$f(x)=T_0+9xf(x)-\frac{56x}{(1-x)^2}+\frac{63x}{1-x}$$ $$f(x)=\frac{T_0}{1-9x}-\frac{56x}{(1-9x)(1-x)^2}+\frac{63x}{(1-9x)(1-x)}$$ $$f(x)=\frac{T_0}{1-9x} +\frac{7}{(1 - x)^2} + \frac{7}{8(1 - x)} - \frac{63}{8(1 - 9x)} -\frac{63}{8(1 - x)} + \frac{63}{8(1 - 9x)}=\\ f(x)=\frac{T_0}{1-9x} +\frac{7}{(1-x)^2} -\frac{7}{1-x}$$

$$f(x)=T_0\sum\limits_{n=0}(9x)^n+7\sum\limits_{n=0}(n+1)x^n-7\sum\limits_{n=0}x^n=\sum\limits_{n=0}\left(T_0\cdot 9^n +7n \right)x^n \tag{2}$$ Or, comparing the terms of $(1)$ and $(2)$ $$T_n=T_0\cdot 9^n +7n$$ Some of the shortcuts are explained here.

The final step is to find $T_0$ ...

• from $\color{red}{2=T_0\cdot9+7}$, given $T(n)=2$ if $n=1$, this was the original question, as per the edit history. Or
• from $\color{red}{2=T_0}$, given $T(n)=2$ if $n=0$, this is from the updated question, as per the edit history.

This proves how flexible the generating functions are ...

Answer 3

Here is a simpler solution, which I give for the generalized form

$$T_n=AT_{n-1}+Bn+C,\quad T_0 \text{ given}$$

Let $T_n=f_n+pn+q$, then

$$\begin{align} & {{f}_{n}}=A{{f}_{n-1}}+n\left( Ap+B-p \right)+\left( -Ap+Aq-q \right) \\ \\ & \text{Let} \\ & p=-\frac{B}{A-1};\quad q=-\frac{pA-C}{A-1} \\ & f_{n}=A{{f}_{n-1}} \\ & f_n=f_0A^n,\quad f_0=T_0+q\\ \\ & T_n=f_0A^n+pn+q \end{align} $$

In the present case, with $[A,B,C]=[9,-56,63]$, we find that $[p,q,f_0]=[7,0,2]$ so that

$$T_n=2\cdot 9^n +7n$$

I have verified this solution numerically.