0

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

Nitin
  • 2,948
Alex Butterfield
  • 301
  • 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)$". – Patrick Stevens Oct 24 '16 at 07:43
  • 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? – Alex Butterfield Oct 24 '16 at 07:50
  • Sometimes your proof of the inductive step depends on the hypothesis holding for more cases than just the previous one. – Vik78 Oct 24 '16 at 07:54
  • @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" – Alex Butterfield Oct 24 '16 at 08:00
  • 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. – Vik78 Oct 24 '16 at 08:10
  • When you think about it, the whole point of induction is that you are assuming you already proved the $(k-1)$th case in the proof of the $k$th case. To have proven the $(k-1)$th case by induction, you must have already proven the $(k-2)$th case, and so on until the base case. – Vik78 Oct 24 '16 at 08:13
  • @vik78 - I think that makes sense as to why I assume something. I also found another proof I'm working on now to make sense in my 'assumption'. I assumed something that I needed to use as a substitution and thus arrived at my correct destination, thus allowing me to conclude my assumption to be true. – Alex Butterfield Oct 24 '16 at 08:17
  • There are times, however, where i don't see that connection. And then the assumption seems redundant. (As above) – Alex Butterfield Oct 24 '16 at 08:17
  • What i'm saying is that using strong induction or weak induction is really just a difference in notation. They're the same concept in different words. – Vik78 Oct 24 '16 at 08:26
  • @vik78 I agree with that. But I'm confused by when and what to assume. Like I just did a proof by WOP that root 2 is irrational. To do this I assumed root2 was rational, that assumption led to a contradiction (there is no smallest element that is either the numerator or denominator in the quotient that is equal to root 2 - and therefore there is no quotient equal to root 2.) - I '''assumed''' that root 2 was rational. But for PMI and PSI I dont see why I need any assumption. (But I'm told I am) – Alex Butterfield Oct 24 '16 at 08:44
  • A major issue here for you is that you have completely misstated "normal" induction. We don't show a subsequent case $n+1$. We show that it holds for $n+1$ assuming that it holds for $n$. If we showed it for an arbitrary $n+1$ we would not be doing induction at all. – Tobias Kildetoft Oct 24 '16 at 10:37
  • Remember, the inductive step holds going from the $999$th to the $1000$th case. When you prove the inductive step, you usually haven't already done the $999$th case as part of the base case. Therefore for the proof of the inductive step you need to assume that you've already done it for the previous case-- you haven't actually done it for the previous case yet, it's an assumption. Then when you apply the inductive step repeatedly to the base case, by the time you get to one case you've already done the previous case. Then your assumption will hold and the proof works out. – Vik78 Oct 24 '16 at 17:51
  • It's a little subtle, but the point is that at the time of proving the inductive step you don't already know for a fact that the hypothesis holds for the previous case, since all you know for sure is that it holds in the base case. You need to assume that you have for the proof to work out. – Vik78 Oct 24 '16 at 17:53

1 Answers1

0

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

Justin Benfield
  • 3,992
  • 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. – Alex Butterfield Oct 24 '16 at 09:24
  • Prove the property of Fibonacci numbers, using PCI: f_n is a natural number for all natural numbers n. – Alex Butterfield Oct 24 '16 at 09:25
  • 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. – Alex Butterfield Oct 24 '16 at 09:28
  • sorry for the confusing formatting. I don't now how to put spaces inside the dollar signs, or line breaks in this comment section. – Alex Butterfield Oct 24 '16 at 09:29
  • 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). – Justin Benfield Oct 24 '16 at 09:42
  • Is it fair then, since it is a conditional statement, to say that I am using the propositional form $P$ implies $Q$ - where I am assuming P to be true, and then showing that Q is true. Because of the truth set of P implies Q, it wouldnt even matter if P was true or not, the conditional statement would still be true or vacuously true. – Alex Butterfield Oct 25 '16 at 06:13
  • That's one way of putting it. The point, as you rightly noticed, is that the inductive step proves the conditional statement previous case $\Rightarrow$ next case. The most common way of proving such a statement is to assume the premise is true, and then prove that the conclusion is true under that assumption. You could also prove it by contraposition, assume not next case, prove not previous case, but then your chain doesn't have a first case because it's going from larger $n$ to smaller $n$, so that's no good for the purposes of induction. – Justin Benfield Oct 25 '16 at 11:06