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!

How to show this statement by induction

  1. Jun 4, 2008 #1
    1. The problem statement, all variables and given/known data

    Show that

    [tex]\forall n \in \mathbb{N}:~ \sum_{k=1}^{n} k = \frac{n(n+1)}{2} = \sum_{k=0}^{n} (-1)^{n+k} k^{2}[/tex]

    3. The attempt at a solution

    I tried to apply the general method of proof by induction.

    (1) Show that it is true for n = 1

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

    (2) Show that if it is true for n = p, it is true for n = p + 1

    Assume that

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

    Now,

    [tex]\sum_{k=1}^{p} k = 1 + 2 + 3 + ... + p[/tex]

    [tex]\sum_{k=1}^{p+1} k = 1 + 2 + 3+ ... + p + (p +1) = \sum_{k=1}^{p} k + (p+1)[/tex]

    According to our assumption, it follows that

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

    If it can be show that

    [tex]\frac{p(p+1)}{2} + (p + 1) = \frac{(p+1)(p+2)}{2}[/tex]

    then the first equality is taken care of satisfactory. A trivial calculation shows that this is indeed the case.

    For the second equality, the assumption is that

    [tex]\sum_{k=0}^{p} (-1)^{p+k} k^{2} = \frac{p(p+1)}{2}[/tex]

    Here is it where it gets a bit tricky for me.

    Now,

    [tex]\sum_{k=0}^{p} (-1)^{p+k} k^{2} = (-1)^{p+1} + (-1)^{p+1} \cdot 4 + (-1)^{p+2} \cdot 8 + ... + (-1)^{2p} \cdot p^{2}[/tex]

    [tex]\sum_{k=0}^{p+1} (-1)^{p+k} k^{2} = (-1)^{p+1} + (-1)^{p+1} \cdot 4 + (-1)^{p+2} \cdot 8 + ... + (-1)^{2p} \cdot p^{2} + (-1)^{2p+2} \cdot (p+1)^{2} = \sum_{k=0}^{p} (-1)^{p+k} k^{2} + (-1)^{2p+2} \cdot (p+1)^{2}[/tex]

    Given our assumption, we get

    [tex]\sum_{k=0}^{p} (-1)^{p+k} k^{2} + (-1)^{2p+2} \cdot (p+1)^{2} = \frac{p(p+1)}{2} + (-1)^{2p+2} \cdot (p+1)^{2}[/tex]

    So if it can be shown that

    [tex]\frac{p(p+1)}{2} + (-1)^{2p+2} \cdot (p+1)^{2} = \frac{(p+1)(p+1)}{2}[/tex]

    then the second inequality is also taken care of satisfactory and part (2) is done.

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

    But this does not equal [tex]\frac{(p+1)(p+1)}{2}[/tex], so I must have made one or more mistakes somewhere, but I am at a loss as to where it is.
     
  2. jcsd
  3. Jun 4, 2008 #2
    when you split the sum [tex]\sum_{k=0}^{p+1}(-1)^{k+1+p}k^{2}[/tex] you should find you can get [tex]-(\sum_{k=0}^{p}k) + (-1)^{2p +2}(p+1)^2
     
    Last edited: Jun 5, 2008
  4. Jun 5, 2008 #3

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Moridin! :smile:

    Alternatve proof for second part …

    Hint: what is (2k)² - (2k - 1)² ? :smile:
     
  5. Jun 5, 2008 #4
    4k - 1?

    You lost me.
     
  6. Jun 6, 2008 #5
    Sorry about my last advice...I didn't identify exactly where you had gone wrong.

    Your mistake stems from this line:
    [tex]\sum_{k=0}^{p+1} (-1)^{p+k} k^{2} = (-1)^{p+1} + (-1)^{p+1} \cdot 4 + (-1)^{p+2} \cdot 8 + ... + (-1)^{2p} \cdot p^{2} + (-1)^{2p+2} \cdot (p+1)^{2} = \sum_{k=0}^{p} (-1)^{p+k} k^{2} + (-1)^{2p+2} \cdot (p+1)^{2}[/tex]

    you should be starting with [tex]\sum_{k=0}^{p+1} (-1)^{p+1+k} k^{2} =...[/tex] not [tex]\sum_{k=0}^{p+1} (-1)^{p+k} k^{2} = ...[/tex]
     
    Last edited: Jun 6, 2008
  7. Jun 6, 2008 #6

    Defennder

    User Avatar
    Homework Helper

    Can you show that [tex]\sum^{n+1}_{k=0} (-1)^{n+k+1}k^2 = -\sum^{n}_{k=0} (-1)^{n+k} k^2 \ + \ (-1)^{2(n+1)} (n+1)^2 [/tex]?

    Note that the last term of the summation is always positive, and given that the terms alternate between positive and negative, this amounts to multiplying the entire summation by -1 to "shift" the summation backwards by one index to accomodate the last summand which must be positive.
     
  8. Jun 6, 2008 #7

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hint: split 4k - 1 into two parts. :smile:
     
  9. Jun 8, 2008 #8
    I understand that equality now, since the multiplier of negative one shifts the exponents one step back according the the power laws. Here is what I got so far.

    [tex]\sum^{p+1}_{k=0} (-1)^{p+k+1}k^2 = -\sum^{p}_{k=0} (-1)^{p+k} k^2 \ + \ (-1)^{2(p+1)} (p+1)^2 = - \frac{p(p+1)}{2} \ + \ (-1)^{2(p+1)} (p+1)^2[/tex]

    However,

    [tex]- \frac{p(p+1)}{2} \ + \ (-1)^{2(p+1)} (p+1)^2 = - \frac{p(p+1)}{2} \ - \ (p+1)^2 = \frac{-(p^{2} + p) - 2(p^{2} +2p +1)}{2} = \frac{-p^{2} - p - 2p^{2} - 2p - 1}{2}[/tex]

    I seem to have made a sign error, because if the last three subtractions where additions, I would be home free.
     
  10. Jun 8, 2008 #9

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hint: 4k - 1 = 2k + (2k - 1).

    So ∑(4k - 1) over even k = … ? :smile:
     
  11. Jun 8, 2008 #10
    7 + 15 + 23 + ... + ?

    :confused:
     
  12. Jun 8, 2008 #11

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Well, yes, but we're trying to avoid summing that, since it's too difficult.

    It equals ∑2k + ∑(2k - 1) over even k, which we can express as a sum over all k, as … ? :smile:
     
  13. Jun 8, 2008 #12
    [tex] - \frac{p(p+1)}{2} \ + \ (-1)^{2(p+1)} (p+1)^2 \neq - \frac{p(p+1)}{2} \ - \ (p+1)^2[/tex]
     
  14. Jun 8, 2008 #13
    I thought I made a mistake around there. Oh right, it is 2m + 1 that gives an odd exponent, but 2m+ 2 gives an even exponent for all positive m? So it should actually be

    [tex] - \frac{p(p+1)}{2} \ + \ (-1)^{2(p+1)} (p+1)^2 = - \frac{p(p+1)}{2} \ + \ (p+1)^2[/tex]

    That simplifies to what we're looking for namely

    [tex]\frac {(p+1)(p+2)}{2}[/tex]

    Then it just a matter of applying the axiom of induction right?
     
  15. Jun 8, 2008 #14
    indeed :smile:
     
  16. Jun 8, 2008 #15
    Thank you all so much for your time and help! :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?