Results 1 to 6 of 6

Math Help - Induction problem

  1. #1
    Newbie
    Joined
    Feb 2006
    Posts
    18

    Induction problem

    N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1 =
    1 + 2 + 3 + ... N



    I am trying to prove the statement above by using induction however, I am not sure what the statement means

    First I tried to find a base case when N=1

    1^2 + 1 = 1 which is not true

    Can someone please help me out? Thanks
    Last edited by hotmail590; October 7th 2006 at 12:19 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hotmail590 View Post
    N^2 - (N-1)^2 + (N-2)^2 - (n-3)^2 + ... + 1 =
    1 + 2 + 3 + ... + n



    I am trying to prove the statement above by using induction however, I am not sure what the statement means

    First I tried to find a base case when N=1

    1^2 + 1 = 1 which is not true

    Can someone please help me out? Thanks
    I think you are not providing all the information that you have and we need
    to do this. For instance are N and n the same or is one twice the other?

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2006
    Posts
    18
    Sorry for the typo, its just one variable N
    Also there was not any +'s before 1 and N at the ends


    Prove by induction that the sum:

    N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1

    equals to

    1 + 2 + 3 + ... N
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hotmail590 View Post
    Sorry for the typo, its just one variable N
    Also there was not any +'s before 1 and N at the ends


    Prove by induction that the sum:

    N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1

    equals to

    1 + 2 + 3 + ... N
    Base case: the first is 1 when N=1, as is the second, hence the base case
    holds.

    Now suppose that for some k:

    k^2 - (k-1)^2 + (k-2)^2 - (k-3)^2 + ... 1 = k + (k-1) + .. + 1

    ..............................................=k(k+1)/2

    Now:

    (k+1)^2 - k^2 + (k-1)^2 - ... 1

    ...........=(k+1)^2 - (k^2 - (k-1)^2 + (k-2)^2 - (k-3)^2 + ... 1)

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

    ...........=(k+1)^2 - k(k+1)/2 = k^2/2 + 3k/2 + 1= (k+1)(k+2)/2

    ...........= (k+1) + k + .. +1.

    So if the two expressions are equal for some N=k they are equal for N=k+1,
    and they are equal for N=1, hence by induction they are equal for all
    N>=1.

    RonL
    Last edited by CaptainBlack; October 7th 2006 at 02:06 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2006
    Posts
    18
    Thanks for all your help CaptainBlack. I would just like to make sure that I got the base case for the problem.


    So the left side:

    N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1


    Is equivalent to N(N+1)/2 so when N = 1, (base case) that would equal to 1(1+1)/2 =1

    And for the right side:

    1+2+3...N

    It would be just 1 when N =1 right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hotmail590 View Post
    Thanks for all your help CaptainBlack. I would just like to make sure that I got the base case for the problem.


    So the left side:

    N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1


    Is equivalent to N(N+1)/2 so when N = 1, (base case) that would equal to 1(1+1)/2 =1

    And for the right side:

    1+2+3...N

    It would be just 1 when N =1 right?
    Not quite, we have

    N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1

    and when N=1 is just 1, as there is but a single term.

    The N(N+1)/2 is present in what I wrote as it is the sum of the first
    N integers, that is:

    1 + 2 + .. + N = N(N+1)/2,

    the proof requires that the sum of the consecutive integers be replaced
    by this short from to make the subsequent calculations simpler.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another induction problem help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 12th 2012, 04:57 PM
  2. induction problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 22nd 2010, 07:28 AM
  3. induction problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 8th 2009, 09:18 PM
  4. induction problem,
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 7th 2009, 05:57 AM
  5. Induction Problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 15th 2007, 09:33 AM

Search Tags


/mathhelpforum @mathhelpforum