I'm looking for a solid explanation to grow in intuition for strong induction after having a decent foundation in ordinary induction. For example, The proof by induction for "Prove by induction for each $n \in \mathbb{N}$, $3$ divides $4^n$" is as follows.
We proceed by induction.
For $n \in \mathbb{N}$ let $P(n)$ be the statement $3|4^n-1$.
Basis: $n = 1$, $P(1)$ means $3|4^1-1$ which is logically equivalent to $3|3$, which is true.
Inductive Step: Let $n \in \mathbb{N}$ and $P(n)$ be true.
[We want to show that $3|4^{n+1} – 1$ is true.]
Now:
$4^n+1 – 1$
$= 4\cdot 4^n – 1$
$= (3+1)4^n – 1$
$= (3\cdot 4^n)+(4^n-1)$ [Inductive Hypothesis]
Since $3\cdot 4^n$ is divisible by $3$ [it has a factor of $3$] and $4^n-1$ is divisible by $3$ [by the inductive hypothesis] then their sum is also divisible by $3$. Thus, $P(n+1)$ is true.
Thus, since the base case and inductive step are true, $P(n)$ is true i.e. $\forall n \in \mathbb{N}: 3|4^n-1$.
I know the principle of strong mathematical induction can be explained in a similar way that the ordinary principle of mathematical induction is explained. How can I "piggyback" off of this simple example to connect the dots to strong induction.
Would the first step be to define a new sentence, say $Q(n)$, as $P(1),P(2),\ldots,P(n)$ are all true?
Best Answer
I assume that by "complete mathematical induction" you refer to what is often known as "strong induction." Yes, this approach notes that if you are reasoning inductively and can show that $P(1)$ is true and $P(k) \implies P(k+1)$, then you can examine the general case $P(n+1)$ with not only $P(n)$ in your toolbox, but each of $P(1), P(2), \ldots, P(n)$.
For the particular proposition that you gave, strong induction is not helpful. The standard proof by mathematical induction is exactly as you have written it. (Of course, it is not the only way to prove this proposition: you could consider that $4^n = (3+1)^n$ and when the latter is expanded you have a sum of terms that are each divisible by $3$ except the final term, a $1$, which disappears since you are considering $4^n - 1$. But this gets away from your query...)
For an example that is more elucidating, consider proving that every natural number greater than $2$ can be factored entirely into primes. Try proving this by induction and you will see that it is not so helpful: the base case goes through fine, but if you have a natural number $n$, really what you want to say is that either $n$ is prime (and you're done) or $n$ is composite and can be written as $n = a \cdot b$ for two natural numbers $a, b < n$. And it is here that one essentially stagnates with the standard inductive approach.
The advantage of strong induction in this case is that you can say, since each of $a$ and $b$ is less than $n$, they satisfy the inductive hypothesis of being factorable into primes, so each can be factored and these factorizations can then be multiplied together to give a prime decomposition of $n$.