Source code online books for professionals by professionals

Figure 4-1.  Using a reduction from A to B to solve A with an algorithm for B. The algorithm for B (the central, inner 
circle) can transform the input B? to the output B!, while the reduction consists of the two transformations (the smaller 
circles) going from A? to B? and from B! to A!, together forming the main algorithm, which transforms the input A? to the 
output A!

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
70
We can take this for granted, and we just splice it into the original formula and see whether we can deduce P(n):
And there you go. The inductive step is established, and we now know that the formula holds for all natural numbers n.
The main thing that enables us to perform this inductive step is that we assume we’ve already established P(n–1). 
This means that we can start with what we know (or, rather, assume) about n–1 and build on that to show something 
about n. Let’s try a slightly less orderly example. Consider a rooted, binary tree where every internal node has two 
children (although it need not be balanced, so the leaves may all have different depths). If the tree has n leaves, how 
many internal nodes does it have?
1
We no longer have a nice sequence of natural numbers, but the choice of induction variable (n) is pretty obvious. 
The solution (the number of internal nodes) is n–1, but now we need to show that this holds for all n. To avoid some 
boring technicalities, we start with n = 3, so we’re guaranteed a single internal node and two leaves (so clearly P(3) is 
true). Now, assume that for n–1 leaves, we have n–2 internal nodes. How do we take the crucial inductive step to n?
This is closer to how things work when building algorithms. Instead of just shuffling numbers and symbols, we’re 
thinking about structures, building them gradually. In this case, we’re adding a leaf to our tree. What happens? The 
problem is that we can’t just add leaves willy-nilly without violating the restrictions we’ve placed on the trees. Instead, 
we can work the step in reverse, from n leaves to n–1. In the tree with n leaves, remove any leaf along with its (internal) 
parent, and connect the two remaining pieces so that the now-disconnected node is inserted where the parent was. 
This is a legal tree with n–1 leaves and (by our induction assumption) n–2 internal nodes. The original tree had one 
more leaf and one more internal node, that is, n leaves and n–1 internals, which is exactly what we wanted to show.
Now, consider the following classic puzzle. How do you cover a checkerboard that has one corner square 
missing, using L-shaped tiles, as illustrated in Figure 
4-2
? Is it even possible? Where would you start? You could try 
a brute-force solution, just starting with the first piece, placing it in every possible position (and with every possible 
orientation), and, for each of those, trying every possibility for the second, and so forth. That wouldn’t exactly be 
efficient. How can we reduce the problem? Where’s the reduction?
2