CMPS 295 Lecture Notes - Strong Induction and Well-Ordering
resources:
*Alternative Forms of Standard Induction*
Standard induction is expressed by
P(0) ^ [(P(k) -> P(k+1)] -> P(n), for 0 < k < n, and n >= 0. // basis is 0
An alternative form of standard induction is to use an integer other than
zero as a basis. Many of the problems from last week did this. For example:
P(1) ^ [(P(k) -> P(k+1)] -> P(n), for 0 < k < n and n >= 1. // basis is 1
* Strong Induction *
Strong induction difers from standard induction in that the inductive
hypothesis for proposition P is not just P(k) but everything from the basis
up to and including P(k). This concept is expressed by proposition P over
N = {0,1,2,3,...}:
(P(0) ^ ((P(1)^...^P(k)) -> P(k+1))) -> P(n), 0 < k < n, n >= 0.
As you move from P(k) to P(k+1) you break up the k+1 chunk into two smaller
chunks, each of which is smaller than k. The size of the sub-chunks depends
on the problem. To generalize:
k+1 = i + (k-i) + 1
= (i + 1) + (k - i), for 0 < i < k.
In standard induction you wrote P(k+1) in such a way that you could make use
of P(k). In strong induction you make use of anything between the basis and k.
If the basis is 0 then the inductive hypothesis looks like this:
Assume P(0)...P(k), show P(k+1), where P(k+1) is written as P(i+1) and P(k-i).
EXAMPLE 1.
Prove that any positive integer >= 8 can be written as a sum of 3s and/or 5s.
Examples: P(8)=5+3, P(9)=3+3+3, P(10)=5+5, P(11)=3+3+5. Appears to be true.
Basis: P(8)=5+3. P(9)=3+3+3. P(10)=5+5.
Inductive Hypothesis: Assume true for P(k-2) ^ P(k-1) ^ P(k):
P(j): every integer j, j = k-2...k, can written as a sum of 3s and 5s.
Inductive Step: Show true for P(k+1).
By the inductive hypothesis, P(k-2) is true. Since k+1=(k-2)+3, P(k+1) is also
true. Alternatively, you can use a basis of j from 8...12 and show that k+1 =
(k-4)+5.
EXAMPLE 2.
Prove that all multiples of 5 cents, >= 20, can be formed using dimes and
quarters. Do the induction on n, where n represents the multiples of 5 cents.
P(n): all 5n multiples can be formed, n >= 4.
Examples: P(4)=2 dimes; P(5)=1 quarter; P(6)=3 dimes; P(7)=1 quarter+1 dime;
Appears true.
Basis: P(4): 20c = 2 dimes
P(5): 25c = 1 quarter
IH: Assume true for P(j), j = k-1..k
IS: Show true for P(k+1).
Since true for P(k-1), add 1 dime to this multiple. Now true for P(k+1).
ex. P(4) = 20c
P(5) = 25c
P(6) = P(4) + 10c = 30c
P(7) = P(5) + 10c = 35c
...
EXAMPLE 3.
P(n): An ATM has only $20 and $50 bills. Show that the ATM can dispense every
multiple n of $10, n >= 4. (Assume an unlimited supply of bills.)
Basis. P(4) = $20 + $20 = $40.
P(5) = $50
IH: Assume true for P(j), j = k-1 to k
IS. Show true for P(k+1).
Given P(k-1), add $20 and now true for P(k+1).
Ex.
P(4) = $20 + $20
P(5) = $50
P(6) = $20 + $20 + $20
P(7) = $50 + $20
P(8) = $20 + $20 + $20 + $20
EXAMPLE 4.
P(n): all positive integers n > 1 are either prime or are the product of a
finite number of primes. (Fundamental Theorem of Arithmetic)
Some concrete examples:
P(2) is prime.
P(3) is prime.
P(4) is the product of two primes < 3.
P(5) is prime.
P(6) is the product of two primes < 5.
P(7) is prime.
P(8) is the product of three primes.
...
Basis. P(2) = 2 is prime.
IH: P(j): Assume true for j, j = 2..k.
P(2) ^ P(3) ^ ... ^ P(k).
IS: Show true for P(k+1).
k+1 is either prime or composite. If k+1 is prime we are done. If k+1 is
composite then k+1 = pq. The largest value for p is when q=2 and the
smallest value for k is 2. Plug these in you you get
2+1 = 2p.
3 = 2p.
p = 3/2.
Clearly, the largest value of p must be less than the smallest value of
k. Thus p must be less than k. By the same reasoning, the largest value
of will always be less than the smallest value of k. Thus p < k and q < k.
By IH, both p and q are either prime or the product of a finite number of
primes. Therefore, the number of factors of k+1 is the sum of two finite
numbers, thus is also finite.
EXAMPLE 5.
Show that all terms in the sequence recursively defined by
b(0) = 0. b(1) = 3. b(n) = b(n-1) + b(n-2) for n >= 2
are divisable by 3.
The terms look like this:
n: 0 1 2 3 4 5 6 ..
0 3 3 6 9 15 24
Use strong induction on n to show P.
Basis. P(0) = 0, 0/3 = 0; true.
Inductive Hypothesis. Assume true for P(k) and P(j), for all j > 0 and < k.
Induction Step. Show true for P(k+1):
P(k+1): Show b(k+1) = b(k) + b(k-1) is divisable by 3
By the induction hypothesis we assume term b(k) and term b(k-1) are both
divisable by 3, thus we can express these terms as
b(k) = 3x and b(k-1) = 3y.
Since 3x + 3y = 3(x+y), true for all n.
EXAMPLE 6.
Use strong induction to show that any group of 12 or more
students can be divided into subgroups of 4 or 5 students.
P: n >= 12 can be divided into subgroups of 4 or 5
Examples:
P(12) = 4 + 4 + 4
P(13) = 4 + 4 + 5
P(14) = 4 + 5 + 5
P(15) = 5 + 5 + 5
Proof.
Basis: P(12) is true.
Inductive Hypothesis. Assume true for P(12),....,P(k).
Inductive Step. Given P(12),...P(k), show true for P(k+1).
By IH we know P(k+1-4) is true. Thus, add 4 to P(k+1-4) and P(k+1) is also
true.
THE STONES PROBLEM
Suppose you begin with a pile of n stones. You split the starting pile into
two smaller piles of arbitrary size. You then pick one of the two piles (any
pile of size > 1 will do). You split that pile into two piles of arbitrary
size. Pick another pile. Split that pile into two piles of arbitrary size.
Continue splitting piles until you end up with n piles of one stone each.
(This requires n - 1 splits, which can be shown with induction.)
Each time you split a pile in the process above, multiply the number of
stones in each of the two sub-piles. E.g., if after the split one pile has r
stones and one pile has s stones, compute rs. Sum all of the products rs from
each split. Use strong induction to show that no matter how you split the
piles, the sum of all the products computed at each split equals n(n-1)/2.
If we call this proposition P, show that P(n) = n(n-1)/2, for n >= 1.
Example. n = 7. n(n-1)/2 = 21.
ooooooo
split 1. ooo oooo r=3 s=4 rs=12
split 2. o oo r=1 s=2 rs=2
... o o r=1 s=1 rs=1
o ooo r=1 s=3 rs=3
o oo r=1 s=2 rs=2
o o r=1 s=1 rs=1
The sum of rs at each step is 12+2+1+3+2+1 = 21. Appears to work. We can use
strong induction to prove it.
Observe that P appears to hold for the sub-piles; e.g., sub-pile of size
4: 4(3)/2=6; 3+2+1=6. Sub-pile of size 3: P(3)=6/2=3; 1+2=3. rs=12. Thus
P(7) split into 4 and 3 is 3+6+12=21; e.g., P(7) = P(4) + P(3) + 4*3.
P(4)=6. P(3)=3, thus P(7) = 6 + 3 + 12 = 21. n(n-1)/2=7(6)/2 = 21; check.
This observation allows us to use strong induction. To generalize:
P(n) = P(n-i) + P(i) + (n-i)(i), P(1) = 0.
We now have a recursive formula over n, where n is the number of stones in
the pile from which you are computing rs. We need to show for n stones, that
the summation of rs over all splits is n(n-1)/2.
Basis. P(2): There is one split. 1*1 = 2(1)/2 = 1. check.
Inductive Hypothesis. Assume true for all piles of size i, for i from 1 to k.
Thus we can assume P(1)..P(k) is true.
Inductive Step. Show true for n=k+1. This means that the sum of all products
computed at all splits for k+1 stones; P(k+1) = (k+1)(k)/2. Show this.
Suppose that our first splitting of k+1 stones is into a pile of i stones and
a pile of (k+1)-i stones, where i < k+1 and >= 1. Thus r=i, s=(k+1)-i and
rs=i(k+1-i). Multiply i through:
rs=ik+i-i^2.
By IH, we assume P(1)...P(k) is true.
Since i is <= k, by IH P(i) = i(i-1)/2.
Since k+1-i <= k, by IH P(k+1-i) = (k+1-i)(k-i)/2.
We can now add P(i) and P(k+1-i). Call this sum X:
i(i-1)/2 + (k+1-i)(k-i)/2 =
(i^2-i)/2 + (k+1-i)(k-i)/2 =
(i^2 - i + k^2 + k - i - 2ik + i^2)/2 =
(2i^2 - 2i + k^2 + k - 2ik)/2.
Next we need to sum rs and X. First express rs with a denominator of 2:
rs=ik+i-i^2.
= 2(ik+i-i^2)/2
= (2ik + 2i -2i^2)/2
Sum rs and X:
(2i^2 - 2i + k^2 + k - 2ik)/2 + (2ik + 2i -2i^2)/2
= (2i^2 - 2i + k^2 + k - 2ik + 2ik + 2i -2i^2)/2
= (2i^2 - 2i + k^2 + k - 2ik + 2ik + 2i -2i^2)/2
= (2i^2 - 2i + k^2 + k - 2ik + 2ik + 2i -2i^2)/2
Rearrange terms:
(2i^2 - 2i^2 - 2i + 2i + k^2 + k - 2ik + 2ik)/2.
Simplify:
(k^2 + k)/2.
Factor:
k(k+1)/2. qed.
//////////////////////
Auxilliary Work:
k+1-i
* k-i
------
k^2 + k -ik
-ik - i + i^2
----------------
k^2 + k - i - 2ik + i^2.
MORE STRONG INDUCTION.
Let P be the proposition that 12 | (n^4 - n^2) for n >= 1. For example:
P(1): 12 | 0; yes. P(2): 12 | (2^4 - 2^2); yes. True for n=1 and n=2.
Prove P for n >= 1 using strong induction.
Basis: P(1): 12 | 1 - 1. Since 12 divides zero, check.
Inductive Hypothesis (IH): (P(k)..P(1)): 12|(k^4-k^2),12|((k-1)^4-(k-1)^2),
and so forth down to k=1. Assume true.
Inductive Step. Show P(k+1): 12 | ((k+1)^4 - (k+1)^2).
Expand and combine terms:
P(k+1): 12 | k^4 + 4k^3 + 5k^2 + 2k.
By IH we assume P(k-5): 12 | (k-5)^4 - (k-5)^2. Expand and combine terms:
P(k-5): 12 | k^4 - 20k^3 + 149k^2 - 490k + 600.
Make P(k+1) into something we can use IH, P(k-5). Restate P(k+1) as follows:
(k^4 - 20k^3 + 149k^2 - 490k + 600) + 24k^3 - 144k^2 + 492k - 600.
Sanity check on the above step:
k^4 -20k^3 +149k^2 -490k +600 +24k^3 -144k^2 +492k -600 =k^4 +4k^3 +5k^2 +2k.
Replace the parenthesized part of P(k+1) with 12i since by IH 12 divides it:
12i + (24k^3 - 144k^2 + 492k - 600).
Factor out a 12 from remaining terms:
= 12i + 12(2k^3 - 12k^2 + 4k - 50). bingo.
////////
Note: Standard induction with just P(k) would also work:
(k+1)^4 = k^4 + 4k^3 + 6k^2 + 4k + 1
(k+1)^4 - (k+1)^2 = k^4 + 4k^3 + 6k^2 + 4k + 1) - (k^2 + 2k + 1)
= k^4 + 4k^3 + 6k^2 + 4k + 1 - k^2 - 2k - 1.
= k^4 + 4k^3 + 5k^2 + 2k. <<< SHOW 12 divides this
We can rearrange terms to get something we can replace with P(k):
= (k^4 - k^2) + 6k^2 + 4k^3 + 2k.
BY IH. 12 | k^4 - k^2, thus replace this term with 12i.
= 12i + (4k^3 + 6k^2 + 2k). Remove the first term since 12 divides it.
Find a factor of 12 in this:
4k^3 + 6k^2 + 2k.
We know that 3 consecutive integers will always have a factor of 2 and a
factor of 3; i.e., a factor of 6. Rearrange terms to use this fact:
4k^3 + 6k^2 + 2k = (k^3 + 3k^2 + 2k) + 3k^3 + 3k^2.
= k(k^2 + 3k + 2) + 3k^3 + 3k^2.
= k(k+1)(k+2) + 3k^3 + 3k^2.
Remove k(k+1)(k+2) since that term has a factor of 6 and we are left with:
3k^3 + 3k^2.
Factor out a 3k^2.
3k^2(k + 1).
Rearrange things a bit.
3k(k)(k + 1).
Since k(k+1) has a factor of 2, qed.
//////////
We could also use strong induction on P(k+1-6) since adding 6 to an
integer that already has a factor of 6 will ensure an integer that still has
a factor of 6. (k+1-6) = k-5. Thus assume P(k-5):
12 | (k-5)^4 - (k-5)^2.
k-5 k^2 - 10k + 25
k-5 k^2 - 10k + 25
======== =================
k^2 -10k + 25. k^4 - 10k^3 + 25k^2
- 10k^3 +100k^2 - 250k
25k^2 - 250k + 25^2
---------------------------------
k^4 -20k^3 + 150k^2 - 500k + 625
(k^4 - 20k^3 + 150k^2 - 500k + 625) - (k^2 - 10k + 25)
= k^4 - 20k^3 + 149k^2 - 490k + 600.
By IH Assume 12 | k^4 - 20k^3 + 149k^2 - 490k + 600.
Show P(k+1): 12 | k^4 + 4k^3 + 5k^2 + 2k.
(k^4 - 20k^3 + 149k^2 - 490k + 600) + 24k^3 - 144k^2 + 492k - 600.
By IH: 12i + (24k^3 - 144k^2 + 492k - 600).
= 12i + 12(2k^3 - 12k^2 + 4k - 50). bingo.
=======================================================
| Using Induction to Prove Properties of Binary Trees |
=======================================================
Definition.
A full binary tree T is a binary tree where each node has either no children or
two children. An internal node in T has two children. An external node in T is
a node with no children and is called a leaf. For a tree with a single node, the
node is an external node. Size(T) returns the number of nodes in T.
Initial Step. Tree T starts as a single leaf node. Size(T) = 1.
Rule 1. To add nodes to T call function add2nodes() that adds two nodes to an
arbitrary leaf node in T, thus maintaining the property of a full tree. At any
given time Size(T) = 2k + 1, k>=1, where k is the kth call to add2nodes().
Property P.
Let I be the count of internal nodes in T. Let E be the count of external nodes
in T. Then E = I + 1, for the initial tree and for all other trees. Let T_i
represent the ith call to add2nodes(). Example:
T_0 T_1 T_2 and so on...
O O O
E_0 = 1 / \ E_1 = 2 / \ E_2 = 3
I_0 = 0 O O I_1 = 1 O O I_2 = 2
/ \
O O
Property P appears to hold in the examples above.
*******************************
* Proof by Standard Induction *
*******************************
In standard induction over the number of calls to add2nodes() to show P holds
for all full trees T.
Basis: A tree of size 1 has 1 external node and 0 internal nodes. E=I+1. check.
IH. Assume P holds for the k_th call to add2nodes(). Thus,
E_k = I_k + 1, for T_k.
IS. Show P holds for the k+1_th call to add2nodes():
E_k+1 = I_k+1 + 1, for T_k+1.
When you add two nodes to T_k, an external node will become an internal node
in T_k+1. Tree T_k+1 will have two more external nodes than T_k. Eq 1 and 2
express this observation:
Eq. 1 Eq. 2
E_k+1 = E_k - 1 + 2. I_k+1 = I_k + 1.
= E_k + 1.
By IH E_k = I_k + 1. Plug IH into Eq. 1:
E_k+1 = (I_k + 1) + 1.
E_k+1 = (I_k + 1) + 1.
E_k+1 = I_k + 2.
Rearrange terms in Eq. 2:
I_k+1 = I_k + 1
I_k = I_k+1 - 1.
Plug (I_k = I_k+1 - 1) into (E_k+1 = I_k + 2):
E_k+1 = (I_k+1 - 1) + 2.
E_k+1 = I_k+1 + 1. qed.
*****************************
* Proof by Strong Induction *
*****************************
Use Strong induction to show E=I+1 holds for all full trees T.
Basis: A tree of size 1 has 1 external node and 0 internal nodes. E=I+1. check.
IH. P holds for all trees constructed by the i_th application add2nodes() from
i=0 to k.
E_i = I_i + 1, for i=0 to k.
IS. Show P holds for the k+1_th application of add2nodes().
Break the tree at application k+1 into its left subtree, its right subtree and
its root. We don't know the size of the left subtree but we assume by IH that P
is true. Say the left subtree was constructed by i applications, for i < k. i:
E_i = I_i + 1, for some i < k.
Likewise for the right subtree, for some j < k:
E_j = I_j + 1, for some j < k.
By observation we know the number of external nodes in T_k+1 is the number of
external nodes of the left subtree plus the right subtree:
E_k+1 = E_i + E_j.
By IH E_i = I_i + 1 and E_j = I_j + 1, thus
E_k+1 = (I_i + 1) + (I_j + 1).
Simplify.
E_k+1 = (I_i + I_j + 1) + 1. Eq 3.
By observation the number of internal nodes of T_k+1 is expressed by
I_k+1 = (I_i + I_j + 1).
Plug above observation into Eq 3.
E_k+1 = I_k+1 + 1. qed.
*********************************
* Proof by Structural Induction *
*********************************
Now use structural induction to show E=I+1 holds for tree T constructed by any
number of applications of Rule 1. Structural induction follows the recursive
rule of building a tree.
Recursive Definition.
Tree T starts as a single leaf node. A single node is an external node.
Rule 1. To add nodes to T call function add2nodes() that adds two nodes to an
arbitrary leaf node in T, thus maintaining the property of a full tree. The
attachment leaf node becomes in internal node.
Use structural induction to show E = I + 1. Call this property P.
Proof by Structural Induction.
Basis: A tree of size 1 has 1 external node and 0 internal nodes. E=I+1. check.
IH. Assume P holds for some arbitrary tree T built by applying Rule 1. By
definition, when you call add2nodes() to T you add 2 external nodes and 1
external node becomes an internal node. Assuming P holds for T to begin with
we have this equation:
E_new = E_old - 1 + 2.
= E_old + 1.
I_new = I_old + 1.
Adding one to E_old and one to I_old maintains the original relationship, thus
P still holds. Since there is no other way to build a tree than to follow
Rule 1 we have proven P for all trees. Qed.
----------------------------------------------------------------------------
EXAMPLE.
A complete binary tree is a tree in which all levels of the tree are filled.
The height of such trees is defined as the number of nodes you cross from the
root to the leaf level. For a single node h = 1. It appears that the size of
these trees is 2^h - 1. For example, for height 3:
o
/ \ Size(h=3): 2^3 - 1 = 7.
o o
/ \ / \
o o o o
Use induction over the height of the tree to prove it.
Basis: A tree with 1 node is height 1. 2^1 - 1 = 1. check.
IH. Assume Size(k) = 2^k - 1, for height k.
IS. Show Size(k+1) = 2^(k+1) - 1, for height k+1.
By observation a tree of height k + 1 has Size(k) + Size(k) + 1 nodes. By IH,
Size(k) = 2^k - 1, for a tree of height k. Plug IH into our observation:
Size(k+1) = (2^k - 1) + (2^k - 1) + 1.
= 2(2^k - 1) + 1.
= 2(2^k - 1) + 1.
= 2^(k+1) - 2 + 1.
= 2^(k+1) - 1.