Results 1 to 4 of 4

Thread: 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
    $\displaystyle (k+1)^2 = k^2+2k+1$.
    Follow Math Help Forum on Facebook and Google+

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

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

    $\displaystyle n^2 - n = (2k + 1)^2 - (2k + 1)$

    $\displaystyle = (2k + 1)(2k + 1 - 1)$

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


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

    $\displaystyle n^2 - n = (2m)^2 - 2m$

    $\displaystyle = 2m(2m - 1)$

    which is clearly even.


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

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    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.
    $\displaystyle n^2-n$ is even for $\displaystyle n\ \ge\ 1$

    You've completed the base case...

    Now you must show whether or not...

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

    P(k)

    $\displaystyle k^2-k$ is even

    P(k+1)

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

    Proof

    $\displaystyle (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, 10:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 17th 2010, 07:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Nov 1st 2008, 04:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum