# Is this a valid shortcut (using induction hypothesis) for the proof of the sum of the first n natural numbers?

http://jriedy.users.sonic.net/VI/math202-f08/Solutionsforthirdweeksassignments.html

If you look at this link and go down to the equation right after

To proceed, we pull the n+1  term out of the sum to see that


Couldn't you stop then and there, since by the induction hypothesis you assume that

$$\sum_{i=1}^{n}{i} = \frac{n*(n+1)}{2}$$

So, all you're left with is

$$n+1 = n+1$$

which is true.

So, basically all that factoring out and other steps in that website are redundant?

-

No, you cannot stop there, because the purpose of the induction is not to show the truth of

$$\sum_{i=1}^{n} i + (n+1) = \frac{n(n+1)}{2} + n+1$$

Indeed, that statement is a trivial consequence of the induction hypothesis, as you correctly noted. The purpose of the inductive step is to show that

$$\sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2}$$

To establish the general formula

$$\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$$

To get the second formula written above, you must resort to the factoring.

-
In the book I'm reading, the author frequently uses the induction hypothesis S(n) to simplify S(n+1)...now I'm confused why you can't use it here to show that S(n+1) is true. –  Wuschelbeutel Kartoffelhuhn Sep 17 '12 at 0:59
you replace one term via the induction hypothesis. why is it not legal to replace more? –  Wuschelbeutel Kartoffelhuhn Sep 17 '12 at 1:06
You can use $n$ case to show that the $n+1$ case is true, this is the crux of proof by induction. However, I think the issue here is that you are confused as to what exactly is the "goal" of the $n+1$ case. The goal of the $n+1$ case is to get $(n+1)(n+2)/2$ on the right-hand side. In other words, the goal of this induction is to put the expression in a particular form. Does that clarify anything? –  Isaac Solomon Sep 17 '12 at 1:08
Aren't you allowed to start with the second equation from your answer (just say "I conjecture that this is true, but it might not be") and then simplify it, and then replace it with the induction hypothesis to establish its truth at the end with an expression like 1=1? Is there something illegal in this way? I don't see the logical flaw in my approach. –  Wuschelbeutel Kartoffelhuhn Sep 17 '12 at 1:12
I think I get it now. The website author is just "massaging" the LHS in that line, not the entire equation. Of course, I dont want to establish the truth of the LHS only –  Wuschelbeutel Kartoffelhuhn Sep 17 '12 at 1:37

One can indeed reduce the inductive proof to verifying the equality $\rm\: n+1 = n+1\:$ by using a special form of induction tailored specifically for such indefinite sums. Namely we can invoke the Fundamental Theorem of Difference Calculus (which has a simple inductive proof).

$$\rm\ F(n)\ =\ \sum_{i\:=\:1}^n\ f(i)\ \iff\ \ F(n\!+\!1) - F(n)\ =\ f(n\!+\!1),\ \ \ F(1) =\: f(1)$$

In your example we have $\rm\:F(n)\, =\, n(n\!+\!1)/2,\ \ f(n)\, =\, n,\:$ hence $\rm\: F(1) = 1 = f(1),\:$ and

$$\rm\ F(n\!+\!1)-F(n)\ =\ \dfrac{(n\!+\!1)(n\!+\!2)}2-\dfrac{n(n\!+\!1)}2\ =\ (n\!+\!1)\left(\dfrac{n\!+\!2}2-\dfrac{n}2\right)\, =\, n\!+\!1\, =\, f(n\!+\!1)$$

hence the sought equality follows by the Fundamental Theorem.

Note that by employing the Fundamental Theorem we have reduced the proof to the mechanical verification of the equations on the RHS of the $\iff$, which here amount to checking that two polynomials in $\rm\,n\,$ are equal (here $\rm = n\!+\!1).\:$ No ingenuity is required in devising the inductive step. Instead that ingenuity has been encapsulated once and for all in the proof of the Fundamental Theorem - whose inductive proof is obvious because we have abstracted away from all the peculiarities of its special cases. Namely, the inductive step amounts simply to telescopic cancellation - a general method behind may inductive proofs. For further discussion and examples see my many posts on telescopy.

-