• Support PF! Buy your school textbooks, materials and every day products Here!

How to show this statement by induction

  • Thread starter Moridin
  • Start date
  • #1
664
3

Homework Statement



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]

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.
 

Answers and Replies

  • #2
210
0
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:
  • #3
tiny-tim
Science Advisor
Homework Helper
25,832
249
Hi Moridin! :smile:

Alternatve proof for second part …

Hint: what is (2k)² - (2k - 1)² ? :smile:
 
  • #4
664
3
Hi Moridin! :smile:

Alternatve proof for second part …

Hint: what is (2k)² - (2k - 1)² ? :smile:
4k - 1?

You lost me.
 
  • #5
210
0
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:
  • #6
Defennder
Homework Helper
2,591
5
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.
 
  • #7
tiny-tim
Science Advisor
Homework Helper
25,832
249
4k - 1?

You lost me.
Hint: split 4k - 1 into two parts. :smile:
 
  • #8
664
3
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.
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.
 
  • #9
tiny-tim
Science Advisor
Homework Helper
25,832
249
Hint: split 4k - 1 into two parts. :smile:
Hint: 4k - 1 = 2k + (2k - 1).

So ∑(4k - 1) over even k = … ? :smile:
 
  • #10
664
3
Hint: 4k - 1 = 2k + (2k - 1).

So ∑(4k - 1) over even k = … ? :smile:
7 + 15 + 23 + ... + ?

:confused:
 
  • #11
tiny-tim
Science Advisor
Homework Helper
25,832
249
7 + 15 + 23 + ... + ?

:confused:
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:
 
  • #12
210
0
[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.
[tex] - \frac{p(p+1)}{2} \ + \ (-1)^{2(p+1)} (p+1)^2 \neq - \frac{p(p+1)}{2} \ - \ (p+1)^2[/tex]
 
  • #13
664
3
[tex] - \frac{p(p+1)}{2} \ + \ (-1)^{2(p+1)} (p+1)^2 \neq - \frac{p(p+1)}{2} \ - \ (p+1)^2[/tex]
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?
 
  • #14
210
0
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?
indeed :smile:
 
  • #15
664
3
Thank you all so much for your time and help! :smile:
 

Related Threads for: How to show this statement by induction

  • Last Post
Replies
1
Views
1K
Replies
1
Views
2K
Replies
8
Views
986
Replies
3
Views
1K
Replies
11
Views
1K
Replies
4
Views
5K
Top