12.2.8. Example of 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. So the difference is that in the regular induction, the truth of the proposition P(k+1) has to be established by just using P(k) that means when you want to prove that P(k+1) is true, you are just given the hypothesis or the premise that P(k) is true. You are not told anything about what is P(k – 1), P(k – 2) and so on. Whereas in the strong induction, which we have for which argument form is given in the right hand side part when you are establishing the truth of proposition P(k+1), while doing that you can assume that the statement P is true for all values in the domain starting from b up to k that is the difference.

Strong induction allows us to assume that a property P is true for every integer up to a certain point k when trying to prove it for k + 1. This is different from regular induction where we only assume it's true for k to establish the truth for k + 1. In strong induction, having the truth for all previous integers gives more comprehensive support for proving the next case.

Imagine climbing stairs. In regular induction, to reach step k + 1, you just need to be able to step onto k. In strong induction, you can consider that you can climb any of the previous steps (1 through k) to justify your ability to reach k + 1. This inherently provides a stronger basis for the next step.

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 often simplifies the process of proving statements significantly, especially when the standard approach (regular induction) might be cumbersome. It provides broader leverage by allowing you to utilize all previously established truths rather than just the immediate predecessor.

Consider the task of writing an essay. If you can build on all of your previous paragraphs (everything you've written so far), it makes crafting the next paragraph easier. In contrast, if you only rely on the last paragraph, you might struggle to see how to continue the essay effectively.

I will prove what we call as the fundamental theorem of arithmetic and the fundamental theorem of arithmetic says that you take any positive integer starting from one onward it can be expressed as product of prime factors or prime powers, basically.

The proof involves starting with a base case (e.g., for n = 1) and then using strong induction, where you assume the theorem holds for all integers up to k. You then prove it for k + 1 by considering two cases: whether k + 1 is prime or composite. The prime case is straightforward, while the composite case leverages the factors of k + 1, both of which are less than or equal to k, to conclude the theorem holds for k + 1.

Think of a library catalog where each book can be classified. If you know how to categorize all books up to a certain point, you can easily categorize the next book based on those examples, regardless of its specific content.

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 making here.

Here's how the proof proceeds: You establish several base cases for amounts from 12 to 15. Each of these can be created using combinations of 4 and 5 rupee stamps. Then, assuming that postage for amounts k is possible for each of these values, you demonstrate how to achieve k + 1 by adding stamps accordingly. This method hinges on ensuring that you can always represent k + 1 based on the established combinations from previous amounts.

Imagine trying to create every possible amount of money using only coins of two denominations, say 2 and 3 rupees. If you can create 12, 13, and so on, you can always find a way to create the next amount by using one of each coin type in a particular combination, building from what you have already established.

--