My professor gave us the answer to a homework question and i dont know how she got some of it?
1 + 3n <= 4^n, n >= 0 for all integers n
Base case
let n = 0
then 1 + 3n = 1 + 3(0) = 1
4^n = 4^0 = 1
1 + 3n = 1 = 4^n good
next inductive Step
P(k) ----> P(k + 1)
4^k >= 1 + 3k (ind hyp)
4^(k+1) = 4^k x 4 laws of exponent
>=(1 +3k) 4 by induction
.......if
>=(4 + 12k) 4^(k+1)>=(4 + 3k)
..... it's only required to show
4^(k+1)>=1 + 3k + 3 4^(k+1)>=1 + 3(k + 1) conclusion
What i dont get is in bold
1) It looks like they flipped the equity sign and equation after the base case? why?
2) The stuff in bold i see they multiplied (1 + 3k) to get (4 + 12k). how did they get to (4 + 3k) then to
1 + 3k + 3?
they used the fact that 4+12k>4+3k and (4)+3k=(1+3)+3k
Thank you!!!