Deck 5: Induction and Recursion

Question 1

Answer 1

The basis step follows since one line divides the plane into 2 · 1 parts. For the inductive step assume that k lines passing through a point divide the plane into 2k parts. Suppose that we have k + 1 lines. If we take k of these lines, by the inductive hypothesis they divide the plane into 2k parts. Adding the (k+1)st line splits exactly two of these parts in two. Hence these k + 1 concurrent lines split the plane into 2k + 2 = 2 · (k + 1) parts. This completes the proof.

Question 2

Answer 2

Question 3

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

Answer 3

Question 4

Give a recursive algorithm for computing na using addition, where n is a positive integer and a is a real

Question 5

Question 6

What is wrong with the following proof that every positive integer equals the next larger positive integer?

Question 7

Question 8

Question 9

Question 10