1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ The first time I was exposed to it the lecturer called it strong induction and since then he has always called it complete induction for whatever reason. Anyways, to be more precise in my question I changed the phrasing so thank you for that. Your explanation makes a lot of sense. I was under the impression we could expand ordinary induction proofs to a strong induction proof but, as you said, without the proper proposition that doesn't work. I'm going to tinker with that proof to get a more tangible understanding of what you're talking about. Thanks for informative reply. $\endgroup$ – kr1tzb1tz Mar 29 '17 at 4:31
  • 1
    $\begingroup$ This was very helpful for me. It brought a few ideas together that I've been toying with and made it more cohesive. Thanks again! (Sorry for the late response.) $\endgroup$ – kr1tzb1tz Apr 2 '17 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.