0
$\begingroup$

I get induction.

(i) show that the statement holds when n=1 (or some basis)

(ii) show that the statement holds for a general subsequent case, $n+1$.

By PMI the statement holds for all cases.

Dominoes, and all that. I get it. It makes sense.

But when it comes to Principle of Strong/Complete Induction i don't understand why we are assuming it holds for a range. Honestly the whole 'assume' part of any induction is what gets me. Why do I need to assume anything? Isn't it adequate to show it works without assuming it?

I have added an example of PSI below.


Use PCI to prove that every natural number greater than or equal to $11$ can be written in the form $2s +5t$, for some natural numbers $s$ and $t$.


Approach:

I would think I need to show that it works for n=11, and it works for m=12, and then show how it will work for n+2 and m+2 (since both need a slightly different formula to compute).

$n=11 = 2(3) +5(1); s=3$ and $t=1$

$n=12 = 2(1) +5(2); s=1$ and $t=2$

so obviously, for each subsequent case n, you add another s to the n-2. I find it tricky to express this succinctly but here's my attempt at a proof.


Proof (by PCI):

(i) Let n be an integer greater than or equal to $11$.

When $n=11 = 2(3) +5(1); s=3$ and $t=1.$

When $n=12 = 2(1) +5(2); s=1$ and $t=2.$

Thus the statement holds for $n=11$ and $n=12$.

(ii) Assume the statement holds for $11\leq i \leq n$. Because $n\geq 13$, $n-2 \geq 11$, so $n-2 = 2s =5t$ for some $s$, $t$ in $\mathbb{N}.$

Therefore $n=2(s+1) +5t$.

Therefore, by PCI, every natural number greater than or equal to $11$ can be written in the form $2s +5t$, for some natural numbers $s$ and $t$.

$\endgroup$
  • $\begingroup$ It might help you to think of it as "suppose" instead of "assume". "Isn't it adequate to show it works without assuming it?" - yes, but it's cumbersome. To show $P(7)$, it's much much easier to show "$P(1)$, and $P(n) \to P(n+1)$, so by induction $P(7)$" than it is to show "$P(1)$, so $P(2)$, so $P(3)$, so, $\dots$, so $P(7)$". $\endgroup$ – Patrick Stevens Oct 24 '16 at 7:43
  • $\begingroup$ Thanks @PatrickStevens - I do understand why induction is helpful. What I meant was, why is the assumption necessary for induction. Can I not say something like... because it holds for n=1, and it holds for all subsequent cases, n+1, then it holds for all cases, by PMI. ---- instead of Assume it holds, now look, it holds? ---- it is specifically the need for the assumption that I don't understand. Why is the assumption helpful? $\endgroup$ – Alex Butterfield Oct 24 '16 at 7:50
  • $\begingroup$ Sometimes your proof of the inductive step depends on the hypothesis holding for more cases than just the previous one. $\endgroup$ – Vik78 Oct 24 '16 at 7:54
  • $\begingroup$ @vik78 - the example I gave does exactly that. But I feel like the assumption I made in step (ii) is unnecessary. Wouldn't the proof make sense without that sentence, "Assume the statement holds for 11≤i≤n" $\endgroup$ – Alex Butterfield Oct 24 '16 at 8:00
  • $\begingroup$ The thing is, the hypothesis of strong induction is actually equivalent to that of weak induction. So you didn't actually make any extraneous assumptions using strong induction in place of weak induction. $\endgroup$ – Vik78 Oct 24 '16 at 8:10
0
$\begingroup$

In some problems, the truth of the $(k+1)$-st case can require that more than just the $k$th case be true (maybe all cases, $1$ through $k$ are required). In these cases, strong induction, or a variant thereof is required (so that you have the relevant preceding cases true in order to complete the inductive step).

All proofs by induction are made up of two key parts: The base case, and the inductive step.

In the inductive step, you assume the truth of the $k$th case (or in the strong variant, all cases up to $k$) and use that to prove that the $(k+1)$-st case holds. What you establish in this step is the implication:

Previous case(s) $\Rightarrow$ Next case

This, of course, is a conditional statement, and hence, does not, on it's own, suffice to prove the original proposition (that it's true for all cases). This is what the base case does. It 'starts the dominoes falling'.

With the base case proven, then you get a chain of implications:

Base case $\Rightarrow$ 2nd case

With base case true, therefore 2nd case is true

2nd case (and base case in strong version) $\Rightarrow$ 3rd case

etc.

thus all cases in the chain are true (this is the dominoes falling part of the induction).

$\endgroup$
  • $\begingroup$ thanks for the reply. Let me run this example by you as I don't think I'm being clear in what it is that confuses me. $\endgroup$ – Alex Butterfield Oct 24 '16 at 9:24
  • $\begingroup$ Prove the property of Fibonacci numbers, using PCI: f_n is a natural number for all natural numbers n. $\endgroup$ – Alex Butterfield Oct 24 '16 at 9:25
  • $\begingroup$ Proof: $n=1 f_n=1, n=2 f_2 = 1, n=3 f_3=3$. Now ''''assume'''' $f_n$ is a natural number for all 3<n<k. Because $f_(k+1) = f_k + f_(k-1)$, where $f_k$ and $f_k-1$ are natural numbers then $f_(k+1)$ is also a natural number, since the sum of two positive integers is also a positive integer. $\endgroup$ – Alex Butterfield Oct 24 '16 at 9:28
  • $\begingroup$ sorry for the confusing formatting. I don't now how to put spaces inside the dollar signs, or line breaks in this comment section. $\endgroup$ – Alex Butterfield Oct 24 '16 at 9:29
  • $\begingroup$ You only technically need to assume that $f_k$ and $f_{(k-1)}$ are natural numbers for the inductive step. This is an assumption because, at this stage, you do not actually know yet if what you are stating is true. Even when the inductive step is complete, you only know it's truth if the base cases have been proven (because the inductive step is a conditional statement, the condition being that the previous two cases are true). $\endgroup$ – Justin Benfield Oct 24 '16 at 9:42

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.