Is this proof by induction that $\sum_{i=1} ^{n} i = \frac{n(n+1)}{2}$ correct?

Question

I know it is a supposedly trivial proof and that of course there are a lot of similar topics, but I'm unclear about whether I could logically exhausts the demonstration (I'm also not very clear about the process of proving by induction, say, if I took the steps properly). So I'm showing my demonstration and asking for critiques on it, hoping you won't find it annoying to have someone asking this again here. It goes like that:

Proposition: $1 + 2 + 3 + \dotsb+ n = \frac{n(n + 1)}{2}$

Proof:

Verifying the expression for the base case $n = 1$: $$\frac{1(1 + 1)}{2} = 1$$ which is correct. So we can assume the proposition is true for any $k \leq n$. Now let's verify if it holds for $n + 1$: $$\sum_{i=1}^{n+1} i = \frac{(n + 1)[(n + 1) + 1]}{2} = \frac{(n + 1)(n + 2)}{2} = \frac{n^2 + 3n + 2}{2}.$$

Now, subtracting $(n + 1)$ from both sides of the equation yields $$\sum_{i=1}^{n} i = \frac{n^2 + 3n + 2 - 2n - 2}{2} = \frac{n^2 - n}{2} = \frac{n(n + 1)}{2}$$ which is true and confirms the hypothesis for $n+1$ also.

Answer 1

First of all, you're using strong induction unnecessarily. Here's the basics of how weak induction works:

Say there's a statement $S(n)$ that you want to prove for all whole numbers $n\geq 1$. Then you first need to prove it for $n=1$ (which you did), and then you assume $S(n)$ is true for some value $n$ (because you just proved it was). The "inductive step" tries to prove $S(n+1)$ is true. If it is true, then it will be true for the next value, and the next value, and the next value, ... etc (dominoes are the common analogy), so we will be done.

The problem with your proof is that it assumed $S(n+1)$ was true in the first place, and then reasoned that $S(n)$ was true. It should be the other way around. Just because you come to a true statement at the end of an argument doesn't mean you came to the required statement.

Now it is often helpful to start with the solution and work backwards, but keep in mind it must be in the right order when you write down a proof.

Answer 2

Your induction step consists only of a remark that subtracting $\,n\!+\!1\,$ for both sides of $\,S(n\!+\!1) = T(n\!+\!1)\,$ yields $\,S(n) = T(n).\,$ However, for the induction step we need $\,S(n) = T(n)\,\Rightarrow\, S(n\!+\!1) = T(n\!+\!1).\,$ We can deduce that by reversing your your observation, i.e. it follows by adding $\,n+1\,$ to both sides. But it is essential to explicitly state this derivation of the inductive step $\,P(n)\,\Rightarrow\,P(n\!+\!1)\,$ in order to convince the reader that you understand how to correctly present a proof by induction.

Remark $\ $ Your observation is that $\,S(n\!+\!1)-S(n) = n\!+\!1 = T(n\!+\!1)-T(n),\,$ therefore $\,S\,$ and $\,T\,$ both satisfy the recurrence $\,F(n\!+\!1)-F(n) = n+1,\ F(1) = 1.\,$ The inductive proof is essentially proving the uniqueness theorem for such recurrences, i.e that any two solutions $\,S,T\,$ that start off equal at the initial point $\,n=1\,$ must remain equal for all $\,n\ge 1.\,$ With no extra effort you can prove this for any similar recurrence, which yields a more conceptual view of the matter.

Alternatively you can view this type of induction as a special case of a telescopic sum. See my posts on telescopy for further discussion of this viewpoint.