# Prove by induction....

• Sep 5th 2012, 02:21 AM
linalg123
Prove by induction....
1. Prove that for all $m \in N$, prove that $2m \leq m^2+1$

2. Hence, or otherwise, prove by induction that for all $n \in N$ there exists a $k \in N$ such that $n \leq k^2 \leq 2n$

for 1. would it just be $0 \leq m^2 - 2m +1$
$0 \leq (m-1)^2$?
• Sep 5th 2012, 02:40 AM
Prove It
Re: Prove by induction....
\displaystyle \begin{align*} (m - 1)^2 &\geq 0 \textrm{ for all } x \in \mathbf{R} \\ m^2 - 2m + 1 &\geq 0 \\ m^2 + 1 &\geq 2m \end{align*}
• Sep 5th 2012, 03:06 AM
linalg123
Re: Prove by induction....
So for part 2, I haven't done many proofs by induction.

You say let n=1. So $1 \leq k^2 \leq 2$. True for k=1

Suppose it's true for n=j. So $j \leq k^2 \leq 2j$

Prove it's true for n=j+1. So $j+1 \leq k^2 \leq 2j+2$

Is that right? I still don't know how to do it though. Any help?
• Sep 5th 2012, 05:21 AM
emakarov
Re: Prove by induction....
Quote:

Originally Posted by linalg123
Suppose it's true for n=j. So $j \leq k^2 \leq 2j$

Prove it's true for n=j+1. So $j+1 \leq k^2 \leq 2j+2$

Is that right? I still don't know how to do it though.

The induction statement P(n) is "there exists a k such that n ≤ k² ≤ 2n". You assume P(j) and you are allowed to call the number whose existence is guaranteed by P(j) simply by k. Now you need to prove a new existence statement P(j + 1); the new number whose existence you need to prove may or may not be equal to k from P(j). Therefore, it is unreasonable to try to prove that j + 1 ≤ k² ≤ 2j + 2 always holds for that particular k.

However, we can break the inductive step into two cases. From P(j) we know that j ≤ k². Case 1 is when j < k²; then P(j + 1) is obvious for the same k. Case 2 is when j = k²; then clearly you need to find a new k' such that j + 1 ≤ k'² ≤ 2j + 2. Can you do this?

There is also a direct proof of P(n) for all n. Fix an n and let m = max {i | i² < n}. Then m² < n (which is the same thing as m² ≤ n - 1), but (m + 1)² ≥ n. We need to show that (m + 1)² ≤ 2n. We have

m² + 2m + 1 = m² + 2m - 1 + 2 ≤ (since 2m - 1 ≤ m² by 1) 2m² + 2 ≤ (since m² ≤ n - 1) 2n - 2 + 2 = 2n.
• Sep 5th 2012, 07:31 PM
linalg123
Re: Prove by induction....
Quote:

Originally Posted by emakarov
The induction statement P(n) is "there exists a k such that n ≤ k² ≤ 2n". You assume P(j) and you are allowed to call the number whose existence is guaranteed by P(j) simply by k. Now you need to prove a new existence statement P(j + 1); the new number whose existence you need to prove may or may not be equal to k from P(j). Therefore, it is unreasonable to try to prove that j + 1 ≤ k² ≤ 2j + 2 always holds for that particular k.

However, we can break the inductive step into two cases. From P(j) we know that j ≤ k². Case 1 is when j < k²; then P(j + 1) is obvious for the same k. Case 2 is when j = k²; then clearly you need to find a new k' such that j + 1 ≤ k'² ≤ 2j + 2. Can you do this?

There is also a direct proof of P(n) for all n. Fix an n and let m = max {i | i² < n}. Then m² < n (which is the same thing as m² ≤ n - 1), but (m + 1)² ≥ n. We need to show that (m + 1)² ≤ 2n. We have

m² + 2m + 1 = m² + 2m - 1 + 2 ≤ (since 2m - 1 ≤ m² by 1) 2m² + 2 ≤ (since m² ≤ n - 1) 2n - 2 + 2 = 2n.

I understand the direct proof, thanks, but i'm still not sure about the induction one.

I get Case 1 because if $j then clearly $j+1 \leq k^2 \leq 2j+2$

for Case 2, if $j=k^2$ $j+1 \leq (k+1)^2$

$(k+1)^2 = k^2 + 2k -1 +2 \leq 2k^2+2$ but $j=k^2$

$(k+1)^2 \leq 2j+2$

k'=k+1

Is that correct? And is that fully proved now by induction?
• Sep 6th 2012, 12:46 AM
emakarov
Re: Prove by induction....
Quote:

Originally Posted by linalg123
Is that correct? And is that fully proved now by induction?

Yes.