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

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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$.

Answer 4

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$$

Answer 5

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$$

Answer 6

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$$

Answer 7

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$.

Answer 8

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$.

Answer 9

My favorite Proof Without Words for this sum:

Answer 10

We have, (x+1)^2 - x^2 = 2x + 1

Using this, we can say,

1^2 = 0^2 + 1 = 0 +1 = 1

2^2 = 1^2 + 3 = 1 + 3 = 4

3^2 = 2^2 + 5 = 1 + 3 + 5 = 9 and so on...

This explains why the sum is n^2.

Answer 11

Step 1. For n = 1 it's true that 1 = 2*1-1

Step 2. We suppose that 1+3+5+...+(2n-1) = n2 and want to prove that: 1+3+5+...+(2(n+1)-1) = (n+1)2

We add (2(n+1) -1) to this: 1+3+5+...+(2n-1) = n2

and get: 1+3+5+...+(2n-1) + (2(n+1) -1) = n2 + (2(n+1) -1)

so: 1+3+5+...+(2(n+1) -1) = n2 + 2n+2 -1

but n2+2n+1 = (n+1)2

so we finally have: 1+3+5+...+(2(n+1)-1) = (n+1)2