Results 1 to 4 of 4

Math Help - Proof by Induction

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    2

    Proof by Induction

    n^2 - n is even for any n >= 1

    So far i have the base case:
    n=1 1^2-1 = 0 and 2^2-2=2 which are both even.
    then prove for n = k so k^2 - 2 for k>=1

    then n= (k+1)^2 - (k+1).... having problems with further steps.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    715
    Thanks
    2
    [LaTeX ERROR: Convert failed] .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,831
    Thanks
    1602
    Why do you have to use induction?

    If n is odd and \geq 1, then n = 2k+1 where k \in \{0, 1, 2, \dots\} and

    n^2 - n = (2k + 1)^2 - (2k + 1)

     = (2k + 1)(2k + 1 - 1)

     = 2k(2k + 1) which is clearly even.


    If n is even and >1, then n = 2m where m = \{1, 2, 3, \dots\} and

    n^2 - n = (2m)^2 - 2m

     = 2m(2m - 1)

    which is clearly even.


    Therefore n^2 - n is even for any n \geq 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by zaj091000 View Post
    n^2 - n is even for any n >= 1

    So far i have the base case:
    n=1 1^2-1 = 0 and 2^2-2=2 which are both even.
    then prove for n = k so k^2 - 2 for k>=1

    then n= (k+1)^2 - (k+1).... having problems with further steps.
    n^2-n is even for n\ \ge\ 1

    You've completed the base case...

    Now you must show whether or not...

    true\ for\ n=k causes true\ for\ n=k+1

    P(k)

    k^2-k is even

    P(k+1)

    (k+1)^2-(k+1) is even if P(k) is true

    Proof

    (k+1)^2-(k+1)=k^2+2k+1-k-1=k^2+k=\left(k^2-k)+2k

    Since 2k is even...

    If P(k) is true, then P(k+1) is definately true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction that 4| 5^n - 1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 11:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 17th 2010, 08:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2008, 05:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum