1. Suppose You Wish to Prove That the Following Is True for All Positive Integers N By

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)

(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.

(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)

(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.

(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): .

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

Ans: P(1): , which is true since both sides are equal to -1. P(k) ® P(k + 1):

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 for all n ³ 0.

Ans: P(0): , which is true since 1 = 1. P(k) ® P(k + 1): .

8. Use the Principle of Mathematical Induction to prove that for all n ³ 1.

Ans: P(1): , which is true since 1 = 1. P(k) ® P(k + 1):

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 for all positive integers n.

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

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: and sizes. Assuming that the supply of each size is infinite, prove that every border (n 7) can be covered with these tiles.

Ans: P(8): use one of each type. P(k) ® P(k + 1): If a tile is used as part of the covering of a strip, replace a tile with two tiles to cover a strip. Otherwise, the tiles for the strip must include three tiles; replace three of these with two tiles to cover a 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.

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.

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 for all n ³ 1.

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

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. .

Ans: an = an - 1, .

38. an = 21/2n.

Ans: , .