Question: How to derive this formula? 

$$n^2=\sum\_{k=1}^n(2k-1).$$

Answer: 
*[Notice](http://en.wikipedia.org/wiki/Square_number#Properties) how the difference of two consecutive squares is always an odd number:* $$(x+1)^2=x^2+(2x+1)$$
[![Image](https://i.stack.imgur.com/CJiZi.png)](http://betterexplained.com/articles/surprising-patterns-in-the-square-numbers-1-4-9-16/)
Checking the first few cases, we find:

$1 = 1$

$1 + 3 = 4$

$1 + 3 + 5 = 9$

$1 + 3 + 5 + 7 = 16$

**Okay:** The sequence $1, 4, 9, 16, \ldots$ might be enough evidence to hazard a guess, namely, that the sum of the first $n$ odds is $n^2$.

Let's state this more formally in terms of a *proposition*. Given $n \in \mathbb{N}$, we write the following:

$P(n):$ the sum of the first $n$ odds is $n^2$.

This is a proposition about the natural numbers; so we can now proceed to see if it can be proved by mathematical induction. First up is the **base case**, $P(1)$. What does $P(1)$ mean in plain English?

$P(1):$ the sum of the first $1$ odd is $1^2$.

This is **true**: $1 = 1^2$.

Excellent; the **base case** is taken care of!

Next up is the **inductive hypothesis** (**IH**):

Suppose that $P(k)$ holds for $k \in \mathbb{N}$. Written out, this says that we assume the following:

$P(k):$ the sum of the first $k$ odds is $k^2$.

That is, $1 + 3 + \cdots + (2k-1) = k^2$.

To finish off the proof by induction we need to **prove** the following:

$P(k) \implies P(k+1)$

Stated in plain English, we need to show that **if** $P(k)$ is true, **then** $P(k+1)$ is true, too.

What does $P(k+1)$ assert? It says that:

$P(k+1):$ the sum of the first $k+1$ odds is $(k+1)^2$.

Is this true?

Well, the first $k+1$ odds are: $1 + 3 + \cdots + (2k-1) + (2k+1)$.

Note that, by our **IH**, we know the sum of the first $k$ of these addends; namely, we know that:

$1 + 3 + \cdots + (2k-1) = k^2$.

And so, by **hypothesis**, the sum of the first $k+1$ odds can be written as:

$1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1) = k^2 + 2k + 1 = (k+1)^2$, where the final equality was just a matter of factoring the expression at hand.

**A ha**! In addition to $P(1)$ being true, we have now also proved that $P(k) \implies P(k+1)$.

And so, by the Principle of Mathematical Induction, $P(n)$ holds for all $n \in \mathbb{N}$. **QED**.