Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

9 Answers 9

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank you very much! –  Juan247 Mar 26 at 16:37
3  
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$.

share|improve this answer
    
Thank you very much!!! –  Juan247 Mar 26 at 16:37
4  
+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:

squares

share|improve this answer
    
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$.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.