Thread: Mathematical Induction

What is wrong with this "proof"?

"Theorem" For every positive integer n, $\displaystyle \sum_{i=1}^n i = (n+1/2)^2/2$

Basic step : The formula is true for n = 1

Inductive Step: Suppose that $\displaystyle \sum_{i=1}^n i = (n+\frac{1}{2})^2/2$. Then $\displaystyle \sum_{i=1}^{n+1} i = (n+\frac{1}{2})^2/2 = (\sum_{i=1}^n i) + (n+1) $. By the inductive hypothesis, $\displaystyle \sum_{i=1}^{n+1} i = (n+\frac{1}{2})^2/2 + n + 1 = (n^2 + n + \frac{1}{4})/2 + n + 1 $ $\displaystyle = (n^2 + 3n + \frac{9}{4})/2 = (n + \frac{3}{2})^2/2 = [(n+1) + \frac{1}{2}]^2/2$, completing the inductive step.

What I have found wrong is the basic step actually doesn't hold true for n = 1. But I cant find any other mistakes

The sum of the first n integers is $\displaystyle \frac{n(n+1)}{2}$, not $\displaystyle \frac{(n+\frac{1}{2})^{2}}{2}$

The induction should show that your theroem is false.

Since it doesn't hold for 1, that's a clue.

Originally Posted by galactus

The sum of the first n integers is $\displaystyle \frac{n(n+1)}{2}$, not $\displaystyle \frac{(n+\frac{1}{2})^{2}}{2}$

The induction should show that your theroem is false.

Since it doesn't hold for 1, that's a clue.

is that all the mistakes then besides the basic step and the one you mentioned?