Mathematical Induction

**Discrete** · July 16th 2007, 05:37 PM

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

**galactus** · July 16th 2007, 06:06 PM

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.

**Discrete** · July 16th 2007, 06:51 PM

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?

Thread: Mathematical Induction

LinkBack

Thread Tools

Display