How to find the closed form of $f(n) = 9^k \times (-56) + f(n-1)$ I have to find the closed form for 
$$T(n) = \begin{cases} 
2 , &\text{ if } n=0 \\
9T(n-1) - 56n + 63, &\text{ if } n > 1
\end{cases}$$
I used the repeated substitution method and I found that the pattern for the coefficient of n is equal to the following:
$$f(1) = -56$$
$$f(n) = 9^{n-1} \times (-56) + f(n-1)$$
I tried to find the closed form of $f(n) = 9^{n-1} \times (-56) + f(n-1)$, but it just got more and more confusing. I believe it may be a series of some sort. Is there a way to find a closed form for this?
Thank you!
 A: Usually, these problems are solved using induction. But induction requires you to already 'know' (or guess) the answer. Using generating functions we can solve the problem without having to ever guess:
$$t(n) = 9t(n-1) - 56n + 63$$
$$t(0) = 2$$
Now suppose we write:
$$T(x) = \sum_{n=0}^\infty t(n)x^n$$
We know:
$$T(x) = 2 + \sum_{n=1}^\infty (9t(n-1) - 56n + 63)x^n$$
$$T(x) = 2 +9\sum_{n=1}^\infty t(n-1)x^n -56\sum_{n=1}^\infty nx^n+ 63 \sum_{n=1}^\infty x^n$$
$$T(x) = 2 +9\sum_{n=0}^\infty t(n)x^{n+1} -56\frac{x}{(1-x)^2}+ 63 \frac{x}{1-x}$$
$$T(x) = 2 +9xT(x) -56\frac{x}{(1-x)^2}+ 63 \frac{x}{1-x}$$
$$T(x) = 2\frac{1}{1-9x} -56\frac{x}{(1-9x)(1-x)^2}+ 63 \frac{x}{(1-9x)(1-x)}$$
$$T(x) = 2\frac{1}{1-9x} +\frac{-56x + 63x(1-x)}{(1-9x)(1-x)^2}$$
$$T(x) = 2\frac{1}{1-9x} +\frac{7x(1-9x)}{(1-9x)(1-x)^2}$$
$$T(x) = 2\frac{1}{1-9x} +7\frac{x}{(1-x)^2}$$
$$T(x) = 2\sum_{n=0}^\infty 9^nx^n + 7\sum_{n=0}^\infty nx^n$$
$$T(x) = \sum_{n=0}^\infty \Big (2\cdot 9^n  + 7n\Big)x^n = \sum_{n=0}^\infty t(n)x^n$$
Therefore, $t(n) = 2\cdot 9^n + 7n$.
A: A particular solution that satisfies $T(n)=9T(n-1)-56n+63$ is
$$T(n)=An+B.$$
Then we have
$$An+B=9A(n-1)+9B-56n+63\quad \Longrightarrow\quad A=7,\,B=0$$
The solution of $T(n)=9T(n-1)$, is $T(n)=9^nC$. 
So the general solution for the problem is
$$T(n)=7n+9^nC.$$
From $T(0)=2$ we have $C=2$. 
The final solution is 
$$T(n)=7n+2\times 9^{n}.$$
A: As I was lulled into solving the problem stated in the title, let me present a general solution for problems of this type. What I will do is to reduce the problem to a generalized Fibonacci form, i.e., $f_n=af_{n-1}+bf_{n-2}$, which can be solved with the methods shown here.
So consider the recursion formula
$$f_n=A\cdot B^n+f_{n-1},\quad f_0 ~\text{given}$$
Then we can say
$$
\frac{f_n-f_{n-1}}{f_{n-1}-f_{n-2}}=\frac{A\cdot B^n}{A\cdot B^{n-1}}=B\\
\text{or}\\
f_n=af_{n-1}+bf_{n-2}\\
a=B+1,\quad b=-B\\
f_0,\quad f_1=A\cdot B+f_0
$$
The characteristic roots for this system are $B,1$. That's all there is to it. The methods given in the link provide a number of ways to express the results.
