4
$\begingroup$

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.

$\endgroup$

11 Answers 11

4
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ This is indeed a proof of the stated proposition, but it explains nothing about induction. $\endgroup$ – wolfen Mar 26 '14 at 16:58
  • $\begingroup$ 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. :-) $\endgroup$ – ml0105 Mar 26 '14 at 17:01
13
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ +1 for explaining how induction works, as well as how it applies to the stated problem. $\endgroup$ – wolfen Mar 26 '14 at 16:59
5
$\begingroup$

My favorite Proof Without Words for this sum:

squares

$\endgroup$
  • $\begingroup$ Brilliant! It's great for teaching purposes. $\endgroup$ – orion Mar 26 '14 at 21:15
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you are familiar of Arithmetic Progressions(AP), then it becomes very easy to prove this fact with the 'Sum of n terms of an AP' formula. Check up for it. $\endgroup$ – Hariharan Jul 17 '17 at 9:59
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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