Mathematical Induction

• July 16th 2007, 04:37 PM
Discrete
Mathematical Induction
What is wrong with this "proof"?

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

Basic step : The formula is true for n = 1

Inductive Step: Suppose that $\sum_{i=1}^n i = (n+\frac{1}{2})^2/2$. Then $\sum_{i=1}^{n+1} i = (n+\frac{1}{2})^2/2 = (\sum_{i=1}^n i) + (n+1)$. By the inductive hypothesis, $\sum_{i=1}^{n+1} i = (n+\frac{1}{2})^2/2 + n + 1 = (n^2 + n + \frac{1}{4})/2 + n + 1$ $= (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
• July 16th 2007, 05:06 PM
galactus
The sum of the first n integers is $\frac{n(n+1)}{2}$, not $\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.
• July 16th 2007, 05:51 PM
Discrete
Quote:

Originally Posted by galactus
The sum of the first n integers is $\frac{n(n+1)}{2}$, not $\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?