I have a homework assignment that requires me to prove a recursive function through induction. It seems like that I am stuck on simple algebraic properties and I can't figure it out… If you can, please direct me to the properties(examples would be awesome) instead of the solution. I feel like I really need to solve this one myself to find inner peace.
Given : T(n) = { 0 if n = 0; 5 if n=1; 3T(n-1) + 4T(n-2) if n > 1}
Prove by induction that for all natural numbers n, T(n) = 4n – (-1)n
The following is my logic,
since I have to prove T(n+1), I have to prove T(n+1) = 4n+1 – (-1)n+1
Base Case: T(0) = 40 – (-1)0 = 1 – 1 = 0
Induction Step: Assume T(n), prove T(n+1). I want to prove that 3T(n-1) + 4T(n-2) + (n+1) = 4n+1 – (-1)n+1
1. 3T(n-1) + 4T(n-2) + (n+1)
2. 3[4n-1 – (-1)n-1] + 4[4n-2 – (-1)n-2] + (n+1)
3. 3[4n-1 – (-1)n-1] + 4n-1 – 4(-1)n-2 + (n+1)
4. 3*4n-1 – 3*(-1)n-1 + 4n-1 – 4(-1)n-2 + (n+1)
5. 4*4n-1 – 3*(-1)n-1 – 4(-1)n-2 + (n+1)
6. 4n – 3*(-1)n-1 – 4(-1)n-2 + (n+1)
7. 4n – [-1n-2(3(-1)-4)] + (n+1)
8. 4n – [-1n-2(-3-4)] + (n+1)
9. 4n – [-1n-2(-7)] + (n+1)
10. 4n – 1[-1n-2(-7)] + (n+1)
11. 4n -1n-1(-7) + (n+1)
So that's as far as I've gone. I feel like I am almost there, but I am not sure what to do with the (-7) and the (n+1) at the end. Any help would be greatly appreciated!
Best Answer
Spoiler Alert $$ \begin{align} T(n+1) &= 3T(n)+4T(n-1)\\ &= 3(4^n-(-1)^n)+4(4^{n-1}-(-1)^{n-1})\\ &= (3+1)4^n-3(-1)^n-4(-1)^{n-1}\\ &= 4^{n+1}-(-1)^{n-1}(3(-1)^1+4)\\ &= 4^{n+1}-(-1)^{n-1}\\ &= 4^{n+1}-(-1)^{n+1} \end{align} $$