# induction

• March 19th 2008, 04:36 PM
daaavo
induction
how would I go about proving:

the sum of the first n odd numbers is equal to n^2 for every n which is greater than or equal to 1.

Thanks
• March 19th 2008, 05:12 PM
topsquark
Quote:

Originally Posted by daaavo
how would I go about proving:

the sum of the first n odd numbers is equal to n^2 for every n which is greater than or equal to 1.

Thanks

First comes the n = 1 case.
$\sum_{i = 1}^{1}(2i - 1) = 1 = 1^2$ (check!)

Now let the theorem be true for some n = k. We need to show that it is also true for n = k + 1.
$\sum_{i = 1}^{k + 1}(2i - 1) = \sum_{i = 1}^{k}(2i - 1) + (2(k + 1) - 1)$

By our assumption:
$\sum_{i = 1}^{k}(2i - 1) = k^2$

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

For your theorem to be true this must be equal to $(k + 1)^2$. Can you finish this?

-Dan