Page 1 of 2 12 LastLast
Results 1 to 10 of 15

Thread: Induction proof: 1^3+2^3+...+n^3=(1+2+3+...+n)^2

  1. #1
    Junior Member
    Join Date
    May 2018
    Posts
    39

    Induction proof: 1^3+2^3+...+n^3=(1+2+3+...+n)^2

    Hi. if you find any fault in this proof please let me know since I couldn't find an answer on the back of my math book.

    Prove that

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

    Statement

    Let [tex]P(n)[/tex] be the statement [tex]\displaystyle\sum_{i=0}^{n} i^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2[/tex]

    The sum of the first [tex]n[/tex] positive integers is [tex]\frac{n(n+1)}{2}[/tex] which is a theorem refered to as 1-1.

    We can rewrite the statement [tex]P(n)[/tex] based on theorem 1-1 as [tex]\displaystyle\sum_{i=0}^{n} i^3 = (\frac{n(n+1)}{2})^2[/tex].

    Now we will show that [tex]P(n)[/tex] is true for all integers [tex]n \geq 0[/tex]

    Base case

    [tex]P(0)[/tex] is the statement [tex]\displaystyle\sum_{i=0}^{0} i^3 = (\frac{0(0+1)}{2})^2= 0[/tex] which is clearly true.


    The induction step

    Let [tex]k \geq 0[/tex] be an integer. Assume (for induction) that [tex]P(k)[/tex] is true. That means [tex]\displaystyle\sum_{i=0}^{k} i^3[/tex] [tex]\stackrel{?}{=}[/tex][tex](\frac{k(k+1)}{2})^2[/tex], is true for [tex]n=k[/tex].

    We will prove that [tex]P(k+1)[/tex] is true as well. That is, we must prove that [tex]\displaystyle\sum_{i=0}^{k} i^3 + (k+1)^3= (\frac{(k+1)((k+1)+1)}{2})^2[/tex]. To prove this equation, start by adding [tex](k+1)^3[/tex]
    to both sides of the inductive hypothesis:

    [tex]\displaystyle\sum_{i=0}^{k+1} i^3= (\frac{k(k+1)}{2})^2 + (k+1)^3[/tex]. Now, simplifying the right side we get:

    [tex]=\frac{k^2((k+1)^2)}{4} + (k+1)^3 = \frac{k^2(k+1^2) +(4k+4)(k+1)^2}{4} = \frac{(k+2)^2(k+1)^2}{2^2} = (\frac{((k+2)(k+1)=}{2})^2 = (\frac{(k+1)((k+1)+1)}{2})^2 [/tex]

    Thus [tex]P(k+1)[/tex] is true, so by the principle of mathematical induction [tex]P(n)[/tex] is true for all integers [tex]n \geq 0[/tex]

    Q.E.D.



    Last edited by Aion; 06-10-2018 at 08:42 AM.

  2. #2
    Senior Member
    Join Date
    Nov 2017
    Location
    Rochester, NY
    Posts
    2,194
    Quote Originally Posted by Aion View Post
    Hi. if you find any fault in this proof please let me know since I couldn't find an answer on the back of my math book.

    Prove that

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

    Statement

    [tex]\displaystyle\sum_{i=0}^{n} x^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2[/tex]

    By using theorem 1-1: The sum of the first n positive integers is [tex]\frac{n(n+1)}{2}[/tex]

    We can rewrite the statement as [tex]\displaystyle\sum_{i=0}^{n} x^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2=(\frac{n(n+1)}{2})^2[/tex]

    Show true for [tex]n=1[/tex]

    [tex]\displaystyle\sum_{i=0}^{1} x^3 = 0^3 + 1^3 = 1[/tex] and [tex]1^2 = 1[/tex]

    LHS(Left-hand side) = RHS(Right-hand side), therefore, the statement is true for [tex]n = 1[/tex]

    The induction hypothesis

    [tex]\displaystyle\sum_{i=0}^{k+1} x^3[/tex] [tex]\stackrel{?}{=}[/tex] is true for some value of [tex]k≥n[/tex], hence [tex]k≥1[/tex].

    The induction step

    We must show that the statement is true for some value of [tex]n = k +1[/tex], such that it will also be true for the next value of [tex]n[/tex].


    Assuming that [tex]\displaystyle\sum_{i=0}^{k} x^3=(\frac{k(k+1)}{2})^2[/tex], we find that

    [tex]\displaystyle\sum_{i=0}^{k+1} x^3= \displaystyle\sum_{i=0}^{k} x^3 + (k+1)^3 = (\frac{k(k+1)}{2})^2 + (k+1)^3= [/tex]

    [tex]\frac{k^2((k+1)^2)}{4} + (k+1)^2 = \frac{k^2(k+1^2) +(4k+4)(k+1)^2}{4} = \frac{(k+2)^2(k+1)^2}{2^2} = (\frac{(k+2)(k+1)}{2})^2 = (\frac{(k+1)((k+1)+1)}{2})^2) [/tex]

    The last equation is the same equation as [tex](\frac{n(n+1)}{2})^2[/tex] which is based on Theorem1-1, except that n is replaced by (k+1). Hence whenever it is true for all the integers 1,2,...,k, then it is true for the integer k+1.
    The ideas are fine; but you have not written what you meant in some places.

    First, you keep writing [tex]\displaystyle\sum_{i=0}^{n} x^3[/tex]. But that means [tex]\displaystyle\sum_{i=0}^{n} x^3 =x^3 + x^3 + ... + x^3[/tex] ! Presumably you meant to write [tex]\displaystyle\sum_{i=0}^{n} i^3 = 0^3 + 1^3 + 2^3 + ... + n^3[/tex].

    The base case really should be n = 0, not n = 1, the way you've written the sum; you didn't state the conditions on n for the theorem, so if it starts at n = 1, you really should have written [tex]\displaystyle\sum_{i=1}^{n} i^3 = 1^3 + 2^3 + ... + n^3[/tex].

    Where you say you are stating the induction hypothesis, you are not really stating anything (an equal sign with a question mark doesn't assert anything). But the second line under "The Induction Step" is the induction hypothesis.

    I could quibble about other parts of the wording, but I don't want to go too far. The important thing is that you got the math right; it's just the symbols and the words that need improvement ...

  3. #3
    Senior Member
    Join Date
    Dec 2014
    Posts
    2,221
    Quote Originally Posted by Aion View Post
    Hi. if you find any fault in this proof please let me know since I couldn't find an answer on the back of my math book.

    Prove that

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

    Statement

    [tex]\displaystyle\sum_{i=0}^{n} x^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2[/tex]

    By using theorem 1-1: (we don't know what Theorem 1-1 is)The sum of the first n positive integers is [tex]\frac{n(n+1)}{2}[/tex]

    We can rewrite the statement as [tex]\displaystyle\sum_{i=0}^{n} x^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2=(\frac{n(n+1)}{2})^2[/tex]

    Show true for [tex]n=1[/tex]

    [tex]\displaystyle\sum_{i=0}^{1} x^3 = 0^3 + 1^3 = 1[/tex] and [tex]1^2 = 1[/tex]

    LHS(Left-hand side) = RHS(Right-hand side), therefore, the statement is true for [tex]n = 1[/tex]

    The induction hypothesis

    [tex]\displaystyle\sum_{i=0}^{k+1} x^3[/tex] [tex]\stackrel{?}{=}[/tex] is true for some value of [tex]k≥n[/tex], hence [tex]k≥1[/tex].(I would write true for n=k)

    The induction step

    We must show that the statement is true for some value of [tex]n = k +1[/tex], such that it will also be true for the next value of [tex]n[/tex].(not very clear)


    Assuming that [tex]\displaystyle\sum_{i=0}^{k} x^3=(\frac{k(k+1)}{2})^2[/tex], we find that

    [tex]\displaystyle\sum_{i=0}^{k+1} x^3= \displaystyle\sum_{i=0}^{k} x^3 + (k+1)^3 = (\frac{k(k+1)}{2})^2 + (k+1)^3= [/tex]

    [tex]\frac{k^2((k+1)^2)}{4} + (k+1)^2 = \frac{k^2(k+1^2) +(4k+4)(k+1)^2}{4} = \frac{(k+2)^2(k+1)^2}{2^2} = (\frac{(k+2)(k+1)}{2})^2 = (\frac{(k+1)((k+1)+1)}{2})^2) [/tex]

    The last equation is the same equation as [tex](\frac{n(n+1)}{2})^2[/tex] which is based on Theorem1-1, except that n is replaced by (k+1). Hence whenever it is true for all the integers 1,2,...,k, then it is true for the integer k+1.


    Very nicely done for a high school student or anyone beginning to do proofs. I did find some errors that are in red above many of which have been already pointed out to you. All in all this is very good.
    A mathematician is a blind man in a dark room looking for a black cat which isnít there. - Charles R. Darwin

  4. #4
    Senior Member
    Join Date
    Nov 2017
    Location
    Rochester, NY
    Posts
    2,194
    I'd noticed the wrong exponent, too, but forgot to mention it, as it was clearly just a typo.

    What I suggest you do is try fixing the errors and improving the wording (perhaps looking at models you were given), and then we can help you finalize it. Some of the wording improvements you need are rather important in the long run, so I do hope we can get to those.

  5. #5
    Junior Member
    Join Date
    May 2018
    Posts
    39
    Quote Originally Posted by Jomo View Post
    ...
    Quote Originally Posted by Dr.Peterson View Post
    I'd noticed the wrong exponent, too, but forgot to mention it, as it was clearly just a typo.

    What I suggest you do is try fixing the errors and improving the wording (perhaps looking at models you were given), and then we can help you finalize it. Some of the wording improvements you need are rather important in the long run, so I do hope we can get to those.
    Ok, so I've tried to make some changes to the proof. Please let me know if you think that I've made some improvements to the wording. Thanks for the help!
    Last edited by Aion; 06-10-2018 at 08:49 AM.

  6. #6
    Senior Member
    Join Date
    Nov 2017
    Location
    Rochester, NY
    Posts
    2,194
    Quote Originally Posted by Aion View Post
    Ok, so I've tried to make some changes to the proof. Please let me know if you think that I've made some improvements to the wording. Thanks for the help!
    I assume you are planning to post the new proof?

  7. #7
    Junior Member
    Join Date
    May 2018
    Posts
    39
    Quote Originally Posted by Dr.Peterson View Post
    I assume you are planning to post the new proof?
    No. I just made changes to the proof posted above based on your feedback.

  8. #8
    Senior Member
    Join Date
    Nov 2017
    Location
    Rochester, NY
    Posts
    2,194
    Quote Originally Posted by Aion View Post
    No. I just made changes to the proof posted above based on your feedback.
    Oh. In my opinion, that is bad form, because it hides the history of the discussion, and people like me don't expect to have to look back there.


    Quote Originally Posted by Aion View Post
    Hi. if you find any fault in this proof please let me know since I couldn't find an answer on the back of my math book.

    Prove that

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

    Statement

    Let [tex]P(n)[/tex] be the statement [tex]\displaystyle\sum_{i=0}^{n} i^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2[/tex]

    The sum of the first [tex]n[/tex] positive integers is [tex]\frac{n(n+1)}{2}[/tex] which is a theorem refered to as 1-1.

    We can rewrite the statement [tex]P(n)[/tex] based on theorem 1-1 as [tex]\displaystyle\sum_{i=0}^{n} i^3 = (\frac{n(n+1)}{2})^2[/tex].

    Now we will show that [tex]P(n)[/tex] is true for all integers [tex]n \geq 0[/tex]

    Base case

    [tex]P(0)[/tex] is the statement [tex]\displaystyle\sum_{i=0}^{0} i^3 = (\frac{0(0+1)}{2})^2= 0[/tex] which is clearly true.


    The induction step

    Let [tex]k \geq 0[/tex] be an integer. Assume (for induction) that [tex]P(k)[/tex] is true. That means [tex]\displaystyle\sum_{i=0}^{k} i^3[/tex] [tex]\stackrel{?}{=}[/tex][tex](\frac{k(k+1)}{2})^2[/tex], is true for [tex]n=k[/tex].

    We will prove that [tex]P(k+1)[/tex] is true as well. That is, we must prove that [tex]\displaystyle\sum_{i=0}^{k} i^3 + (k+1)^3= (\frac{(k+1)((k+1)+1)}{2})^2[/tex]. To prove this equation, start by adding [tex](k+1)^3[/tex]
    to both sides of the inductive hypothesis:

    [tex]\displaystyle\sum_{i=0}^{k+1} i^3= (\frac{k(k+1)}{2})^2 + (k+1)^3[/tex]. Now, simplifying the right side we get:

    [tex]=\frac{k^2((k+1)^2)}{4} + (k+1)^3 = \frac{k^2(k+1^2) +(4k+4)(k+1)^2}{4} = \frac{(k+2)^2(k+1)^2}{2^2} = (\frac{((k+2)(k+1)=}{2})^2 = (\frac{(k+1)((k+1)+1)}{2})^2 [/tex]

    Thus [tex]P(k+1)[/tex] is true, so by the principle of mathematical induction [tex]P(n)[/tex] is true for all integers [tex]n \geq 0[/tex]

    Q.E.D.
    I'll just make every comment I can, some of which will be utterly trivial!

    You didn't correct the statement of the theorem itself to say "for all positive integers n", which is required. Later you allow n to be zero; that is not necessary for the theorem as presumably intended. What was the exact wording of the problem as written?

    You still show i starting at 0 rather than 1. This has no effect on the truth of what you say, but is technically a different sum than what was shown in the theorem, and could lead to errors in other problems. But if the theorem was for n >= 0, then all this is correct.

    For our purposes it is not necessary to name theorem 1-1 (though as an answer in your class, what you originally wrote was fine). We just need to know it was previously proved.

    You don't need the question mark on the equal sign in the induction hypothesis, as that is used to say that something is not known to be true, and here it is being assumed.

    I would change the line

    That is, we must prove that [tex]\displaystyle\sum_{i=0}^{k} i^3 + (k+1)^3= (\frac{(k+1)((k+1)+1)}{2})^2[/tex].

    to

    That is, we must prove that [tex]\displaystyle\sum_{i=0}^{k+1} i^3 = (\frac{(k+1)((k+1)+1)}{2})^2[/tex].

    The left side as you wrote it would be better left to the next line.

    I can't find anything more to comment on beyond these quibbles. Excellent work!

  9. #9
    Senior Member
    Join Date
    Dec 2014
    Posts
    2,221
    Quote Originally Posted by Aion View Post
    Hi. if you find any fault in this proof please let me know since I couldn't find an answer on the back of my math book.

    Prove that

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

    Statement

    Let [tex]P(n)[/tex] be the statement [tex]\displaystyle\sum_{i=0}^{n} i^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2[/tex]

    The sum of the first [tex]n[/tex] positive integers is [tex]\frac{n(n+1)}{2}[/tex] which is a theorem refered to as 1-1.

    We can rewrite the statement [tex]P(n)[/tex] based on theorem 1-1 as [tex]\displaystyle\sum_{i=0}^{n} i^3 = (\frac{n(n+1)}{2})^2[/tex].

    Now we will show that [tex]P(n)[/tex] is true for all integers [tex]n \geq 0[/tex]

    Base case

    [tex]P(0)[/tex] is the statement [tex]\displaystyle\sum_{i=0}^{0} i^3 = (\frac{0(0+1)}{2})^2= 0[/tex] which is clearly true.


    The induction step

    Let [tex]k \geq 0[/tex] be an integer. Assume (for induction) that [tex]P(k)[/tex] is true. That means [tex]\displaystyle\sum_{i=0}^{k} i^3[/tex] [tex]\stackrel{?}{=}[/tex][tex](\frac{k(k+1)}{2})^2[/tex], is true for [tex]n=k[/tex].

    We will prove that [tex]P(k+1)[/tex] is true as well. That is, we must prove that [tex]\displaystyle\sum_{i=0}^{k} i^3 + (k+1)^3= (\frac{(k+1)((k+1)+1)}{2})^2[/tex]. To prove this equation, start by adding [tex](k+1)^3[/tex]
    to both sides of the inductive hypothesis:

    [tex]\displaystyle\sum_{i=0}^{k+1} i^3= (\frac{k(k+1)}{2})^2 + (k+1)^3[/tex]. Now, simplifying the right side we get:

    [tex]=\frac{k^2((k+1)^2)}{4} + (k+1)^3 = \frac{k^2(k+1^2) +(4k+4)(k+1)^2}{4} = \frac{(k+2)^2(k+1)^2}{2^2} = (\frac{((k+2)(k+1)=}{2})^2 = (\frac{(k+1)((k+1)+1)}{2})^2 [/tex]

    Thus [tex]P(k+1)[/tex] is true, so by the principle of mathematical induction [tex]P(n)[/tex] is true for all integers [tex]n \geq 0[/tex]

    Q.E.D.



    You are getting there. Do not expect your proof to be perfect initially. A few years from now you will look back on your proofs and will see immediate improvements.

    if you find any fault in this proof please let me know since I couldn't find an answer on the back of my math book. Since there is no one way to do a proof, the solution in the back of the book will not be unique. At some point you need to develop your own style of writing a proof.
    A mathematician is a blind man in a dark room looking for a black cat which isnít there. - Charles R. Darwin

  10. #10
    Junior Member
    Join Date
    May 2018
    Posts
    39
    Prove that:


    [tex]1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2[/tex]. By using the following theorem: The sum of the first [tex]n[/tex] positive integers is [tex]\frac{n(n+1)}{2}[/tex] for [tex]n \geq 1[/tex]


    Statement


    Let [tex]P(n)[/tex] be the statement [tex]\displaystyle\sum_{i=1}^{n} i^3 =1^3 + 2^3 + ... + n^3 = (1+2+3+...+n)^2[/tex]


    We can rewrite the statement [tex]P(n)[/tex] as [tex]\displaystyle\sum_{i=1}^{n} i^3 = (\frac{n(n+1)}{2})^2[/tex].


    I intend to prove that [tex]P(n)[/tex] is true for all integers [tex]n \geq 1[/tex]


    Base case


    [tex]P(0)[/tex] is the statement [tex]\displaystyle\sum_{i=1}^{0} i^3 = 0[/tex] which is clearly true.


    The induction step


    Let [tex]k \geq 0[/tex] be an integer. Assume (for induction) that [tex]P(k)[/tex] is true. That means


    [tex]\displaystyle\sum_{i=1}^{k} i^3=(\frac{k(k+1)}{2})^2[/tex], is true for [tex]n=k[/tex].


    Now we will prove that [tex]P(k+1)[/tex] is true as well.


    That is, we must prove that [tex]\displaystyle\sum_{i=1}^{k+1} i^3 = (\frac{(k+1)((k+1)+1)}{2})^2[/tex].


    To prove this equation, start by adding [tex](k+1)^3[/tex]to both sides of the inductive hypothesis:


    [tex]\displaystyle\sum_{i=1}^{k} i^3 + (k+1)^3 = (\frac{k(k+1)}{2})^2 + (k+1)^3[/tex] By simplifying the right side we get:


    [tex]\frac{k^2((k+1)^2)}{4} + (k+1)^3 = \frac{k^2(k+1^2) +(4k+4)(k+1)^2}{4} = \frac{(k+2)^2(k+1)^2}{2^2} = (\frac{((k+2)(k+1)}{2})^2 = (\frac{(k+1)((k+1)+1)}{2})^2 [/tex]


    Thus [tex]P(k+1)[/tex] is true, so by the principle of mathematical induction [tex]P(n)[/tex] is true for all integers [tex]n \geq 1[/tex]


    Q.E.D.


    There are fewer errors now entirely thanks to Dr.Peterson and Jomo. Thank's for the help!
    Last edited by Aion; 06-11-2018 at 04:19 PM.

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •