1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I can do algebra, but I can't prove this properly (and formally)

  1. Sep 14, 2011 #1
    1. The problem statement, all variables and given/known data

    Prove that for every integer [tex]n\geq1[/tex], that

    [tex]1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}[/tex]


    2. The attempt at a solution

    Note that everything after this sentence are what I am going to write in my assignment to hand in.

    (1) Base Case

    [tex]S(n) : \frac{n(n + 1)(2n + 1)}{6}[/tex]

    Assume it is true for n = 1

    [tex]S(1) : \frac{1(1 + 1)(2 + 1)}{6} = 1 = 1^2[/tex]

    Which is true

    (2) Inductive Step, let n = k + 1, then

    [tex]S(k + 1) : \frac{(k + 1)(k + 2)(2k + 3)}{6}[/tex]

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

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

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

    Therefore by Principles of Mathematical Induction, [tex]1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}[/tex] is true for all integers [tex]n\geq1[/tex]

    Q.E.D

    Questions

    a) Is it okay to say "all" instead of "every"?

    b) Yeah I will try to line it up in my real assignment, but I couldn't figure out how to do it here.

    c) DO I have to put that Q.E.D thing to look smart?

    d) Did I do it correctly or did I totally embarrassed myself
     
  2. jcsd
  3. Sep 14, 2011 #2
    Ideally you would want to clearly exhibit that your S(k+1) does indeed have the same form as S(k). So I would add at your very end that

    Thus if S(k)=k(k+1)(2k+1)/6, then we also have S(k+1)=(k+1)[(k+1)+1][2(k+1)+1]/6. So by induction the statement is true.
     
  4. Sep 15, 2011 #3

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    (c): If your professor wants you to use "Q.E.D.", then use it. I've also seen lowercase q.e.d., as well as QED and qed. Also symbols: □ or ■ . What really makes you look smart is a solid proof.


    (d): In general the proof looks pretty good, particularly if you're fairly new to doing proofs.

    For the inductive step:
    Make it clear that you are assuming that your expression is true for n = k and from that you are showing that it's true for n = k+1.

    In the problem you posted here, I would write something like:
    Inductive Step: Assuming that, [itex]\displaystyle S(k)=\frac{k(k + 1)(2k + 1)}{6}\,,[/itex] show that [itex]\displaystyle S(k+1)=\frac{(k+1)(k + 2)(2k + 3)}{6}\,.[/itex]

    Proof:
    [itex]\displaystyle S(k+1)=S(k)+(k+1)^2[/itex]

    [itex]\displaystyle =\frac{k(k + 1)(2k + 1)}{6}+(k+1)^2[/itex]
    ...

    [itex]\displaystyle =\frac{(k+1)(k + 2)(2k + 3)}{6}\,.[/itex]

    ...​

    Many, if not most, students have trouble with inductive proofs. They tend to assume the thing that they should be proving. You have done a good job avoiding that here.
     
  5. Sep 15, 2011 #4

    Mark44

    Staff: Mentor

    Here Sammy is telling you the same thing I said earlier and in another thread.
     
  6. Sep 15, 2011 #5
    1) Base Case

    [tex]S(n) : \frac{n(n + 1)(2n + 1)}{6}[/tex]

    Let n =1

    [tex]S(1) : \frac{1(1 + 1)(2 + 1)}{6} = 1 = 1^2[/tex]

    Which is true

    (2) Inductive Step,

    Assume that [tex]S(n) : \frac{n(n + 1)(2n + 1)}{6}[/tex] is true, then let n = k + 1 [This is my inductive hypothesis?]

    [tex]S(k + 1) : \frac{(k + 1)(k + 2)(2k + 3)}{6}[/tex]

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

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

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

    Therefore by Principles of Mathematical Induction, [tex]1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}[/tex] is true for all integers [tex]n\geq1[/tex]

    Q.E.D
     
  7. Sep 16, 2011 #6
    Your induction hypothesis is what you assume (after all hypothesis means some sort of guess), i.e. your assumption that S(k)=k(k+1)(2k+1)/6.

    So to prove a statement on S(n), you need to

    1. Establish the base case, i.e. check S(1).
    2. Assume S(k) is true. This is your induction hypothesis.
    3. Show that if S(k) is true, then S(k+1) is true.
     
  8. Sep 18, 2011 #7
    Guys for my inductive hypothesis, do I need to state that [tex]n \in \mathbb{Z}[/tex] and [tex]n \geq 0[/tex]
     
  9. Sep 18, 2011 #8
    n is really just a natural number. instead of worrying about writing n is an element of z greater than or equal to 1, just say it's a natural number.

    When you write the beginning part, you should put what S(n) is, 1^2 + 2^2 + 3^2.. n^2
    e.g say
    Prove that [itex] 1^2 + 2^2 + 3^2.. n^2 = \frac{n(n + 1)(2n + 1)}{6} [/itex]

    Then you show it for n=1, like you did.

    Now, change your n's to k's. You need to write:
    Assume it is true for n=k, that is, assume [itex] 1^2 + 2^2 + 3^2.. k^2 = \frac{k(k + 1)(2k + 1)}{6} [/itex]

    Then, for k+1, [itex] 1^2 + 2^2 + 3^2.. (k+1)^2 = \frac{(k+1)(k + 2)(2(k+1) + 1)}{6} [/itex]

    Then show it like you did.

    I like the QED. My prof used to always write, Therefore, by the PMI, the proof is over.

    QED sounds better than "the proof is over" in my opinion.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: I can do algebra, but I can't prove this properly (and formally)
  1. How Can I prove this? (Replies: 3)

  2. Can I prove this? (Replies: 15)

Loading...