Community College of Philadelphia



1. Suppose you wish to prove that the following is true for all positive integers n by using the Principle of Mathematical Induction: 1 + 3 + 5 + ... + (2n − 1) ’ n2.

(a) Write P(1)

(b) Write P(72)

(c) Write P(73)

(d) Use P(72) to prove P(73)

(e) Write P(k)

(f) Write P(k + 1)

(g) Use the Principle of Mathematical Induction to prove that P(n) is true for all positive integers n

Ans: (a) 1 ’ 12.

(b) 1 + 3 + 5 + ... + 143 ’ 722.

(c) 1 + 3 + 5 + ... + 145 ’ 732.

(d) 1 + 3 + 5 + ... + 145 ’ (1 + 3 + 5 + ... + 143) + 145 ’ 722 + 145 ’ 722 + 2 ⋅ 72 + 1 ’ (72 + 1)2 ’ 732.

(e) 1 + 3 + ... + (2k − 1) ’ k2.

(f) 1 + 3 + ... + (2k + 1) ’ (k + 1)2.

(g) P(1) is true since 1 ’ 12. P(k) → P(k + 1): 1 + 3 + ... + (2k + 1) ’ k2 + (2k + 1) ’ (k + 1)2.

2. Suppose you wish to use the Principle of Mathematical Induction to prove that 1 ⋅ 1! + 2 ⋅ 2! + 3 ⋅ 3! + ... + n ⋅ n! ’ (n + 1)! − 1 for all n ≥ 1.

(a) Write P(1)

(b) Write P(5)

(c) Write P(k)

(d) Write P(k + 1)

(e) Use the Principle of Mathematical Induction to prove that P(n) is true for all n ≥ 1

Ans: (a) 1 ⋅ 1! ’ 2! − 1.

(b) 1 ⋅ 1! + 2 ⋅ 2! + ... + 5 ⋅ 5! ’ 6! − 1.

(c) 1 ⋅ 1! + 2 ⋅ 2! + ... + k ⋅ k! ’ (k + 1)! − 1.

(d) 1 ⋅ 1! + 2 ⋅ 2! + ... + (k + 1)(k + 1)! ’ (k + 2)! − 1.

(e) P(1) is true since 1 ⋅ 1! ’ 1 and 2! − 1 ’ 1. P(k) → P(k + 1): [pic] .

3. Use the Principle of Mathematical Induction to prove that [pic] for all positive integers n.

Ans: P(1): [pic] , which is true since both sides are equal to −1. P(k) → P(k + 1): [pic]

[pic].

4. Use the Principle of Mathematical Induction to prove that 1 + 2n ≤ 3n for all n ≥ 1.

Ans: P(1): 1 + 21 ≤ 31, which is true since both sides are equal to 3. P(k) → P(k + 1): 1 + 2k + 1 ’ (1 + 2k) + 2k ≤ 3k + 2k ≤ 3k + 3k ’ 2 ⋅ 3k < 3 ⋅ 3k ’ 3k + 1.

5. Use the Principle of Mathematical Induction to prove that n3 > n2 + 3 for all n ≥ 2.

Ans: P(2): 23 > 22 + 3 is true since 8 > 7. P(k) → P(k + 1): (k + 1)2 + 3 ’ k2 + 2k + 1 + 3 ’ (k2 + 3) + 2k + 1 < k3 + 2k + 1 ≤ k3 + 3k ≤ k3 + 3k2 + 3k + 1 ’ (k + 1)3.

6. Use the Principle of Mathematical Induction to prove that 2 | (n2 + n) for all n ≥ 0.

Ans: P(0): 2 | 02 + 0, which is true since 2 | 0. P(k) → P(k + 1): (k + 1)2 + (k + 1) ’ (k2 + k) + 2(k + 1), which is divisible by 2 since 2 | k2 + k and 2 | 2(k + 1).

7. Use the Principle of Mathematical Induction to prove that [pic] for all n ≥ 0.

Ans: P(0): [pic] , which is true since 1 ’ 1. P(k) → P(k + 1): [pic].

8. Use the Principle of Mathematical Induction to prove that [pic] for all n ≥ 1.

Ans: P(1): [pic] , which is true since 1 ’ 1. P(k) → P(k + 1): [pic]

9. Use the Principle of Mathematical Induction to prove that 2 | (n2 + 3n) for all n ≥ 1.

Ans: P(1): 2 | 12 + 3 ⋅ 1, which is true since 2 | 4. P(k) → P(k + 1): (k + 1)2 + 3(k + 1) ’ (k2 + 3k) + 2(k + 2), which is divisible by 2 since 2 | k2 + 3k and 2 | 2(k + 2).

10. Use the Principle of Mathematical Induction to prove that 2n + 3 ≤ 2n for all n ≥ 4.

Ans: P(4): 2 ⋅ 4 + 3 ≤ 24, which is true since 11 ≤ 16. P(k) → P(k + 1): 2(k + 1) + 3 ’ (2k + 3) + 2 ≤ 2k + 2 ≤ 2k + 2k ’ 2k + 1.

11. Use the Principle of Mathematical Induction to prove that 3 | (n3 + 3n2 + 2n) for all n ≥ 1.

Ans: P(1): 3 | 13 + 3 ⋅ 12 + 2 ⋅ 1, which is true since 3 | 6. P(k) → P(k + 1): (k + 1)3 + 3(k + 1)2 + 2(k + 1) ’ (k3 + 3k2 + 2k) + 3(k2 + 3k + 2), which is divisible by 3 since each of the two terms is divisible by 3.

12. Use the Principle of Mathematical Induction to prove that any integer amount of postage from 18 cents on up can be made from an infinite supply of 4-cent and 7-cent stamps.

Ans: P(18): use one 4-cent stamp and two 7-cent stamps. P(k) → P(k + 1): if a pile of stamps for k cents postage has a 7-cent stamp, replace one 7-cent stamp with two 4-cent stamps; if the pile contains only 4-cent stamps (there must be at least five of them), replace five 4-cent stamps with three 7-cent stamps.

13. Suppose that the only currency were 3-dollar bills and 10-dollar bills. Show that any dollar amount greater than 17 dollars could be made from a combination of these bills.

Ans: P(18): Eighteen dollars can be made using six 3-dollar bills. P(k) → P(k + 1): Suppose that k dollars can be formed, for some k ≥ 18. If at least two 10-dollar bills are used, replace them by seven 3-dollar bills to form k + 1 dollars. Otherwise (that is, at most one 10-dollar bill is used), at least three 3-dollar bills are being used, and three of them can be replaced by one 10-dollar bill to form k + 1 dollars.

14. Use mathematical induction to prove that every amount of postage of six cents or more can be formed using 3-cent and 4-cent stamps.

Ans: P(6): Six cents postage can be made from two 3-cent stamps. P(k) → P(k + 1): either replace a 3-cent stamp by a 4-cent stamp or else (if there are only 4-cent stamps in the pile of stamps making k cents postage) replace two 4-cent stamps by three 3-cent stamps.

15. Prove that [pic] for all positive integers n.

Ans: The basis case holds since [pic] . Now assume that [pic] for some k. It follows that [pic].

16. Use mathematical induction to show that n lines in the plane passing through the same point divide the plane into 2n regions.

Ans: The basis step follows since one line divides the plane into 2 regions. Now assume that k lines passing through the same point divide the plane into 2k regions. Adding the (k + 1)st line splits exactly two of these regions into two parts each. Hence k + 1 concurrent lines split the plane into 2k + 2 ’ 2(k + 1) regions.

17. Let a1 ’ 2, a2 ’ 9, and an ’ 2an − 1 + 3an − 2 for n ≥ 3. Show that an ≤ 3n for all positive integers n.

Ans: Let P(n) be the proposition that an ≤ 3n. The proof uses the Second Principle of Mathematical Induction. The basis step follows since a1 ’ 2 ≤ 3 ’ 31 and a2 ’ 9 ≤ 9 ’ 32. Now assume that P(k) is true for all k such that 1 ≤ k < n. Then ak ≤ 3k for 1 ≤ k < n. Hence an ’ 2an − 1 + 3an − 2 ≤ 2 ⋅ 3n − 1 + 3 ⋅ 3n − 2 ’ 2 ⋅ 3n − 1 + 3n − 1 ’ 3 ⋅ 3n − 1 ’ 3n.

18. Floor borders one foot wide and of varying lengths are to be covered with nonoverlapping tiles that are available in two sizes: [pic] and [pic] sizes. Assuming that the supply of each size is infinite, prove that every [pic] border (n > 7) can be covered with these tiles.

Ans: P(8): use one of each type. P(k) → P(k + 1): If a [pic] tile is used as part of the covering of a [pic] strip, replace a [pic] tile with two [pic] tiles to cover a [pic] strip. Otherwise, the tiles for the [pic] strip must include three [pic] tiles; replace three of these with two [pic] tiles to cover a [pic] strip.

19. A T-omino is the tile that is pictured below. Prove that every 2n × 2n(n > 1) chessboard can be tiled with T-ominoes.

[pic]

Ans: P(2): The figure below shows a tiling of a 4 × 4 board.

P(k) → P(k + 1): Divide the 2k + 1 × 2k + 1 board into four quarters,

each of which is a 2k × 2k board. P(k) guarantees that each of these

four 2k × 2k boards can be tiled. Put these four tiled boards together

to obtain a tiling for the 2k + 1 × 2k + 1 board.

[pic]

20. Use the Principle of Mathematical Induction to prove that 4 | (9n − 5n) for all n ≥ 0.

Ans: P(0): 4 | 1 − 1 is true since 4 | 0. P(k) → P(k + 1): 9k + 1 − 5k + 1 ’ 9(9k − 5k) + 5k(9 − 5). Each term is divisible by 4: 4 | 9k − 5k (by P(k)) and 4 | 9 − 5.

21. Use the Principle of Mathematical Induction to prove that 5 | (7n − 2n) for all n ≥ 0.

Ans: P(1): 5 | 7 − 2 is true since 5 | 5. P(k) → P(k + 1): 7k + 1 − 2k + 1 ’ 7(7k − 2k) + 2k(7 − 2). Each term is divisible by 5: 5 | 7k − 2k (by P(k)) and 5 | 7 − 2.

22. Prove that the distributive law A1 ∩ (A2 ∪ ... ∪ An) ’ (A1 ∩ A2) ∪ ... ∪ (A1 ∩ An) is true for all n ≥ 3.

Ans: The second form of mathematical induction is used. P(3) is true since it is the ordinary distributive law for intersection over union. P(3) ∧ ... ∧ P(n) → P(n + 1): A1 ∩ (A2 ∪ ... ∪ An + 1) ’ A1 ∩ ((A2 ∪ ... ∪ An) ∪ An + 1) ’ [A1 ∩ (A2 ∪ ... ∪ An)] ∪ (A1 ∩ An + 1) ’ [(A1 ∩ A2) ∪ ... ∪ (A1 ∩ An)] ∪ (A1 ∩ An + 1) ’ (A1 ∩ A2) ∪ ... ∪ (A1 ∩ An + 1).

23. Prove that [pic] for all n ≥ 1.

Ans: P(1): [pic] , which is true since the right side is equal to 1/2. P(k) → P(k + 1): [pic]

24. Find the error in the following proof of this “theorem”:

“Theorem: Every positive integer equals the next largest positive integer.”

“ Proof: Let P(n) be the proposition 'n ’ n + 1'. To show that P(k) → P(k + 1), assume that P(k) is true for some k, so that k ’ k + 1. Add 1 to both sides of this equation to obtain k + 1 ’ k + 2, which is P(k + 1). Therefore P(k) → P(k + 1) is true. Hence P(n) is true for all positive integers n.”

Ans: No basis case has been shown.

Use the following to answer questions 25-33:

In the questions below give a recursive definition with initial condition(s).

25. The function f (n) = 2n, n = 1, 2, 3, ....

Ans: f (n) = 2f (n - 1), f (1) = 2.

26. The function f (n) = n!, n = 0, 1, 2, ....

Ans: f (n) = nf (n - 1), f (0) = 1.

27. The function f (n) = 5n + 2, n = 1, 2, 3, ....

Ans: f (n) = f (n - 1) + 5, f (1) = 7.

28. The sequence a1 ’ 16, a2 ’ 13, a3 ’ 10, a4 ’ 7, ….

Ans: an ’ an − 1 − 3, a1 ’ 16.

29. The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, ….

Ans: an ’ an − 1 + an − 2, a1 ’ 1, a2 ’ 1.

30. The set {0,3,6,9,…}.

Ans: 0 ∈ S; x ∈ S → x + 3 ∈ S.

31. The set {1,5,9,13,17,…}.

Ans: 1 ∈ S; x ∈ S → x + 4 ∈ S.

32. The set {1,1/3,1/9,1/27,…}.

Ans: 1 ∈ S; x ∈ S → x/3 ∈ S.

33. The set {…,−4,−2,0,2,4,6,…}.

Ans: 0 ∈ S; x ∈ S → x ± 2 ∈ S.

Use the following to answer questions 34-39:

In the questions below give a recursive definition (with initial condition(s)) of {an} (n ’ 1,2,3,…).

34. an ’ 2n.

Ans: an ’ 2an − 1, a1 ’ 2.

35. an ’ 3n − 5.

Ans: an ’ an − 1 + 3, a1 ’ −2.

36. an ’ (n + 1)/3.

Ans: an ’ an − 1 + 1/3, a1 ’ 2/3.

37. [pic].

Ans: an ’ an − 1, [pic].

38. an ’ 21/2n.

Ans: [pic] , [pic].

39. an ’ n2 + n.

Ans: an ’ an − 1 + 2n, a1 ’ 2.

Use the following to answer questions 40-44:

In the questions below give a recursive definition with initial condition(s) of the set S.

40. {3,7,11,15,19,23,…}.

Ans: 3 ∈ S; x ∈ S → x + 4 ∈ S.

41. All positive integer multiples of 5.

Ans: 5 ∈ S; x ∈ S → x + 5 ∈ S.

42. {…,−5,−3,−1,1,3,5,…}.

Ans: 1 ∈ S; x ∈ S → x ± 2 ∈ S.

43. {0.1,0.01,0.001,0.0001}.

Ans: 0.1 ∈ S; x ∈ S → x/10 ∈ S.

44. The set of strings 1,111,11111,1111111,….

Ans: 1 ∈ S; x ∈ S → x11 ∈ S (or x ∈ S → 100x + 11 ∈ S).

45. Find f (2) and f (3) if f (n) ’ 2f (n − 1) + 6, f (0) ’ 3.

Ans: f (2) ’ 30, f (3) ’ 66.

46. Find f (2) and f (3) if f (n) ’ f (n − 1) ⋅ f (n − 2) + 1, f (0) ’ 1, f (1) ’ 4.

Ans: f (2) ’ 5, f (3) ’ 21.

47. Find f (2) and f (3) if f (n) ’ f (n − 1) / f (n − 2), f (0) ’ 2, f (1) ’ 5.

Ans: f (2) ’ 5/2, f (3) ’ 1/2.

48. Suppose {an} is defined recursively by [pic] and that a0 ’ 2. Find a3 and a4.

Ans: a3 ’ 63 and a4 ’ 3,968.

49. Give a recursive algorithm for computing na, where n is a positive integer and a is a real number.

Ans: The following procedure computes na:

procedure mult(a: real number, n: positive integer)

if n ’ 1 then mult(a,n) : ’ a

else mult(a,n) : ’ a + mult(a,n − 1).

50. Describe a recursive algorithm for computing 32n where n is a nonnegative integer.

Ans: The following procedure computes 32n:

procedure power(n: nonnegative integer)

if n ’ 0 then power(n) : ’ 3

else power(n) : ’ power(n − 1) ⋅ power(n − 1).

51. Verify that the program segment

a : ’ 2

b : ’ a + c

is correct with respect to the initial assertion c ’ 3 and the final assertion b ’ 5.

Ans: Suppose c ’ 3. The program segment assigns 2 to a and then assigns a + c ’ 2 + 3 ’ 5 to b.

52. Consider the following program segment:

i : ’ 1

total : ’ 1

while i < n

begin

i : ’ i + 1

total : ’ total + i

end.

Let p be the proposition “[pic] and i ≤ n.” Use mathematical induction to prove that p is a loop invariant.

Ans: Before the loop is entered p is true since [pic] and i ≤ n. Suppose p is true and i < n after an execution of the loop. Suppose that the while loop is executed again. The variable i is incremented by 1, and hence i ≤ n. The variable total was [pic], which now becomes [pic]. Hence p is a loop invariant.

53. Verify that the following program segment:

if x ≤ y then

max : ’ y

else

max : ’ x.

is correct with respect to the initial assertion T and the final assertion (x ≤ y ∧ max ’ y) ∨ (x > y ∧ max ’ x).

Ans: If x < y initially, max is set equal to y, so (x ≤ y ∧ max = y) is true. If x = y initially , max is set equal to y, so (x ≤ y ∧ max = y) is again true. If x > y, max is set equal to x, so (x > y ∧ max = y) is true.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download