1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Well, try it. You need some base case...what do you propose? $\endgroup$ – lulu Nov 3 '16 at 12:54
  • 2
    $\begingroup$ Just to stress: it is not true that the fact that $n$ can be written as you want implies that $n+1$ can. $3=3\times 1+7\times 0$ but $4$ can't be written in the desired form. $\endgroup$ – lulu Nov 3 '16 at 12:59
  • $\begingroup$ Note: if you don't put it inside MathJax then $<$ is interpreted as the start of an HTML tag, and everything on the line after it does not show. $\endgroup$ – Graham Kemp Nov 3 '16 at 13:02
  • $\begingroup$ If the induction step were $P(n) \implies P(n+1)$ we'd need only one base case. If the induction step were $P(n) \implies P(n+2)$ then one base case would only prove it true for every other number and we'd need two base cases to prove for all numbers. Here your induction step is $P(n) \implies P(n + 3)$ so one base case will only prove it for one third of the numbers. $P(12) \implies P(n \equiv 0 \mod 3;n \ge 12)$ which is not enough. $P(13) \implies P(n \equiv 1\mod 3; n > 12)$. and we need $P(14)$ to get $P(n\equiv 2 \mod 3; n > 12)$. $\endgroup$ – fleablood Nov 3 '16 at 18:58
  • $\begingroup$ I remmeber the Chicken McNugget Theorem link $\endgroup$ – Ricardo Largaespada Nov 4 '16 at 0:09
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true? $\endgroup$ – IgnorantCuriosity Nov 6 '16 at 19:47
  • $\begingroup$ @IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12\le k<n$, where $n$ is some natural number greater than or equal to $15$. If $n\ge 15$, then $12\le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \\ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ... $\endgroup$ – Brian M. Scott Nov 6 '16 at 19:54
  • $\begingroup$ ... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible. $\endgroup$ – Brian M. Scott Nov 6 '16 at 19:55
  • $\begingroup$ I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me? $\endgroup$ – IgnorantCuriosity Nov 6 '16 at 20:13
  • $\begingroup$ @IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments. $\endgroup$ – Brian M. Scott Nov 6 '16 at 20:15
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? 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)? $\endgroup$ – IgnorantCuriosity Nov 3 '16 at 15:48
  • $\begingroup$ See the addition, @IgnorantCuriosity $\endgroup$ – Graham Kemp Nov 3 '16 at 23:55
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.