# How to prove for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?

I'm new to induction so please bear with me. How can I prove using induction that, for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?

I think $9$ can be an example since the sum of the first $9$ positive odd numbers is $1,3,5,7,9,11,13,15,17 = 81 = 9^2$, but where do I go from here.

-

Note that odd integers are of the form $2k + 1$, for $k \in \mathbb{Z}$. Consider the series:

$$\sum_{i=0}^{n} (2i+1) = 2\sum_{i=0}^{n}i + \sum_{i=0}^{n} 1 = 2 * \frac{n(n-1)}{2} + n = n^{2} - n + n = n^{2}$$

Hopefully this gives you a better idea of what is going on. This is the algebra you'll probably want to use for your inductive step.

-
Thank you very much! –  Juan247 Mar 26 at 16:37
This is indeed a proof of the stated proposition, but it explains nothing about induction. –  wolfen Mar 26 at 16:58
The algebra would be used on the inductive step when we add in the $(n+1)$. This was intended more as a hint to get the OP going, which it seems to have done. :-) –  ml0105 Mar 26 at 17:01

Induction is done by demonstrating that if the condition is true for some $n$ then it must also be true for $n+1$. If you then show that the condition is true for $n=0$ then it must be true for all $n>0$. For this problem:

Step $1$: $n=1$

The sum of the first $1$ odd numbers is $1$. $1^2=1$. Therefore the condition holds for $n=1$.

Step $2$: induction

If the sum of the first $n$ odd numbers is $n^2$ then the sum of the first $n+1$ integers is $n^2 + (2n + 1) = (n+1)(n+1)=(n+1)^2$

So the condition is also true for $n+1$.

Step $3$: conclusion

Since the we have shown that the condition is true for $n=1$ and we have shown that if it is true for $n$ then it is also true for $n+1$ then it follows by induction that it is true for all $n\geq 1$.

-
Thank you very much!!! –  Juan247 Mar 26 at 16:37
+1 for explaining how induction works, as well as how it applies to the stated problem. –  wolfen Mar 26 at 16:59

My favorite Proof Without Words for this sum:

-
Brilliant! It's great for teaching purposes. –  orion Mar 26 at 21:15

Let $P(n)$ be the statement that the sum of the first $n$ odd positive integers is $n^2$. $1=1^2$, so we have $P(1)$.

Suppose we have $P(k)$ for some positive integer $k$. Then the sum of the first $k$ odd positive integers is $k^2$. Now the $(k+1)$th odd positive integer is $2k+1$, so the sum of the first $k+1$ odd positive integers is $k^2+2k+1=(k+1)^2$. Hence we have $P(k+1)$.

It follows that we have $P(n)$ for all positive integers $n$.

-

what you want to prove: $\sum_{i=0}^{n-1} (2i + 1) = n^2$.

induction base ($n=1$): $\sum_{i=0}^{n-1} (2i + 1) = 1$.

induction step ($n \rightarrow n+1$):

$\sum_{i=0}^{(n+1)-1} (2i + 1) = 2n + 1 + \sum_{i=0}^{n-1} (2i + 1) = n^2 + 2n + 1 = (n+1)^2$.

-

Induction.

Conjecture:

$$\sum_{k=1}^{2n-1}k=n^2$$ where $2n-1$ is the $n$-th odd number.

First term ($n=1$):

$$\sum_{k=1}^1 k=1=n^2$$

Induction step:

$$(n+1)^2=n^2+(2n+1)=\sum_{k=1}^{2n-1} k + (2n+1)=\sum_{k=1}^{2(n+1)-1}k$$

-

If you already know what is the sum of all the first $\;n\;$ natural numbers:

$$1+3+5+\ldots+(2n-1)=1+2+3+\ldots+2n-(2+4+6+\ldots+2n)=$$

$$=\frac{2n(2n+1)}2-2(1+2+\ldots+n)=n(\color{green}{2n}+\color{red}1)-n(\color{green}n+\color{red}1)=n^2$$

-

Perhaps not the answer you are looking for but have you ever noticed that the difference of two consecutive squares is always odd? And furthermore that the difference of the next two consecutive squares is $2$ more than the previous one?

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

From here you can easily prove your answer but you can also use this trick for calculating squares easily such as : $$103^2 = 100^2 + 201 + 203 + 205 = 10000 + 609 = 10609$$

-
Thank you very much!!! –  Juan247 Mar 27 at 2:07

Here's a direct approach (using a trick from Don Knuths "Concrete Mathematics"):

$\sum_{i=0}^{n-1} (i+1)^2 = \sum_{i=0}^n i^2$ (index shifting, and 0th summand is 0).

Now, we manipulate the left side of the above equation:

$\sum_{i=0}^{n-1} (i+1)^2 = \sum_{i=0}^{n-1} (i^2 + 2i + 1) = \sum_{i=0}^{n-1} i^2 + \sum_{i=0}^{n-1} (2i + 1)$, which can (by adding and subtracting $n^2$) be transformed to $\sum_{i=0}^n i^2 - n^2 + \sum_{i=0}^{n-1} (2i + 1)$.

That is, we now know that $\sum_{i=0}^n i^2 - n^2 + \sum_{i=0}^{n-1} (2i + 1) = \sum_{i=0}^n i^2$. Subtracting $\sum_{i=0}^n i^2$ on both sides yields $- n^2 + \sum_{i=0}^{n-1} (2i + 1) = 0$, resulting in $n^2 = \sum_{i=0}^{n-1} (2i+1)$ - stating that the first $n$ odd numbers sum up to $n^2$.

-