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