Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Prove by induction....

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    149
    Thanks
    3

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,318
    Thanks
    1234

    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*}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2010
    Posts
    149
    Thanks
    3

    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?
    Last edited by linalg123; September 5th 2012 at 02:40 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Prove by induction....

    Quote Originally Posted by linalg123 View Post
    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.
    Thanks from linalg123
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2010
    Posts
    149
    Thanks
    3

    Re: Prove by induction....

    Quote Originally Posted by emakarov View Post
    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<k^2 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?
    Last edited by linalg123; September 5th 2012 at 06:56 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Prove by induction....

    Quote Originally Posted by linalg123 View Post
    Is that correct? And is that fully proved now by induction?
    Yes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove the following by induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 17th 2011, 04:34 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Prove by induction that (3^n + 5^n)/2 >> 4^n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 10th 2010, 09:22 AM
  4. Induction to prove
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 25th 2008, 07:24 AM
  5. Prove by induction....
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 9th 2008, 11:37 AM

Search Tags


/mathhelpforum @mathhelpforum