Strong Induction

Strong Induction

ex. Show that for all integers n ≥ 14, n can be written as a sum of threes and eights.

Strong Mathematical Induction

Let P(n) be a predicate that is defined for integers n and let a and b be fixed integers with a ≤ b. Suppose

1. P(a), P(a +1),…, P(b) are all true.

2. For any integer k ≥ b, if P(i) is true for all integers i with

a ≤ i≤ k, then P(k+1) is true.

Then P(n) is true for all integers n ≥ a.

ex. Suppose c1, c2, … is a sequence such that c1 = 1, c2 = 3,

ck = ck-2 + 2ck-1 for all integers k ≥ 3. Prove that cn is odd for all integers n ≥ 1.

ex. Suppose g0, g1, g2. … is a sequence such that g0 = 12, g1 = 29,

gk = 5gk-1 – 6gk-2 for integers k ≥ 2. Prove that gn = 5(3n) + 7(2n) for all integers n ≥ 0.

Do:

1. Suppose b1, b2, b3, … is a sequence defined as b1 = 3, b2 = 6,

bk = bk - 2 + bk - 1 for all integers k ≥ 3. Prove bn is divisible by 3 for all integers n ≥ 1.

2. Suppose a0, a1, a2, a3, … is a sequence defined as a0 = a1 = a2 = 1 and ak = ak – 2 + ak – 3 for all integers k ≥ 3. Prove..

More problems

ex 4.4.1: Prove: Every integer greater than 1 is divisible by a prime.

ex: Prove: Every positive integer can be written uniquely in the form where r is a nonnegative integer, .

ex. You observe a line of people standing at a movie box-office. Everyone in the line is either a woman or a man, but not both. You notice that the first person in line is a woman and the last person in line is a man. Prove, using SMI, that somewhere in the line, a woman is standing directly in front of a man.

ex. Find, with proof by SMI, a recurrence formula for the number of distinct paths of length n feet using 1-foot boards and 2-foot boards.