Results 1 to 8 of 8

Math Help - induction help

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    induction help

    Hey guys, im really struggling with induction. Question: Use induction to prove that 1 + 7 + 19 +..... + ( 3n^2 - 3n + 1) = n^3 for all positive integers n by completing the following steps:

    a) Show that the statement is true when n=1.

    My answer: Is this just substituting n=1 into 3n^2 - 3n + 1 ? and how do I know its true?

    b) show that, if 1 + 7 + 19 + .... + ( 3k^2 - 3k + 1) = k^3, then 1 + 3 + 5 + ... + ( 3k^2 - 3k + 1) + (3(k + 1)^2 -3(k + 1) +1) = (k+1)^3 .

    my answer: Not sure this one! Any help would be much appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2008
    Posts
    383
    Sorry this is wrong. O.o
    Last edited by BabyMilo; April 19th 2010 at 03:31 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by jvignacio View Post
    Hey guys, im really struggling with induction. Question: Use induction to prove that 1 + 7 + 19 +..... + ( 3n^2 - 3n + 1) = n^3 for all positive integers n by completing the following steps:

    a) Show that the statement is true when n=1.

    My answer: Is this just substituting n=1 into 3n^2 - 3n + 1 ? and how do I know its true?

    Yes, just check that if you set n=1 on both sides of the equality, then they are equal


    n=1, 3(1)(1)-3(1)+1=3-3+1=1
    1=1(1)1...true for n=1


    b) show that, if 1 + 7 + 19 + .... + ( 3k^2 - 3k + 1) = k^3, then 1 + 3 + 5 + ... + ( 3k^2 - 3k + 1) + (3(k + 1)^2 -3(k + 1) +1) = (k+1)^3 .

    my answer: Not sure this one! Any help would be much appreciated.
    Part b) attempts to show that if the statement is true for some n=k,
    then being true for n=k causes the statement to be true for the next n,
    which is n=k+1.

    The purpose of this is to show that...

    true for n=1 causes the equality to be true for n=2,
    true for n=2 causes the equality to be true for n=3,
    true for n=3 causes the equality to be true for n=4....
    all the way to infinity

    then you can see by thinking about it that an infinite chain of cause and effect
    has been set up between adjacent terms.

    Hence we express the k+1 version in terms of the k version
    to see if there is a cause and effect relationship.

    Essentially, this is why part b) is written as it is.

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

    If it is then examining

    1+7+19+...(3k^2-3k+1)+\left[3(k+1)^2-3(k+1)+1\right]

    which is the sum of (k+1) terms,

    and examining if this is (k+1)^3 if the sum of k terms is k^3, we get

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

    =k^3+3k^2+6k+3-3k-3+1=k^3+3k^2+3k+1

    which is (k+1)^3, since

    (k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1) =k^3+k^2+2k^2+2k+k+1=k^3+3k^2+3k+1

    Hence, the equality being true for some term n=k causes the equality to be true for the next term n=k+1.

    Therefore there is an infinite chain of cause and effect.
    If the equality is true for n=1, this causes the equality to be true for all n.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by BabyMilo View Post
    3n^2-3n+1 does not = n^3

    try when n=2 rather than n=1
    you will see LHS=7 while RHS=8

    if you do step two to prove it,
    you will find LHS= k^3+k+1, while RHS= k^3+3k^2+3k+1

    Hope this helps!
    for a) shouldnt it be LHS = 1, RHS = n^3 = 1^3 = 1, therefore true for n=1 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Archie Meade View Post
    Part b) attempts to show that if the statement is true for some n=k,
    then being true for n=k causes the statement to be true for the next n,
    which is n=k+1.

    The purpose of this is to show that...

    true for n=1 causes the equality to be true for n=2,
    true for n=2 causes the equality to be true for n=3,
    true for n=3 causes the equality to be true for n=4....
    all the way to infinity

    then you can see by thinking about it that an infinite chain of cause and effect
    has been set up between adjacent terms.

    Hence we express the k+1 version in terms of the k version
    to see if there is a cause and effect relationship.

    Essentially, this is why part b) is written as it is.

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

    If it is then examining

    1+7+19+...(3k^2-3k+1)+\left[3(k+1)^2-3(k+1)+1\right]

    which is the sum of (k+1) terms,

    and examining if this is (k+1)^3 if the sum of k terms is k^3, we get

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

    =k^3+3k^2+6k+3-3k-3+1=k^3+3k^2+3k+1

    which is (k+1)^3, since

    (k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1) =k^3+k^2+2k^2+2k+k+1=k^3+3k^2+3k+1

    Hence, the equality being true for some term n=k causes the equality to be true for the next term n=k+1.

    Therefore there is an infinite chain of cause and effect.
    If the equality is true for n=1, this causes the equality to be true for all n.

    For a) do I substitute n=1 into n^3 OR 3n^2 - 3n + 1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by jvignacio View Post
    For a) do I substitute n=1 into n^3 OR 3n^2 - 3n + 1
    Hi jvignacio,

    you must substitute n=1 into both

    for it is the same n on both sides.

    You see, all those earlier terms are 3n^2-3n+1

    with n=1, 2, 3 etc

    Hence, putting n=1, we have only the first term (it doesn't add to anything).

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

    3(2)^2-3(2)+1=12-6+1=7

    3(3)^2-3(3)+1=27-9+1=19 etc

    The n^3 is the sum of these

    1=1^3

    1+7=2^3

    1+7+19=3^3 etc
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Archie Meade View Post
    and examining if this is (k+1)^3 if the sum of k terms is k^3, we get

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

    =k^3+3k^2+6k+3-3k-3+1=k^3+3k^2+3k+1

    which is (k+1)^3, since

    (k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1) =k^3+k^2+2k^2+2k+k+1=k^3+3k^2+3k+1

    Hence, the equality being true for some term n=k causes the equality to be true for the next term n=k+1.

    Therefore there is an infinite chain of cause and effect.
    If the equality is true for n=1, this causes the equality to be true for all n.
    Sorry im just abit confused on why you put k^3 on the left hand side to make it all equal (k+1)^3?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by jvignacio View Post
    Sorry im just abit confused on why you put k^3 on the left hand side to make it all equal (k+1)^3?
    The reason is...

    if 1+7+19+....+\left(3k^2-3k+1\right)=k^3

    then the sum of the first k terms is k^3

    This means that the sum of the first (k+1) terms will be (k+1)^3

    if this equality really is true!

    Think about that.

    However, the sum of the first (k+1) terms is the sum of the first k terms plus the (k+1)th term, which is

    k^3+(k+1)th\ term=k^3+\left[3(k+1)^2-3(k+1)+1\right]

    if the sum of the first k terms really is k^3

    You get the (k+1)th term by using k+1 in place of k.

    Then you need to show that when you add the sum of k terms (which is supposed to be k^3) to the (k+1)th term,

    the answer should be (k+1)^3

    If this is the case, then we can say

    sum\ of\ terms=k^3 causes the sum\ of\ k+1\ terms to be (k+1)^3

    All we've done is to show that the formula being true for a particular value of n=k
    will cause the formula to be true for the next value of n=k+1.

    That establishes a chain reaction.
    Then if you test it for n=1, and it's true, then it's true for all natural numbers n.

    Since this may seem long-winded, it's generally not covered in class.

    There are shortcut ways to prove the initial statement,
    such as

    test for n=1
    assume p(k) true.....test p(k+1)

    but it's easier if you understand the process.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum