# Math Help - Induction

1. ## Induction

How can I prove by induction that:

$n^2 > 3n$ for all n>=4

I do:
n=k
P(k) = k^2 > 3k
P(k+1) = (k+1)^2 > 3(k+1)

How to solve
P(k) --> P(k+1) to prove that P(n) is truth ???

2. $(k+1)^2 = k^2 + 2k + 1 > 3k + 2k + 1 = 5k + 1$

Also, writing $P(k) = k^2 > 3k$ is syntactically wrong -- $P(k)$ is a proposition, not a number.

3. Why $(k+1)^2 > 3k+2k+1$ ??

4. Use the induction hypothesis - $k^2 > 3k$

5. OK. But I not understand why
K^2 > 3k
(k+1)^2 > 3(k+1) ---Why you used 3k+2k+1 ???

6. $(k+1)^2 = k^2 + 2k + 1$
$k^2 > 3k \Rightarrow k^2 + 2k + 1 > 3k + 2k + 1$

7. I not understand why 3k+2k+1 if 3(k+1) = 3k+3 not 3k+2k+1

8. It's an intermediate step..
Do you understand why $k^2 + 2k + 1 > 3k + 2k + 1$?
If yes, then my argument is

$k^2 > 3k \Rightarrow (k+1)^2 =k^2 + 2k + 1 > 3k + 2k + 1 \overbrace{ > }^{k > 1} 3k + 2 + 1 = 3k + 3 = 3(k+1)$.

9. I know that k^2+2k+1 > 3k+2k+1

From where did 3k+2k+1 ?

10. Why does it matter? I don't really understand what's your difficulty. Can you tell me what part you don't understand of my last line in the last post?

11. What you did was take an any expression to prove that (k+1)^2 > 3k + 3 ?

For example

Prove that $2^{2n} -1$ is divisible by 3

I do:
$2^{2k} - 1 = 3m$
$2^{2k} = 3m + 1$
$2^{2k+2} = 12m+4$
$2^{2k+2} -1 = 3(4m+1)$

4m + 1 is divisible by 3 then $2^{2n} - 1$ also divisible by 3

Correct ?

12. Originally Posted by Apprentice123
What you did was take an any expression to prove that (k+1)^2 > 3k + 3 ?
I don't understand your question. Can you rephrase?

For example

Prove that $2^{2n} -1$ is divisible by 3

I do:
$2^{2k} - 1 = 3m$
$2^{2k} = 3m + 1$
$2^{2k+2} = 12m+4$
$2^{2k+2} -1 = 3(4m+1)$

4m + 1 is divisible by 3 then $2^{2n} - 1$ also divisible by 3

Correct ?
That is correct, but you might want to say where you're using the induction hypothesis.

13. OK. Thank you