Proving a simple recurrence relation via induction

Question

There is a recurrence relation such that

$$T(0) = 0, T(1) = 1$$

$$T(n) = 7T(n-1) -12T(n-2)$$

And I'm trying to prove that $$T(n) = -3^n + 4^n$$

So far I have the following

Check base cases for 0,1

$$T(0) = -3^0 + 4^0 = 0$$ $$T(1) = -3^1 + 4^1 = 1$$

As both of these are true we can continue

Next we assume that (inductive hypothesis) $$T(n) = -3^n + 4^n$$

And for the inductive step we have $$T(n+1) = -3^{n+1} + 4^{n+1}$$

We know from our recurrence relation that $$T(n + 1) = 7T(n) - 12T(n-1)$$

This is where I am stuck. I know I can substitute in T(n) but I'm not sure what to do for T(n-1)

Answer 1

"Next we assume that $T(k)=-3^k+4^k$ for all $k\leq n$"

Now...

"For the inductive step we want to prove that $T(n+1)=-3^{n+1}+4^{n+1}$"

So to do that, we use a chain of equalities and algebra, and use the inductive hypothesis somewhere in the middle.

$$\begin{array}{rl}T(n+1)&=7T(n)-12T(n-1)\\&=\dots\\\vdots\\&=\dots~~\text{(by induction hypothesis)}\\ \vdots\\&=-3^{n+1}+4^{n+1}\end{array}$$

$T(n+1)=7T(n)-12T(n-1)=7(-3^n+4^n)-12(-3^{n-1}+4^{n-1})=\dots$

Answer 2

Let P(m) denotes the truth value of the equation $T(m)=−3^m+4^m$ Assume $P(0)\wedge P(1)\land P(2)\wedge...\wedge P(k)$

We want to prove that P(K) is true, in other words, prove that $T(k+1)=−3^{k+1}+4^{k+1}$

By the recurrence relation we have \begin{align} T(k+1)&=7T(k)−12T(k−1)\\ &=7(−3^k+4^k)-12(−3^{k-1}+4^{k-1})\\ &=(6+1)(−3^k+4^k)-4*3(−3^{k-1}+4^{k-1})\\ &=2*3(-3^k+4^k)+(−3^k+4^k)-4*(−3^{k}+3*4^{k-1})\\ &=2*(-3^{k+1}+3*4^k)−3^k+4^k+4*3^k-3*4^k\\ &=2*(-3^{k+1}+3*4^k)+3*3^k-2*4^k\\ &=2*(-3^{k+1})+2*(3*4^k)+3*3^k-2*4^k\\ &=2*(-3^{k+1})+3*3^k+6*4^k-2*4^k\\ &=-2*3^{k+1}+3^{k+1}+4*4^k\\ &=-3^{k+1}+4^{k+1} \end{align}

This completes the proof.