0
$\begingroup$

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?

2 Answers 2

5

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.

  • 1
    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 only2012-09-17
1

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.