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

Do you familiar with power series trick? see here https://en.wikipedia.org/wiki/Recurrence_relation#Solving — C.F.G, Oct 04 '17 at 20:41
https://www.wolframalpha.com/input/?i=t(n)%3D9t(n-1)-56n%2B63 — Peter, Oct 04 '17 at 20:44
Try generating functions, here is an example https://math.stackexchange.com/questions/2426330/how-to-solve-non-homogeneous-recurrence-relations-r-n-2-leftr-n-1-bin/2427791#2427791 — rtybase, Oct 04 '17 at 21:21
The solution you have accepted is incorrect. Please see my correct solution below that has been verified numerically. — Cye Waldman, Oct 05 '17 at 18:16
@CyeWaldman when the accepted solution was provided, the question was stating "$T(n)=2$ if $n=1$". The question was changed since then, look at the edit history ... — rtybase, Oct 05 '17 at 20:51

score 2 · Accepted Answer · answered Oct 04 '17 at 20:47

2

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

answered Oct 04 '17 at 20:47

Zhuoran He

3,039

im trying to find the pattern – Harminder Singh Oct 04 '17 at 20:55
Then do not find the value of $C$, but write $T(n)=7n+9^nC$ and $T(n-k)=7(n-k)+9^{n-k}C$. Cancel $C$ to get the pattern $T(n)=9^kT(n-k)+7n-7(n-k)\times 9^k$, which is independent of initial condition. – Zhuoran He Oct 04 '17 at 21:03

rtybase · Answer 2 · 2017-10-05T21:04:39.547

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

score 0 · Answer 3 · answered Oct 05 '17 at 18:14

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.

Solve the recurrence

3 Answers3

Linked

Related