Odd Number Theorem

Theorem

∑ j=1 n (2j−1)=n 2

That is, the sum of the first n odd numbers is the n th square number.

Corollary

A recurrence relation for the square numbers is:

S n =S n−1 +2n−1

Proof

Proof by induction:
For all n∈N >0 , let P(n) be the proposition:

n 2 =∑ j=1 n (2j−1)

Basis for the Induction

P(1) is true, as this just says 1 2 =1 .
This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if P(k) is true, where k≥1 , then it logically follows that P(k+1) is true.

So this is our induction hypothesis:

k 2 =∑ j=1 k (2j−1)

Then we need to show:

(k+1) 2 =∑ j=1 k+1 (2j−1)

Induction Step

This is our induction step:

				(k+1) 2	=		k 2 +2k+1
					=		∑ j=1 k (2j−1)+2k+1			by the induction hypothesis
					=		∑ j=1 k (2j−1)+2(k+1)−1
					=		∑ j=1 k+1 (2j−1)

So P(k)⟹P(k+1) and the result follows by the Principle of Mathematical Induction.

Therefore:

∀n∈N:n 2 =∑ j=1 n (2j−1)

■ proofwiki