How to show this statement by induction

  • Thread starter Moridin
  • Start date
  • Tags
    Induction
but i think you should have started with\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 = - \frac{n(n+1)}{2} \ + \ (-1)^{2(n+1)} (n+1)^2 = - \frac{n(n+1)}{2} \ + \ (n+1)^2 = (n+1)(n+2) = \frac{(n+1)(n+2)2}{2} -
  • #1
692
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.
 
Physics news on Phys.org
  • #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:
  • #3
Hi Moridin! :smile:

Alternatve proof for second part …

Hint: what is (2k)² - (2k - 1)² ? :smile:
 
  • #4
tiny-tim said:
Hi Moridin! :smile:

Alternatve proof for second part …

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

4k - 1?

You lost me.
 
  • #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:
  • #6
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 accommodate the last summand which must be positive.
 
  • #7
Moridin said:
4k - 1?

You lost me.

Hint: split 4k - 1 into two parts. :smile:
 
  • #8
Defennder said:
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 accommodate 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 said:
Hint: split 4k - 1 into two parts. :smile:

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

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

So ∑(4k - 1) over even k = … ? :smile:

7 + 15 + 23 + ... + ?

:confused:
 
  • #11
Moridin said:
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
Moridin said:
[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
GregA said:
[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
Moridin said:
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
Thank you all so much for your time and help! :smile:
 

1. How does induction work?

Induction is a mathematical proof technique used to prove that a statement is true for all natural numbers. It involves proving the statement is true for a base case, typically n=1, and then showing that if the statement is true for some natural number k, it must also be true for k+1.

2. What is the purpose of using induction?

The purpose of using induction is to prove that a statement is true for all natural numbers, without having to explicitly check each individual number. It allows us to show that a pattern or property holds true for all cases, by proving it for just a few specific cases.

3. How do you choose a base case for an induction proof?

The base case for an induction proof is typically chosen as the smallest natural number that the statement is meant to be true for. This is usually n=1, but it could also be 0 or any other number, depending on the statement being proved.

4. Can you use induction to prove any statement?

No, induction can only be used to prove statements that are true for all natural numbers. It cannot be used to prove statements about real numbers, for example, as there are infinitely many real numbers and it would be impossible to check them all.

5. How do you know when to use induction in a proof?

Induction is typically used when trying to prove statements about natural numbers, such as properties of sequences, series, or recursive definitions. It is also useful for proving statements about combinatorics and discrete mathematics.

Suggested for: How to show this statement by induction

Replies
5
Views
861
Replies
14
Views
921
Replies
13
Views
1K
Replies
12
Views
1K
Replies
3
Views
714
Replies
5
Views
507
Replies
9
Views
869
Back
Top