1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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.