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 ???

Printable View

- Aug 25th 2010, 03:30 PMApprentice123Induction
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 PMDefunkt
$\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 PMApprentice123
Why $\displaystyle (k+1)^2 > 3k+2k+1$ ??

- Aug 25th 2010, 04:17 PMDefunkt
Use the induction hypothesis - $\displaystyle k^2 > 3k$

- Aug 25th 2010, 04:33 PMApprentice123
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 PMDefunkt
$\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 PMApprentice123
I not understand why 3k+2k+1 if 3(k+1) = 3k+3 not 3k+2k+1

- Aug 25th 2010, 05:10 PMDefunkt
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 PMApprentice123
I know that k^2+2k+1 > 3k+2k+1

From where did 3k+2k+1 ? - Aug 25th 2010, 05:43 PMDefunkt
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 PMApprentice123
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 PMDefunkt
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 ?

- Aug 25th 2010, 07:08 PMApprentice123
OK. Thank you