Table of Contents   |   Proof Methods   |   Glossary

---

Misleading Mathematics

Moving Things Across The Equality

Here's an example involving an inequality.  (Inequality proofs come up frequently in solving running time proofs).

(1) Show that the following proposition P(n) is true for all

                                                                                               

(2) Check the base case at n = 4. 

           4! > 4² ; (4 * 3 * 2 * 1 = 24) > (4 * 4 = 16)  True at n = 4      

(3) Assume the following hypothesis is true for all 4 <= i <= k

                                                                                                 

(4) Prove, given the inductive hypothesis, that P(k+1) is true :

           

           

Divide both sides by (k+1)

           

        Therefore

                           

The final statement is incorrect for a number of reasons.  First, it doesn't meet the exact form of the initial hypothesis that

     

We can't move things from side to side of the inequality.  Instead, we need to show that mathematically, (k + 1)! can be rewritten as something that is clearly larger than (k + 1)².

Remember that when you're performing the Inductive Step, you're reducing  f(k+1) to a function of f(k) and k+1, substitute g(k) for f(k), and derive g(k+1).

 Finish the proof correctly.

Back to:

• Understanding Mathematical Induction
• Proving by Induction
• Inductive Practice Problems
• Pitfalls

Top of Page   |   Table of Contents   |   Proof Methods   |   Glossary