Understanding this proof by strong induction that each n≥12 is n = 3a + 7b for some natural numbers (a,b)

Question

Thm: for all natural numbers $n≥12$, $n = 3a +7b$, for some natural numbers $a$, and $b$. (Natural numbers include 0 here).

My question about the following proof has to do with why we need to show 4 different cases, instead just the last one. I expand this question further at the end.

Proof: By strong induction

For all natural numbers $n$, such that $n≥12$, let $P(n)$ be the statement "$n = 3a +7b$."

Let $n$ be an arbitrary natural number such that $n≥12$. Suppose for every $12 ≤ k < n, P(k)$ is true.

We consider 4 cases.

Case#1: $n = 12$ $$n = 3(4) + 0(7)$$

Case#2: $n = 13$ $$n = 3(2) + 7(1)$$

Case#3: $n = 14$ $$n = 3(0) + 7(2)$$

Case#4: $n≥15$ Then $(n−3)≥12$ and $(n−3)<n$. It follows from the induction hypothesis that $P(n-3)$ is true, and so we can choose some $a$ and $b$ such that $3a + 7b = (n-3)$. Thus, $n = 3a +7b +3 = 3(a+1) +7b$. Since $a+1$ is a natural number, it follows that $P(n)$ is true, and the implication follows. Since $n$ was arbitrary, it is true for all such, and the theorem follows.

My question: Why do we need cases $1, 2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $12 ≤ k < n, P(k)$, and then start with case 4 that says $n≥15$. Since I have assumed $P(k)$ for all values less than $n$, I should be able to draw the same conclusions, as none seem dependent on the previous 3 cases.

If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.

Edit: changed $c$ to $b$, also added MathJax delimiters

Answer 1

Let $P(k)$ be the statment ‘$k$ is a multiple of $3$’, and consider the following proposition:

For each integer $n\ge 12$, $P(n)$ is true.

We’ll use your approach to ‘prove’ it by induction. Let $n$ be a natural number such that $n\ge 15$, and suppose that $P(k)$ holds whenever $12\le k<n$. Clearly $n-3\ge 12$, so by hypothesis $n-3$ is a multiple of $3$. Thus, there is an integer $k$ such that $n-3=3k$. But then $n=3k+3=3(k+1)$ is also a multiploe of $3$, and the result follows by induction.

This is clearly nonsense: it certainly is not true that all natural numbers greater than or equal to $12$ are multiples of $3$. However, there is absolutely nothing wrong with the induction step that I just gave. If it were in fact the case that $n\ge 15$, and all integers $k$ such that $12\le k<n$ were multiples of $3$, then it would indeed be true that $n$ was a multiple of $3$. The problem, of course, is that it is not true that all integers $k$ such that $12\le k<n$ are multiples of $3$. In particular, $13$ is not, so when $n=16$ the induction step rests on a false premise: it works if $16-3=13$ is a multiple of $3$, but that is not in fact the case, and you’re not entitled to assume that it is.

In fact what the induction argument above actually shows is that if $12,13$, and $14$ were all multiples of $3$, then every natural number greater than or equal to $12$ would be a multiple of $3$. Unfortunately for that conclusion, $13$ and $14$ are not multiples of $3$. The induction step is only as good as its foundation: if you don’t verify enough base cases to make the induction step work, the argument is worthless.

In your case that means verifying $3$ cases, because the induction step for $n$ requires that the result be true for $n-3$. Thus, proving $P(15)$ by the induction step requires knowing that $P(12)$ is true, not just assuming it. Similarly, proving $P(16)$ by the induction step requires knowing that $P(13)$ is true, and proving $P(17)$ by the induction step requires knowing that $P(14)$ is true. There are no stages before $12,13$, and $14$: $P(12),P(13)$, and $P(14)$ are the foundation on which everything else rests. For example, $P(20)$ follows by the induction argument from $P(20-3)=P(17)$, which follows by the induction argument from $P(17-3)=P(14)$, but $P(14)$ doesn’t follow by the induction from $P(11)$, because $11$ isn’t in the domain of the argument (and in fact $P(11)$ is false).

Answer 2

My question: Why do we need cases $1,2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $k<n$, ...

Well, for starters, $P(11)$ and several others are false so the assumption is not justified.

If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.

Case 1 and Case 4 show that $P(12+3(0))$ and $\forall n\in \Bbb N: \big(\bigwedge\limits_{k=0}^n P(12+3k)\big)\to P(12+3n+3)$, which proves by strong induction that $\forall n\in \Bbb N: P(12+3n)$.

That is $P(12),P(15),P(18), P(21),\ldots$

This misses out two thirds of what we need to show.   The other two cases allow us to "fill in the gaps".

---

Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem?

Case 4 is an implication.   An implication alone is not sufficient to prove its consequent.

Recall the difference between soundness and validity of a proof.

If you only assume a premise, then the conclusion may not be true. You have to demonstrate that the pemise is justified in order to prove the conclusion.

I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?

The predicate $P(12+3k)$ is that $\exists a{\in}\Bbb N~\exists b{\in}\Bbb N: (12+3k)=3a+7b$.

You can see that $P(12)$ is justified because $12=3(4)+7(0)$. That is that $a=4$ and $b=0$ are witnesses to $P(12)$.

We can also show that if $P(n_0)$ is true, then $P(n_0+3k)$ is true for every natural number $k$.   Because $n_0=4a_0+7b_0 ~\to~ (n_0+3k) = 3(a_0+k)+7(b_0)$ is sound.

Then if $P(12)$ is justified, and $\forall k{\in}\Bbb N:P(n_0)\to P(n_0+3k)$ is sound, then it follows that $\forall k\in\Bbb N: P(12+3k)$ is valid.

Answer 3

Usually a proof by induction has this induction step:

Induction step: $P(n) \implies P(n+1)$

So that and the the base case:

Base case: $P(b)$

will yield:

$P(b) \implies P(b+1) \implies P(b+2) \implies ...$ and "any dope can see that will go on forever and cover every $P(n); n \ge b$".

But in this exercise we do not have "$P(n) \implies P(n+1)$" as our induction step. Instead we have:

Induction step: $P(n-3)\implies P(n)$.

Or in other words:

Induction step: $P(n) \implies P(n+3)$.

So if our base case is:

Base case: $P(14)$.

So we can conclude:

$P(14) \implies P(17) \implies....$

And any dope can see this goes on for ever and $P(14 + 3k);k \ge 0$.

.... well, but that's only $\frac 13$ of the cases. We don't know $P(15),P(16), P(18)$, etc.

So we need:

Base case 2 and 3: $P(12)$ and $P(13)$

the we can conclude we have $P(14 + 3k), P(12 + 3j), P(13 + 3m); k,j,m \ge 0$.

Or in other words $P(n); n \ge 12$.

In short: if the induction step shows $P(n) = P(n+c)$, we must either have $c$ base cases to prove $P(n); n \ge base$, or must accept we can only prove $P(base + kc);k \ge 0$.

====old slightly flippant answer where I misunderstood the induction step somewhat below ====

If your induction step includes "If it is true for $(n-3)$" then you actually have to demonstrate that it is true for $(n-3)$. Via a base case.

So if our base case were true for $n = 15$, and we do induction on it and say "since it is true for $(n-3) = 12$..." we need to sit up and do a "whoa! whoa! whoa, whoa.... It's true for $12$? Sez who???"

Hence we also need a base case of $12$.

So we now have a base case for $12$ and $15$. And we do induction on $n=15$ "since it is true for $n-3 = 12$ it is true for $n+1 = 16$". Cool! It's true for $n=16$.

Then we do induction on $n=16$ and we get "since it is true for $n-3 = 13$..." "whoa! whoa! whoa, whoa...."

and so on.

Answer 4

Prove, by strong induction, that if $n\ge12$, then $n=3a+7b$ for some positive integers $a$ and $b$.

Let's do the induction step, first. Suppose that $n>12$ and that, for $12\le k<n$, $k=3a_k+7b_k$.

If $n-3\ge 12$, then, by the induction hypothesis, $n-3=3a+7b$, so $n=3(a+1)+7b$. Otherwise $n-3<12$, that is, $n=12$, $n=13$ or $n=14$.

Since $12=3\cdot4+7\cdot0$, $13=3\cdot2+7\cdot1$ and $14=3\cdot0+7\cdot2$, we are done, by adding $3$. Also with the base case $n=12$ is obviously covered.

Can you see now why also the cases $n=13$ and $n=14$ are needed? When we do $n-3$ we can't assume that $n-3\ge12$ and we must cope with the possibility $n-3<12$.