How to find the closed form of $f(n) = 9^k \times (-56) + f(n-1)$

Question

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!

Answer 1

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$.

Answer 2

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}.$$

Answer 3

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.