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