12.2.6. Strong Induction

It turns out that there is another form of induction, which we call as strong induction. So this is your argument form for the regular induction where you are given a base case and in the inductive step assuming that, the predicate P is true for k you prove it to be true for k + 1. In the strong induction, the difference is in the inductive step.

Strong induction is a variant of mathematical induction. Similar to regular induction, it consists of proving a base case and an inductive step. However, in strong induction, when proving that property P(k + 1) is true, we can use the assumption that P is true not just for P(k) but for all preceding cases P(b) through P(k). This broader inductive hypothesis allows for different proof techniques where the regular inductive step might be inadequate.

Imagine a class of dominoes lined up. With regular induction, you only need to ensure that if a single domino falls, the next domino will fall too. In contrast, with strong induction, if you show that if any previous domino can cause the next one to fall, then all dominoes will fall. This approach is sometimes more practical, especially in complex systems.

The main motivation of strong induction is that it simplifies your proofs several times. In many cases, it is possible that you cannot apply the regular induction directly, but by using strong induction, using the help of strong induction the proof is simplified a lot.

Strong induction can often make proofs simpler, especially in cases where the regular induction might struggle due to dependencies among several previous cases. By allowing the use of all previous statements, strong induction can bypass difficult transitions that would otherwise complicate a proof. It is particularly useful in situations such as combinatorial proofs or those involving recursive structures.

Consider a group project where one student's work relies on the contributions of many others. Strong induction is like being allowed to rely on the entire team's work rather than just the last contribution. This can assist you in completing your task because you have multiple references to build upon, leading to a more complete and robust outcome.

Let me give you another example of strong induction and a statement here is imagine that in India the only postal stamps which are issued are of denomination rupee 4 and rupee 5. Now the statement I am trying to make here is that each denomination or each postage of rupees 12 or more can be expressed in terms of only 4 rupees stamp and 5 rupees stamps that is the statement I am makinghere.

This example illustrates the principle of strong induction through the lens of postal stamp combinations. The base cases have been established for amounts from 12 to 15 rupees to show they can be represented using the available denominations. The inductive step assumes that for any denominations up from 12 to k, they can be represented using the stamps. We then show how k + 1 can be represented by either adding a 4 rupee stamp to the representation of k - 3 or using combinations of stamps to ensure every amount from 12 onward is covered.

This situation is similar to planning a menu using only specific ingredients. If you know that you can create various dishes using only those available ingredients, you may not just rely on the last dish you created but can mix and match previous ones to form new dishes, expanding your culinary possibilities.

As I said earlier that any proof given by regular induction is equivalent to proof by strong induction and so on. ...

The equivalence of regular and strong induction means that one can be transformed into the other. If a proposition can be proved by one method, it can also be proved by the other. For instance, a proof that relies solely on the most recent case can be restructured to consider previous cases in strong induction. This flexibility allows mathematicians to choose the most convenient proof technique for a given problem.

Think of it as having different routes to the same destination. Whether you decide to travel through a shortcut or a longer scenic route, you will still reach the same place. Similarly, whether you use regular induction or strong induction, you’ll arrive at the same conclusion regarding the truth of a mathematical statement.

--