1. ## How did they get this answer to mathematical induction?

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

>=(4 + 12k)
4^(k+1)>=(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?

Thank you!!!

2. $\displaystyle P(k): 1+3k\leq 4^k$ We assume this and we need to obtain $\displaystyle P(k+1): 1+3(k+1)\leq 4^{k+1}$

$\displaystyle 4*[1+3k]\leq [4^k]*4\rightarrow 4+12k\leq 4^{k+1}\rightarrow 4+3k+9k\leq 4^{k+1}$ Since k is positive, we can drop the 9k term WLOG.

Thus, $\displaystyle 4+3k\leq 4^{k+1}\rightarrow 1+3+3k\leq 4^{k+1}\rightarrow 1+3(1+k)\leq 4^{k+1}\rightarrow 1+3(k+1)\leq 4^{k+1}$

3. How did you get 4 + 3k + 9k <= 4^k+1 from 4 + 12k <= 4^(k+1)

4. What is 9k+3k equal to?

5. 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 $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 $4^{k+1}\ \ge\ 1+3(k+1)$

$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!!!
Here is another way...

P(k)

$1+3k\ \le\ 4^k$

P(k+1)

replace k with k+1

$1+3(k+1)\ \le\ 4^{k+1}$

Try to show that P(k+1) has to be valid if P(k) is valid

Proof

if $4^{k+1}\ \ge\ 1+3(k+1)$ ......get this in the form $4^k$ and $1+3k$ for comparison.

then $(4)4^k\ \ge\ 1+3k+3$

$(3)4^k+4^k\ \ge\ (1+3k)+3.$

Since $(3)4^k\ \ge\ 3$ for all $k\ \ge\ 0$

then $4^{k+1}\ \ge\ 1+3(k+1)$ if $4^k\ \ge\ 1+3k$