Odd Number Theorem

Theorem

$\displaystyle \sum_{j=1}^n \left({2j - 1}\right) = 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 \in \N^*$, let $P \left({n}\right)$ be the proposition:

$\displaystyle n^2 = \sum_{j=1}^n \left({2j - 1}\right)$

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 \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

$\displaystyle k^2 = \sum_{j=1}^k \left({2j - 1}\right)$

Then we need to show:

$\displaystyle \left({k+1}\right)^2 = \sum_{j=1}^{k+1} \left({2j - 1}\right)$

Induction Step

This is our induction step:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({k+1}\right)^2\)	\(=\)	\(\displaystyle k^2 + 2 k + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j=1}^k \left({2j-1}\right) + 2 k + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by the induction hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j=1}^k \left({2j-1}\right) + 2 \left({k+1}\right) - 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j=1}^{k+1} \left({2j-1}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore:

$\displaystyle \forall n \in \N: n^2 = \sum_{j=1}^n \left({2j - 1}\right)$

$\blacksquare$

This is usually one of the first proofs by induction that a student mathematician experiences.

Proof of Corollary

Follows directly.

$\blacksquare$

Comment

What this shows is that every square number is the sum of a series of consecutive odd integers:

$n^2 = 1 + 3 + 5 + \cdots + \left({2n-1}\right)$

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.1$
• George E. Andrews: Number Theory (1971): $\S 1.1$: Exercise $5$
• Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.6$