Solve the recurrence $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)$
 A: 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}.$$
A: 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 ...
A: 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.
