ECS 20 Discrete Math: Discussion 4 Mon 10/21/2013
Quiz 2 tomorrow & PS4
Q2: review PS1-3 and quiz 1, especially difficult questions, definitions from class
PS4 Q5: calculus may be used; Q8c ⫋ proper subset of, 𝐴 ⫋ 𝐵 means that 𝐴 is
a subset of but not equal to 𝐵
Mathematical Induction
To prove proposition 𝑃(𝑛) for all integers 𝑛 ≥ 𝑛0, prove the basis: 𝑛 = 𝑛0 is true Inductive step: suppose 𝑛 = 𝑘 is true, show 𝑛 = 𝑘 + 1 is true
1. Prove that 𝑛3 + 5𝑛 is divisible by 6 for every 𝑛 ≥ 1.
Basis:𝑛=1:6|13 +5(1)
Inductive step: suppose 𝑛 = 𝑘 is true, so 6 | 𝑘3 + 5𝑘 Check 𝑛 = 𝑘 + 1:
(𝑘 + 1)3 + 5(𝑘 + 1) = (𝑘3 + 3𝑘2 + 3𝑘 + 1) + (5𝑘 + 5) = (𝑘3 + 5𝑘) + (3𝑘2 + 3𝑘 + 6)
=(𝑘3 +5𝑘)+3𝑘(𝑘+1)+6
From the inductive hypothesis, 6 | (𝑘3 + 5𝑘). 𝑘(𝑘 + 1) is even, so 6 | 3𝑘(𝑘 + 1),
and 6 | 6. Inductive step verified.
2. Prove that 8𝑛 − 3𝑛 is divisible by 5 for every 𝑛 ≥ 1.
Basis:𝑛=1:5|81 −31
Inductive step: suppose 𝑛 = 𝑘 is true, so 5 | 8𝑘 − 3𝑘 Check 𝑛 = 𝑘 + 1:
8𝑘+1 − 3𝑘+1 = 8 ∗ 8𝑘 − 3 ∗ 3𝑘
=8∗8𝑘 −3∗8𝑘 +3∗8𝑘 −3∗3𝑘
=(8−3)∗8𝑘 +3∗(8𝑘 −3𝑘)
=5∗8𝑘 +3∗(8𝑘 −3𝑘)
We know that 5 | 5 ∗ 8𝑘. From the inductive hypothesis, 5 | (8𝑘 − 3𝑘). Inductive
step verified.
3. Prove that 𝑛2 > 7𝑛 + 1 for all 𝑛 ≥ 8.
Basis: 𝑛 = 8: 64 > 56 + 1
Inductive step: suppose 𝑛 = 𝑘 is true, so 𝑘2 > 7𝑘 + 1 Check𝑛=𝑘+1,(𝑘+1)2 >7(𝑘+1)+1
LHS:(𝑘+1)2 =𝑘2 +2𝑘+1>(7𝑘+1)+2𝑘+1=7(𝑘+1)+1+(2𝑘−6) Since 𝑘 ≥ 8, 2𝑘 − 6 > 0 so LHS is greater than RHS, inductive step verified.
4. Induction on a definition An expression 𝐸 is defined as 𝐸 → < 𝑁𝑢𝑚𝑏𝑒𝑟 >
𝐸 → (𝐸 + 𝐸) | (𝐸 ∗ 𝐸) | (𝐸^𝐸) | ln(𝐸)
1
ECS 20 Discrete Math: Discussion 4 Mon 10/21/2013
Prove that an expression 𝐸 has the same number of ( and ).
Basis: 𝐸 = < 𝑁𝑢𝑚𝑏𝑒𝑟 >, 0 (‘s and )’s
Inductive step: suppose 𝑛 = 𝑘 is true, 𝐸𝑘 has the same number of ( and ). Check𝑛=𝑘+1,𝐸𝑘+1 :
Take on either the form (𝐸 + 𝐸) | (𝐸 ∗ 𝐸) | (𝐸^𝐸) | ln(𝐸), all of which contain an equal number of ( and ). Inductive step verified.
Strong vs. Weak Induction
method so far is sometimes called weak induction, 𝑃(𝑘) → 𝑃(𝑘 + 1)
strong induction shows (∀𝑛)𝑃(𝑛) by showing 𝑃(1) ∧ … ∧ 𝑃(𝑘) → 𝑃(𝑘 + 1)
both approaches are equally “strong”, strong induction is easier for certain
proofs, such as PS4 Q6
5. Prove that 𝑎𝑛 ≤ 2𝑛 for the sequence 𝑎0 = 1, 𝑎1 = 2, 𝑎2 = 3, 𝑎𝑖 = 𝑎𝑖 + 𝑎𝑖−1 + 𝑎𝑖−2 Basis: 𝑛 = 0,1,2 true because 1 ≤ 20, 2 ≤ 21, 3 ≤ 22
Inductive step: assume 𝑛 = 0…(𝑘 − 1) is true, show that 𝑛 = 𝑘 is true
i.e. show that 𝑃(𝑘) = 𝑎𝑘 ≤ 2𝑘
𝑎𝑘 = 𝑎𝑘−1 + 𝑎𝑘−2 + 𝑎𝑘−3 ≤ 2𝑘−1 + 2𝑘−2 + 2𝑘−3
≤20 +21 +⋯+2𝑘−3 +2𝑘−2 +2𝑘−1 Geometric series: ≤ 2𝑘 − 1 ≤ 2𝑘
Envelope substitution question
A store sells envelopes in packages of 5 and 12. Prove that for ≥ 𝑛, the store can sell exactly 𝑛 envelopes. To find 𝑛 without trying every number, start with the smallest substitutions to make one more envelope (=inductive step).
The lowest substitution going from 5- to 12-packs is 7(5) → 3(12). This substitution needs at least 7 5-packs.
Consider the case with less than 7 5-packs, i.e. at most 6 5-packs (≤ 30). The lowest substitution going from 12- to 5-packs is 2(12) → 5(5). This substitution needs at least 2 12-packs (≥ 24).
To find 𝑛, we need only to check 30 < 𝑛 ≤ 54, since there will be numbers below 30 that cannot be achieved, and any number 54 or above will work for certain. We will find 𝑛 = 44 to be the first number beyond which all 𝑛 is satisfied.
We can also reverse the order of substitutions. In this example that would be checking 12 < 𝑛 ≤ 47, which also includes 𝑛 = 44.
Once 𝑛 is found, we can formally prove our hypothesis by induction using 𝑛 as the basis. 2