# Induction

• Aug 25th 2010, 03:30 PM
Apprentice123
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 ???
• Aug 25th 2010, 03:38 PM
Defunkt
$(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.
• Aug 25th 2010, 04:03 PM
Apprentice123
Why $(k+1)^2 > 3k+2k+1$ ??
• Aug 25th 2010, 04:17 PM
Defunkt
Use the induction hypothesis - $k^2 > 3k$
• Aug 25th 2010, 04:33 PM
Apprentice123
OK. But I not understand why
K^2 > 3k
(k+1)^2 > 3(k+1) ---Why you used 3k+2k+1 ???
• Aug 25th 2010, 04:43 PM
Defunkt
$(k+1)^2 = k^2 + 2k + 1$
$k^2 > 3k \Rightarrow k^2 + 2k + 1 > 3k + 2k + 1$
• Aug 25th 2010, 04:50 PM
Apprentice123
I not understand why 3k+2k+1 if 3(k+1) = 3k+3 not 3k+2k+1
• Aug 25th 2010, 05:10 PM
Defunkt
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)$.
• Aug 25th 2010, 05:39 PM
Apprentice123
I know that k^2+2k+1 > 3k+2k+1

From where did 3k+2k+1 ?
• Aug 25th 2010, 05:43 PM
Defunkt
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?
• Aug 25th 2010, 06:00 PM
Apprentice123
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 ?
• Aug 25th 2010, 06:03 PM
Defunkt
Quote:

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?

Quote:

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.
• Aug 25th 2010, 07:08 PM
Apprentice123
OK. Thank you