Deck 5: A: Induction and Recursion

Question 1

Suppose you wish to use mathematical induction to prove that: (a) Write P(1). (b) Write P(5). (c) Write P(k). (d) Write P(k + 1). (e) Use mathematical induction to prove that P(n) is true for all n ≥ 1.

Answer 1

Question 2

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

Answer 2

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.

Question 3

Use mathematical induction to prove that for all

Answer 3

P(0): 4 1-1 is true since 4 0 . https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/. each term is divisible by

Question 4

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

Question 5

Use mathematical induction to prove that

Question 6

Let

Question 7

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

Question 8

Use mathematical induction to prove that

Question 9

Use mathematical induction to prove that

Question 10

Use mathematical induction to prove that

Question 11

Use mathematical induction to prove that integers n.

Question 12

Use mathematical induction to prove that

Question 13

Use mathematical induction to prove that

Question 14

Use mathematical induction to prove that

Question 15

Suppose you wish to prove that the following is true for all positive integers n by using mathematical induction:
1+3+5+...+(2 n-1)=n²
(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 mathematical induction to prove that P(n) is true for all positive integers n.

Question 16

Suppose that the only paper money consists of 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.

Question 17

A T -omino is a tile pictured at the right. Prove that every chessboard can be tiled with T-ominoes.

Question 18

Prove that

Question 19

Use mathematical induction to prove that

Question 20

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 can be covered with these tiles.

Question 21

give a recursive definition (with initial condition(s)) of

Question 22

give a recursive definition with initial condition(s).
The set {1, 5, 9, 13, 17, . . .}

Question 23

Prove that for all https://d2lvgg3v3hfg70.cloudfront.net/TB6843/.

Question 24

Prove that the distributive law is true for all

Question 25

Use mathematical induction to prove that for all

Question 26

give a recursive definition (with initial condition(s)) of

Question 27

give a recursive definition (with initial condition(s)) of

Question 28

give a recursive definition with initial condition(s).
The function

Question 29

give a recursive definition (with initial condition(s)) of

Question 30

give a recursive definition with initial condition(s).
The sequence

Question 31

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
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
is true. Hence P(n) is true for all positive integers n ."

Question 32

give a recursive definition (with initial condition(s)) of

Question 33

give a recursive definition with initial condition(s).
The set {. . . , −4, −2, 0, 2, 4, 6, . . .}

Question 34

give a recursive definition with initial condition(s).
The function

Question 35

give a recursive definition (with initial condition(s)) of

Question 36

give a recursive definition with initial condition(s).
The set {1, 1/3, 1/9, 1/27, . . .}

Question 37

give a recursive definition with initial condition(s).
The function

Question 38

Let S be the set of positive integers defined by:
Basis step: 4 S .
Recursive step: If n 11ecb3f6_226e_1945_8ce8_8160bc243d3a_TB6843_11 S , then and 11ecb3f6_4662_3346_8ce8_7d38df65e052_TB6843_11
(a) Show that if , then (mod 6).
(b) Show that there exists an integer (mod 6) that does not belong to

Question 39

give a recursive definition with initial condition(s).
The set {0, 3, 6, 9, . . .}

Question 40

give a recursive definition with initial condition(s).
The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, . . .

Question 41

give a recursive definition with initial condition(s) of the set S .
{. . . , −5, −3, −1, 1, 3, 5, . . .}

Question 42

give a recursive definition with initial condition(s) of the set S .
{3, 7, 11, 15, 19, 23, . . .}

Question 43

Verify that the following program segment is correct with respect to the initial assertion T and the final A

Question 44

Suppose {an} is defined recursively by an = a2n−1 − 1 and that a0 = 2. Find a3 and a4.

Question 45

Find f(2) and f(3) if f(n) = f(n − 1) · f(n − 2) + 1, f(0) = 1, f(1) = 4.

Question 46

Consider the following program segment: Let p be the proposition Use mathematical induction to prove that p is a loop invariant.

Question 47

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

Question 48

Verify that the program segment is correct with respect to the initial assertion c = 3 and the final assertion b = 5.

Question 49

Find and if

Question 50

give a recursive definition with initial condition(s) of the set S .
All positive integer multiples of 5

Question 51

give a recursive definition with initial condition(s) of the set S .
The set of strings 1, 111, 11111, 1111111, . . .