What is wrong with this proof by induction for the value of $2+3+\cdots+n$?

Question

For all $n >= 0$, $2+3+\cdots+n=n(n+1)/2$

This is surely wrong,but why we can use induction to prove it is true?See the below:

Let $P(n)$ be the proposition that $2+3+\cdots+n=n(n+1)/2$

Base step: P(0) is true

Inductive step: Let P(k) be true,therefore

$2+3+\cdots+k=k(k+1)/2$.

Now check when the $n$ equals to $k+1$,so we have $2+3+\cdots+k+k+1=k(k+1)/2+k=(k+1)(k+2)/2$,this is also true. Therefore,we can say that P(k) implies P(k+1). Since we have both P(0) and P(k) implies P(k+1),we can say that P(n) is true.

But P(n) is wrong actually ! What is wrong with the prove?

Answer 1

Some people are saying you have to start from $n=2$. That’s not technically correct, though usually how people do it.

Instead, you can take $P(k)$ to be the statement:

$P(k):$ either $k\lt 2$, or else $2+\cdots+k=k(k+1)/2$.

(Better than interpreting the sum as empty, but you can also do that...)

But then your inductive argument only holds if $k\geq 2$; so your argument, as far as it goes, only proves:

1. $P(0)$ holds
2. If $k\geq 2$, then $P(k)\implies P(k+1)$.

So you need separate proofs for $P(0)\implies P(1)$ and for $P(1)\implies P(2)$. Or for $P(1)$ and $P(2)$.

Now, if you use the formulation I give above, then $P(0)\implies P(1)$ (or more directly, $P(1)$) holds because $P(1)$ is true; but then $P(1)\implies P(2)$ does not hold (because $P(2)$ does not hold). So your inductive step is incomplete and you cannot conclude things work.

If you use the formulation to interpret the sum on the left as emtpy when $k\lt 2$, then you run into trouble with $P(0)\implies P(1)$; because $P(1)$ would give you $0=1(2)/2$, which is false.

Either way, your inductive step proof is incomplete, and when you try to fill it in, you run into one case that does not hold, invalidating the whole thing.

---

For a classical example of an incorrect inductive proof that flounders because the inductive step argument only works for sufficiently large $k$, but fails for small $k$, look at the example worked out under item 4 in this answer

Answer 2

We can't use $P(0)$ since the sum starts from $2$, we should use at least $n=2$ as base case which leads to $2=3$.