When is the strong form of mathematical induction useful?

"Now sometimes we actually need to make a stronger assumption than just the single proposition P(k) is true in order to prove that P(k + 1) is true. In all the examples above, the k + 1 case flowed directly from the k case, and only the k case. But sometimes, you need to know that all the cases less than k + 1 are true in order to prove the k + 1 case. In those situations, we use the strong form of mathematical induction. It says:\n\n1. If a predicate is true for a certain number,\n\n2. and its being true for all numbers up to and including some number would reliably mean that it’s also true for the next number, i.e., one number greater,\n\n3. then it’s true for all numbers.\n\nIt’s exactly the same as the weak form, except that the inductive hypothesis is stronger. Instead of having to prove P(k) ⇒ P(k + 1), we get to prove (∀ i ≤ k P(i)) ⇒ P(k + 1). At first glance that might not seem any easier. But if you look carefully, you can see that we’ve added information to the left hand side of the implication. No longer do we need to rely on the single fact that P(5) is true in order to prove P(6). Now we get to take advantage of the fact that P(1), P(2), P(3), P(4), and P(5) are all known to be true when we try to prove P(6). And that can make a world of difference.\n\nThe Fundamental Theorem of Arithmetic says that every natural number greater than 2 is expressible as the product of one or more primes. For instance, 6 can be written as 2 · 3, where 2 and 3 are primes. The number 7 is itself prime, and so can be written as 7. The number 9,180 can be written as 2 · 2 · 3 · 3 · 3 · 5 · 17, all of which are primes. How can we prove that this is always possible, no matter what the number? Let P(n) be the proposition that the number n can be expressed as a product of prime numbers. Our proof goes like this:\n\n1. base case. P(2) is true, since 2 can be written as 2, and 2 is a prime number. Note we didn’t use 0 or 1 as our base case here, since actually neither of those numbers is expressible as a product of primes. Fun fact.\n\n2. inductive step. We now must prove that (∀ i ≤ k P(i)) ⇒ P(k + 1). Put another way, we assume that P(i) is true for every number up to k, and then use that assumption to prove that P(k + 1) is true as well. Regarding the number k + 1, there are two possibilities: either it’s prime, or it’s not. If it is, then we’re done, because it can obviously be written as just itself, which is the product of one prime. (23 can be written as 23.) But suppose it’s not. Then, it can be broken down as the product of two numbers, each less than itself. (21 can be broken down as 7 · 3; 24 can be broken down as 6 · 4 or 12 · 2 or 8 · 3, take your pick.) Now we know nothing special about those two numbers… except the fact that the inductive hypothesis tells us that all numbers less than k + 1 are expressible as the product of one or more primes! So these two numbers, whatever they may be, are expressible as the product of primes, and so when you multiply them together to get k + 1, you will have a longer string of primes multiplied together. Therefore, (∀ i ≤ k P(k)) ⇒ P(k + 1).\n\n3. conclusion. Therefore, by the strong form of mathematical induction, ∀ n ≥ 2 P(n).\n\nYou can see why we needed the strong form here. If we wanted to prove that 15 is expressible as the product of primes, knowing that 14 is expressible as the product of primes doesn’t do us a lick of good. What we needed to know was that 5 and 3 were expressible in that way. In general, the strong form of induction is useful when you have to break something into smaller parts, but there’s no guarantee that the parts will be one less than the original. You only know that they’ll be smaller than the original.\n\nEarlier we stated that every free tree has one less edge than node. Prove it. Let P(n) be the proposition that a free tree with n nodes has n − 1 edges.\n\n1. base case. P(1) is true, since a free tree with 1 node is just a single lonely node, and has no edges.\n\n2. inductive step. We now must prove that (∀ i ≤ k P(i)) ⇒ P(k + 1). Put another way, we assume that all trees smaller than the one we’re looking at have one more node than edge, and then use that assumption to prove that the tree we’re looking at also has one more node than edge. We proceed as follows. Take any free tree with k + 1 nodes. Removing any edge gives you two free trees, each with k nodes or less. Why? Well, if you remove any edge from a free tree, the nodes will no longer be connected, since a free tree is minimally connected as it is. And we can’t break it into more than two trees by removing a single edge, since the edge connects exactly two nodes and each group of nodes on the other side of the removed edge are still connected to each other. Now the sum of the nodes in these two smaller trees is still k + 1. This is because we haven’t removed any nodes from the original free tree—we’ve simply removed an edge. If we let k₁ be the number of nodes in the first tree, and k₂ the number of nodes in the second, we have k₁ + k₂ = k + 1. Okay, but how many edges does the first tree have? Answer: k₁ − 1. How do we know that? By the inductive hypothesis. We’re assuming that any tree smaller than k + 1 nodes has one less edge than node, and so we’re taking advantage of that legal assumption here. Similarly, the second tree has k₂ − 1 edges. The total number of edges in these two trees is thus k₁ − 1 + k₂ − 1, or k₁ + k₂ − 2. Remember that k + 1 = k₁ + k₂ (no nodes removed), and so this is a total of k + 1 − 2 = k − 1 edges. Bingo. Removing one edge from our original tree of k + 1 nodes gave us a total of k − 1 edges. Therefore, that original tree must have had k edges. We have now proven that a tree of k + 1 nodes has k edges, assuming that all smaller trees also have one less edge than node.\n\n3. conclusion. Therefore, by the strong form of mathematical induction, ∀ n ≥ 1 P(n)."