Originally Posted by

**Thetheorycase** 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 $\displaystyle 4^k\ \ge\ 1+3k\Rightarrow\ (4)4^k\ \ge\ (4)(1+3k)$

** >=(4 + 12k)**

** 4^(k+1)>=(4 + 3k)**

..... it's only required to show $\displaystyle 4^{k+1}\ \ge\ 1+3(k+1)$

$\displaystyle 4+12k>4+3k$

** 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!!!