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.

  • 0
    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.2012-09-17
  • 0
    you replace one term via the induction hypothesis. why is it not legal to replace more?2012-09-17
  • 0
    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?2012-09-17
  • 0
    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.2012-09-17
  • 0
    You can do that as well, starting at equation 2 and working backwards to the equality 1=1. However, that will also require factoring, and is virtually identical as a proof.2012-09-17
  • 0
    @WuschelbeutelKartoffelhuhn You haven't started with the second formula, though. Whichever direction you go, at some point you have to show that $(n+1)(n+2)/2 = (n(n+1)/2) + (n+1)$; does that make sense?2012-09-17
  • 0
    Is what you're saying: I have to start with the LHS or the RHS of S(n+1) and then derive what I'm support to get in a deducive/direct way? I can't start off with LHS AND RHS of S(N+1) and then establish truth (or falsity)?2012-09-17
  • 0
    The LHS and RHS of $S(n+1)$ is $\sum_{i=1}^{n+1} i = (n+1)(n+2)/2$. You can certainly start here, but you can't assume it is true. You need to prove this equality. There are two directions to prove this equality. Either you break it down using the inductive step into something you know is true. Or, you start with the inductive step and create this equality. The key point is that you can't assume the equality.2012-09-17
  • 0
    If I make the LHS=RHS (S(n+1)) statement and implicitly assume that the = here means a = with a ? on top of it (a guess), do I really make a logical error once I reduce it to 1=1 and establish its truth?2012-09-17
  • 0
    It's not a logical error, it just looks weird. What you are doing is showing that the truth of equality $S(n+1)$ is equivalent to the truth of equality $1=1$, and hence true. However, you'll notice that in the process of getting to $1=1$, you will have to use factoring, so you can't skip any steps.2012-09-17
  • 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.