Results 1 to 6 of 6

Math Help - Proof by induction

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    16

    Proof by induction

    My discreet class is working on a project and we are having trouble proving the following equation. We are to prove it using induction:

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

    We are unsure what the base case is even supposed to be. Would it be a base case of 1 or not? The multiplication factor on left side of the equation is confusing us.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by baker11108 View Post
    My discreet class is working on a project and we are having trouble proving the following equation. We are to prove it using induction:

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

    We are unsure what the base case is even supposed to be. Would it be a base case of 1 or not? The multiplication factor on left side of the equation is confusing us.
    Can you double-check the question to verify whether it should be something like

    1+2(2+3....+n)+(n+1)=(n+1)^2-1 ?

    If this is the case, then the minimum value n can be within the brackets is 2,
    since the value 3 tells you that the numbers being summed in brackets are
    all increasing by 1.

    So your base case ought to be n=2.

    To prove this using induction

    P(k) is

    1+2(2+3+4+...+n)+(n+1)=(n+1)^2-1

    P(k+1) is

    1+2(2+3+...+n+[n+1])+([n+1]+1)=([n+1]+1)^2-1

    Try to express P(k+1) in terms of P(k) to show that P(k+1) must be true if P(k) is
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    16
    No, I have it as what I originally posted.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    If you substitute some value of n into both sides,
    you will see the sides are not equal.

    For example, if n=5

    1+2(2+3+4+5)+(5-1)=1+2(14)+4=33

    (5+1)^2-1=6^2-1=36-1=35

    They differ by 2

    However, if you replace the n-1 with n+1, they are then equal.

    Hence, in sticking with the original formula,
    there is no point using induction to prove it's not true.

    However you can use induction to prove that the following is true

    1+2(2+3+...+n)+(n+1)=(n+1)^2-1
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    16
    Okay so let's assume it is n+1 on the left side rather n-1:

    we get:

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

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

    k^2+3k+3 doesn't equal the right side of the equation which is k^2+2k + 3.

    I need another K to make the sides equal. Where am I going wrong?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by baker11108 View Post
    Okay so let's assume it is n+1 on the left side rather n-1:

    we get:

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

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

    k^2+3k+3 doesn't equal the right side of the equation which is k^2+2k + 3.

    I need another K to make the sides equal. Where am I going wrong?
    You have a couple of errors there...

    You added 2 to k+1 and neglected the extra k+1 inside the brackets of the LHS.

    You should have

    P(k)

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

    P(k+1)

    1+2(2+3+....+k+[k+1])+(k+2)=(k+2)^2-1 ?

    Now find the P(k) expression in that

    \color{blue}1+2(2+3+...+k)\color{black}+2(k+1)\col  or{blue}+(k+1)\color{black}+1=(k+2)^2-1 ?

    Now use your RHS from P(k) to evaluate the LHS in the above line

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

    which is

    (k+2)^2-1

    Hence if P(k) is true, it causes P(k+1) to be true
    Last edited by Archie Meade; May 4th 2010 at 02:27 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof using induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 5th 2009, 08:46 PM
  2. Induction Proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 5th 2009, 02:35 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by induction
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 30th 2008, 06:25 AM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum