Let's take another run at proving that a watch movement with 20 parts has 19 connections.

It is difficult to prove that any movement can be constructed one gear at a time by making just one connection with an existing gear. And here is a counter-example to demonstrate the problem.

A ring of six gears, all the same size, is a movement with one degree of freedom. If you construct this movement one gear at a time, you will connect the final gear to two prior components, not to just one. This movement has 6 gears and 6 connections, not the 5 that we want our proof to show.

Something is obviously wrong here. This movement is not what is intended by the problem, but it is not explicitly prohibited either. We need to change the problem:

Given: A movement with 20 moving parts having one degree of freedom and no redundant connections.

Prove: There are 19 connections among those parts.

Now our problem is precise enough. While it may seem wrong to change a problem in order to solve it, this is something that happens all the time in software. The requirements are never stated precisely. We always have to go back and ask questions. In the process, we refine the definition of the problem until we agree on something that can be implemented unambiguously.

Find a new induction
After changing our problem to make it provable, we still find that our original approach is difficult. In order to prove that any valid movement can be built on part at a time, we have to prove that there is always at least one component connected to only one neighbor. We have to prove the existence of a leaf.

While this is not a terribly difficult proof, there is an easier way. We could choose a less restrictive induction. Rather than assuming that we can build a movement one part at a time, we only need to know that we can build any movement from two smaller movements. This satisfies the requirements of inductive reasoning.

So first, to prove that we can construct any movement from two smaller movements, we just need to select any connection within the movement. Now break this connection. One of two things will happen:

• You are left with one movement, in which case the connection was redundant. The larger movement was invalid and therefore not covered by the proof.
• You are left with two movements, each with one degree of freedom. Since we broke only one connection, the others remain intact. Assuming the larger movement had no redundant connections, neither do the smaller ones.

So the process of building a movement out of smaller movements is valid. Now we can write our proof:

1. Let M_j+k be the movement formed by connecting M_j and M_k.
2. g(M_j+k) = g(M_j) + g(M_k), because we combined two sets of gears.
3. c(M_j+k) = c(M_j) + c(M_k) + 1, because we added only one new connection.
4. c(M_j+k) = g(M_j)-1 + g(M_k)-1 + 1, by applying the assumption of the induction.
5. c(M_j+k) = g(M_j) + g(M_k) - 1, by association.
6. c(M_j+k) = g(M_j+k) - 1, by combining 2 and 5.

Q.E.D.