Find the summation of first 'n' odd numbers

Find a simple formula for the summation of the first 'n' odd numbers (1, 3, 5.....).
More formally, find a general solution for :  
n
Σ (2k-1)
k=1

Source : CLRS A.1-1

3 comments:

Madhur Kumar Tanwani said...

A solution for this is available on the mathforum : http://mathforum.org/library/drmath/view/56886.html

However, I find this proof easier. I'll use "S" instead of the sigma sign. All ranges are from 1 to n.

Using linearity property :
S(2k-1) = 2S(k) - S(1)

We know that S(k) is n(n+1)/2, hence :

S(2k-1) = 2(n)(n+1)/2 - n
which means :

S(2k-1) = n^2

Madan Kumar said...

n=1 => sum=1
n=2 => sum=4
n=3 => sum=9

If you want to find the sum of first n odd numbers, then the answer is n*n. It's that simple

Madhur Kumar Tanwani said...

@Madan
That's correct.

The way to derive that the summation is n^2, is to either assume it is n^2 and then prove it via induction or any of the other proofs stated earlier.

 
Stats