Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
4  
The examples are being done by performing operations on the entire equality, not on each side separately. The problem is that if you start with a false equality, one may perform operations on both sides that are not reversible, and obtain an equality. For example, from $1=-1$, square both sides and get $1=1$. The latter is true, but the former is not. The fact that after performing operations on both sides you get a true statement does not imply you began with a true statement, unless each and every step is "reversible". So one must be careful, which is what they are trying to tell you. –  Arturo Magidin Feb 12 '12 at 5:35
1  
Thanks for the quick responses all. It is much more clear now. –  The111 Feb 12 '12 at 6:52
    
@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. –  Hendrik Vogt Feb 12 '12 at 12:46
add comment

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
"Post hoc ergo propter hoc" (Wikipedia) –  kahen Feb 12 '12 at 6:14
add comment

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} $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.