Strong Induction

Strong Induction / Complete Induction / Second Principle of Mathematical Induction (often abbreviated as PCI) is one of the techniques to prove Results/Conjecture.

STATEMENT

Let `P(n)` be a given Propostional Function

To prove that `P(n)` is TRUE for all integers `n\geqn_{o}`, it is sufficient to prove:

BASIS STEP : Verify that `P(n_{o})` is TRUE
INDUCTIVE STEP : Show that conditional statement

`[ P(n_{o}) \wedge P(n_{o}+1) \wedge ....... \wedge P(k) ] \rightarrow P(k+1)`

holds `\forall k\geqn_{o}`

WHAT WE ARE EXACTLY DOING HERE?

We are making a STRONG ASSUMPTION.

We have to ASSUME that `P(1), P(2), . . . P(k)` are true. Based on assumption, we will obtain some mathematical results.
With that results, we have to show that `P(k+1)` will be True.

AS RULE OF INFERENCE

`( P(n_{o}) \wedge [\forall k {( P(n_{o}) \wedge P(n_{o}+1) \wedge ....... \wedge P(k) ) \rightarrow P(k+1)} ] ) \rightarrow \forall n P(n)`

NOTE ✍🏻

Now, PMI, PCI and WOP are equivalent. [PMI stands for Principle of Mathematical Induction, PCI stands for Principle of Complete Induction, while WOP stands for Well Ordering Property]

If something is True by one, it is True by all three.

But often, one way is easier to prove a particular problem.

INTERESTING EXAMPLE 🍫

A Chocolate Bar consists of UNIT SQUARE of `n\timesm` RECTANGULAR GRID. Show that for SPLITTING bar into INDIVIDUAL UNIT SQUARES, we need `nm-1` breaks.

BASIS STEP: For 1x1 Square Grid (Or Rectangular, since every square is rectangle), we need ZERO breaks to break into INDIVIDUAL UNIT SQUARES. Now,

`n=1`

`m=1`

And,

`nm-1=(1\times1) - 1 = 0`

Hence, proposition is true for base case.

INDUCTIVE STEP: Now, let `P(n,m)` denote number of breaks needed to split an `n\timesm` bar. Now, our hypothesis is strong. We are assuming that we have proved for all `j<n` or `k<m` that `P(j,k)` holds. Based on this hypothesis, we have to show that `P(n,m)` will also be True.

Assuming FIRST BREAK is along a row, we get two bars

First Bar of `n_{1}\timesm`, and a
Second Bar of `n_{2}\timesm`

where `n_{1}+n_{2}=n`

Now, Because of Our Hypothesis

To further break First Bar into individual unit squares, we need `n_{1}m -1` breaks.

And, to further break Second Bar into individual unit squares, we need `n_{2}m - 1` breaks.

Therefore, Total Number of Breaks

= `(1) + (n_{1}m -1) + (n_{2}m - 1)`

= `n_{1}m + n_{2}m - 1`

= `m(n_{1} + n_{2}) - 1`

= `mn - 1`

Hence, `P(m,n)` is True on basis of our Hypothesis.

Hence, By Structural Induction `P(m,n)` is True `\forall m\geq1, n\geq1`

😥 CONFUSED? Have a Chocolate. Eating chocolate can be protective for your brain and enhance your brain’s plasticity, the lifelong ability to change and adapt. 😉

Strong Induction