3
$\begingroup$

I am teaching myself discrete math from this text:

http://www.amazon.com/Discrete-Mathematics-Applications-Susanna-Epp/dp/0495391328/

In chapter 5 there is an example of mathematical induction, and then a comment about what NOT to do, but it seems to me that what is described as bad is exactly what was done in the good example. What am I missing? Here is the "good" example first:

enter image description here

Note that this is not the complete induction process, only the "basis step." Later, an example is given of the "wrong" way to solve that same basis step:

enter image description here

It seems to me that in the first example, both the LHS and the RHS were reduced to 1, to show that 1 = 1. In the second example, i.e. what not to do... the same process was undertaken. What is the difference?

Thanks!

  • 0
    @The111: The formulation in the book is a bit misleading, I think. What the author wants to point out here is nothing particular about induction, it's something to have in mind in any proof where you want to show some identity.2012-02-12

3 Answers 3

6

Suppose LHS and RHS are any two things. In short:

  • Starting with LHS = RHS, then doing the same thing to both sides until a true statement is obtained, clearly cannot, in general, prove that LHS = RHS.

    Simplest example: take any numbers LHS and RHS you like, and multiply both sides by $0$, getting the true $0=0$. Proves nothing about any relationship between LHS and RHS. Lots of fallacies are just artfully disguised versions of this one.

  • Working out that LHS is equal (by its definition, by known-to-be-valid manipulations, whatever ...) is equal to some thing, $x$, and then working out that RHS is also equal (by its definition, by other known facts...) to that same thing, $x$, does prove that LHS = RHS. Because it establishes a chain of equalities LHS $= \dots = x = \dots =$ RHS with each equality proved or holding for some specific reason (by definition, by known facts, whatever), and not simply assumed for no reason.

2

The difference is a matter of clarity in your own reasoning. The "good practice" is that if you want to prove an equality, you start with one side and you work with it until you get the other. The "bad practice" is to work in parallel with both sides, as there is the risk that you are not really proving the original equality.

My favourite example of the risky behaviour is: \begin{align} -1=1\\ (-1)^2=1^2\\ 1=1, \end{align} so $-1=1$ is true.

  • 0
    "[Post hoc ergo propter hoc](http://en.wikipedia.org/wiki/Post_hoc_ergo_propter_hoc)" (Wikipedia)2012-02-12
1

The "=" are in the wrong place. Here's where they should be: $ \sum_{i=0}^0 r^i = r^0 = 1 = \frac{r-1}{r-1} = \frac{r^1-1}{r-1} = \frac{r^{0+1}-1}{r-1} $