# Induction

• Aug 25th 2010, 03:30 PM
Apprentice123
Induction
How can I prove by induction that:

\$\displaystyle 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
\$\displaystyle (k+1)^2 = k^2 + 2k + 1 > 3k + 2k + 1 = 5k + 1\$

Also, writing \$\displaystyle P(k) = k^2 > 3k\$ is syntactically wrong -- \$\displaystyle P(k)\$ is a proposition, not a number.
• Aug 25th 2010, 04:03 PM
Apprentice123
Why \$\displaystyle (k+1)^2 > 3k+2k+1\$ ??
• Aug 25th 2010, 04:17 PM
Defunkt
Use the induction hypothesis - \$\displaystyle 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
\$\displaystyle (k+1)^2 = k^2 + 2k + 1\$
\$\displaystyle 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 \$\displaystyle k^2 + 2k + 1 > 3k + 2k + 1\$?
If yes, then my argument is

\$\displaystyle 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 \$\displaystyle 2^{2n} -1\$ is divisible by 3

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

4m + 1 is divisible by 3 then \$\displaystyle 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 \$\displaystyle 2^{2n} -1\$ is divisible by 3

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

4m + 1 is divisible by 3 then \$\displaystyle 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