Subsection 8.10.5 An Everyday Example of Strong Induction
Our last example relied on weak induction. There are also everyday examples that rely on strong induction.
Suppose that we want to argue that parents will love however many children they’ve got. Let’s accept two premises:
[1] A first child is always loved.
[2] If you love all the children you’ve already got, you can always love one more.
Number the children in a family by birth order, starting with 1.
We can use strong induction to prove our claim. In fact, it’s very easy to do that since premise [2] is the claim that we usually have to establish in the induction step. So we have:
Base case: (n = 1) Premise [1] guarantees that the parents love the first child.
Induction step: Prove that if you already love n children you will love the (n+1)st one. This is given as premise [2].
So, by Strong Induction, we have that parents love all their children.
Exercises Exercises
1.
Consider the claim that every tissue in the box will eventually be removed.
Let’s number the tissues. The top one will be 1, the one below it 2, and so forth. We’ll say that a tissue can be removed if part of it sticks up out of the box (as shown in the picture).
We’ll start with four premises:
[1] When the box is opened, the top tissue can be pulled up as
shown in the picture.
[2] The tissues have been folded and put into the box in such a way
that, whenever a tissue is removed, the one below it is pulled up as shown in the picture.
[3] Any tissue that is sticking out of the box, as shown in the picture, can easily be removed.
[4] Any tissue that can be removed will eventually be removed. (Imagine it’s allergy season.)
Define: P(n) ≡ Tissuen will be removed.
We want to prove: ∀n (P(n))
Base case: Show that Tissue1 will be removed. Write your proof.
Induction step: We must prove:
∀n ((Tissuen will be removed) → (Tissuen+1 will be removed))
Do it.
2.
Suppose that we want to prove that one will like ice cream on one’s 80th birthday. Further suppose that we have the following premises:
[1] One will (of course) like ice cream on one’s first birthday.
[2] If you liked ice cream on your birthday last year, you’ll like it
this year.
How shall we prove the claim about the octogenarian birthday?
The two premises that we’ve got suggest that we could perhaps use mathematical induction to prove that one would like ice cream on every birthday. That’s not exactly our claim, but it’s a stronger generalization of it. If we knew that one likes ice cream on every birthday, then, by Universal Instantiation, we’d have that, in particular, one likes it on the 80th.
By the way, this idea of proving something stronger than what we really need isn’t crazy. It’s a fairly common strategy. Sometimes a more general (stronger) claim is easier to prove than a more specific (weaker) one.
So let’s do the induction proof of the generalization. Number annual birthdays in sequence starting with the first one (the one at the end of year 1 of life).
Define: P(n) ≡ One likes ice cream on one’s nth birthday.
We want to prove: ∀n (P(n))
Base case: Write your proof.
Induction step: Write your proof. Hint: It’s trivial.
Finally, prove the specific claim about 80th birthdays.
3.
Recall De Morgan’s Laws for Boolean logic:
¬(p ∧ q) ≡ (¬p ∨ ¬q)
¬(p ∨ q) ≡ (¬p ∧ ¬q)
These two identities let us “push nots through ands and ors”. We’ve made a lot of use of them, both in Boolean logic and in predicate logic.
But, as stated here, they apply only when we want to push a not through a single and or or. What about something like this:
¬(p ∧ q ∧ s ∧ t)
(Notice here that we haven’t used additional parentheses to indicate associativity of ∧. We’ve already proved that (p ∧ q) ∧ s is equal to p ∧ (q ∧ s). In other words, that if there are two instances of ∧, the operation is associative. It is possible to generalize that claim to any number of instances of ∧. In fact the proof is by induction and is similar to the one we’re about to do. For now, take it as a theorem that it doesn’t matter how we associate the ∧ operations.)
Now back to the problem of dealing with ¬. Can we exploit De Morgan here? The answer is yes. But, using only the version of De Morgan that we’ve got so far, we’d have to do it one step at a time, starting with this original expression:
¬(((p ∧ q) ∧ s) ∧ t)
Could we instead generalize De Morgan to apply to any finite sequence of ands or ors? The answer to this too is yes. We’d like to have:
[1] For n ≥ 2, \(\neg\bigwedge_{i = 1}^{n}p_{i} = \ \bigvee_{i = 1}^{n}{\neg p}_{i}\) (pushing ¬ through ∧)
[2] For n ≥ 2, \(\neg\bigvee_{i = 1}^{n}{p_{i} = \ }\bigwedge_{i = 1}^{n}{\neg p}_{i}\) (pushing ¬ through ∨)
Read \(\bigwedge_{i = 1}^{n}p_{i}\) as the and of the n variables pi. Similarly for the large or. These two symbols are to ∧ and ∨ what Σ is to addition.
Just to be clear about this new notation: \((\bigwedge_{i = 1}^{5}{p_{i})} = p_{1\ } \land \ p_{2\ } \land {\ p}_{3\ } \land \ \ p_{4\ } \land \ p_{5\ }.\)
How shall we prove that these generalized De Morgan’s laws are valid?
We’ve just been seeing that, when we want to prove that some property holds of an arbitrary number of items that can be arranged in a reasonable order, induction is a good approach. Let’s see if it works here. In particular, we’ll use induction on the number of variables pi.
Use induction to prove [1].
First write an explicit statement of P(n).
Now prove the base case (n = 2). (We need n to be at least 2, since we need two operands for a single ∧.)
Now do the induction step. First, write an explicit statement of exactly what we must prove in this step.
Now write the rest of the induction step