<s>[INST] 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!
 [/INST] 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$.
</s>