About me

Michael L Perry

Improving Enterprises

Principal Consultant


User login

Inductive reasoning

The problem was: Given: A movement with 20 moving parts having one degree of freedom. Prove: There are ___ connections among those parts. The answer, of course, is 19. But the real exercise is in the proof. This problem is solvable using a technique called inductive reasoning. Inductive reasoning is proving a statement in two parts. First, you prove it for a trivial case. Then, you prove that if it's true for a smaller case, it must be true for a larger case. State the problemTo begin, we need to define some terms to help us reason about the problem. We'll define the terms M, g(M), and c(M) like this:

  • Let M be a movement with one degree of freedom.
  • Let g(M) be the number of gears in the movement.
  • Let c(M) be the number of connections in the movement.

Using these terms, we can state the problem as:

  • Proove that c(M) = g(M)-1.

Start with the trivialThe trivial case is a movement having a single gear. This movement has no connections, since there are no other gears to which it can connect. Written using our new terms:

  • Let M0 be a movement having only one gear.
  • g(M0) = 1.
  • c(M0) = 0.
  • c(M0) = g(M0) - 1.

Build upwardNow if I have a movement Mj, what happens when I add another gear to it? I end up with a movement Mj+1. I want to prove that the connections in Mj+1 are one fewer than the gears. Inductive reasoning lets me assume that this is true for Mj.

  1. c(Mj) = g(Mj) - 1.
  2. g(Mj+1) = g(Mj) + 1, because I added a gear.
  3. c(Mj+1) = c(Mj) + 1, because I connected that gear to exactly one previous gear.
  4. c(Mj+1) = g(Mj) - 1 + 1, by combining steps 1 and 3.
  5. c(Mj+1) = g(Mj) + 1 - 1, by commuting step 4.
  6. c(Mj+1) = g(Mj+1) - 1, by combining steps 2 and 5.

Q.E.D. Not so fastI was imprecise in my reasoning in a few places. While this still led to the correct answer in this case, it might have led to something completely wrong in a different problem. Inductive reasoning requires that you prove that the steps you take to get from a smaller problem to a bigger one will cover all possible problems. You have to prove that you can build a movement one part at a time by connecting that gear to exactly one gear of the previous movement. While this is true, it is by no means obvious. If we can't prove that our induction can build any movement, then we can't use it to prove statements about all movements. What about those that can't be assembled one part at a time? What we need is a different induction, one that more obviously covers all movements.