# Strong Induction Explanation

I would like an explanation of the principle of strong induction in general, as well as a formal statement of how to prove a statement true for some subset of integers using it. Specifcally, I am curious about how to use it to prove that for any $n \gt 5$ there exist nonnegative integers $a$ and $b$ such that $n=3a+4b$.

Let $P(n)$ be a statement we wish to prove true about each positive integer $n \geq n_0$. To prove the result by strong induction, we prove $P(n_0)$ holds, then show that if $P(n)$ holds for each integer $n \leq m$, then $P(n)$ holds for all positive integers $n \geq n_0$.

In this case, $P(n)$ is the statement that the positive integer $n$ can be expressed in the form $n = 3a + 4b$ for some non-negative integers $a$ and $b$ and $n_0 = 6$. \begin{align*} 6 & = 2 \cdot 3 + 0 \cdot 4\\ 7 & = 1 \cdot 3 + 1 \cdot 4\\ 8 & = 0 \cdot 3 + 2 \cdot 4 \end{align*} Hence, $P(6)$, $P(7)$, and $P(8)$ hold.

Next, we assume $P(n)$ holds for each positive integer $n$ such that $6 \leq n \leq m$, where $m \geq 8$. Let $n = m + 1$. Since $P(n)$ holds for each positive integer $n$ satisfying $6 \leq n \leq m$ and $m \geq 8$, $P(m - 2)$ holds. Therefore, there exist non-negative integers $a$ and $b$ such that $$m - 2 = 3a + 4b$$ Hence, $$m + 1 = (m - 2) + 3 = 3a + 4b + 3 = 3(a + 1) + b$$ Since the non-negative integers are closed under addition, if $a$ is a non-negative integer, so is $a + 1$. Hence, $P(m + 1)$ holds, so $P(n)$ holds for each positive integer $n \geq 6$.

First, show that this is true for $n=6$:

$6=3\cdot2+4\cdot0$

Second, assume that this is true for $n$:

$n=3a+4b$

Third, prove that this is true for $n+1$:

$\color\red{n}+1=$

$\color\red{3a+4b}+1=$

$3a+4b-3+4=$

$3(a-1)+4(b+1)$

Please note that the assumption is used only in the part marked red.

Alternatively (although not a complete proof):

• $A_6=\{3,3\}$
• $A_7=\{3,4\}$
• $A_8=\{4,4\}$
• $A_n=\{3\}\cup{A_{n-3}}$

EDIT:

There is an implicit yet significant flaw in the first part of the answer above, which as indicated in a comment by @QthePlatypus, uses weak induction.

The notion of $3(a-1)$ relies on the fact that $a>0$, which is not true for $n=8=3\cdot0+4\cdot2$.

I am leaving it here for others to learn from...

• Isn't this weak induction? In strong induction we assume that it is true for all P(m) m <= n – Q the Platypus Apr 1 '16 at 6:33
• @QthePlatypus: The first part is weak induction (which seemed sufficient for the question at hand). The second part is strong induction. – barak manos Apr 1 '16 at 6:36
• @QthePlatypus: However, there is a flaw in the first part, please see updated answer. – barak manos Apr 1 '16 at 7:17