A summation problem

[Klaynos]

OK this has been annoying me, I'm sure it's relatively simple and I'm just missing something... like the power of thought...

 

show that:

 

[math]

 

\sum_{l=0}^{n-1}(2l+1)=n^2

[/math]

[In My Memory]

OK this has been annoying me, I'm sure it's relatively simple and I'm just missing something... like the power of thought...

 

show that:

 

[math]

 

\sum_{l=0}^{n-1}(2l+1)=n^2

[/math]

 

(I'm substituting an x because 1 and l are hard to distinguish from one another)

 

n-1
__
\     (2x + 1)
/_
x = 0

 

The first term = 1, so we'll just rewrite that equation like this:

 

        n-1
        __
1   +    \  (2x + 1)
        /_
        x=1

Now lets just split our summation into two parts, basically so we have this:

 

 

        n-1                  n-1
        __                   __
1   +    \  (2x)     +        \   1
        /_                   /_
        x=1                  x=1

Solving this is really easy now, the last summation is just a constant, so we get:

 

 

                 n-1
                 __
1  + (n-1)   + 2* \   x
                 /_
                 x=1

 

Rewrite that summation in two parts: a simple summation identity minus the last term of that identity:

 

                 [  n
                 [ __
1  + (n-1)   + 2* [ \   (x)      - (n)
                 [ /_
                 [ x=1

 

w00t! Solvable now:

     n      + 2* [n(n+1)/2      - (n)]

=
     n      +    (n(n+1)        - 2n)
=
     n      +    n^2 + n        - 2n
=
                 n^2

 

Therefore:

n-1
__
\     (2x + 1)     =   n^2
/_
x = 0

[Dave]

OK this has been annoying me, I'm sure it's relatively simple and I'm just missing something... like the power of thought...

 

show that:

 

[math]

 

\sum_{l=0}^{n-1}(2l+1)=n^2

[/math]

 

Okay, first split the sum up:

 

[math]\sum_{l=0}^{n-1} (2l+1) = 2\sum_{l=0}^{n-1} l + \sum_{l=0}^{n-1} 1[/math]

 

Now, the right hand summation is easy: [math]\sum_{l=0}^{n-1} 1 = n[/math].

 

For the left-hand summation; it's a well known fact that [math]1 + 2 + \cdots + n = \frac{n(n+1)}{2}[/math] (I can prove this if you want, but there's millions of proofs out there).

 

So, we get [math]2\sum_{l=0}^{n-1} l = n(n-1) = n^2 - n[/math]. Adding the two sums together we get the final answer.

[Klaynos]

Thanks guys

[woelen]

Another way of proving such things is called by induction.

 

Show that it is true for 1 or 2.

 

Assume that it is true for n. Then show, using the assumption that it is true for n, that it is true for n+1.

 

For n = 1, this obviously is true.

 

Now, assuming it is true for a certain value n, we evaluate the sum for n+1.

 

The sum for n+1 can be written as the sum for n + one term: n² + (2n+1). It is clear that this equals (n+1)².

 

This is the proof.

 

-------------------------------------------------------------

 

This kind of proofs is not useful of course if you don't have a clue what the actual sum is, but in many cases, one has an answer (either found by means of some other ingenious way, or simply given) and then this is a very easy way of proving.