1. Prove that P(A)=2A for any set A. 2. For which positive integers are the following propositional functions true? 1. P(1) is true. For all positive integers n,P(n)P(n+1). 2. P(1) is true. For all positive integers n,P(n)P(n+2). 3. P(1) and P(2) are true. For all positive integers n,P(n)P(n+2). 4. P(1) and P(2) are true. For all positive integers n,P(n) and P(n+1) imply P(n+2). 5. P(0) is true. For all positive integers n, P(0)P(1)P(n2)P(n1)P(n). 3. What is wrong with the following proof? Theorem: It is possible to form postage of three cents or more using just three cent and four cent stamps. Proof: Basis step: We can form postage of three cents with a single three cent. stamp and postage of four cents using a single four cent stamp. Inductive step: Assume that we can form postage of j cents for all nonnegative integers j with jk using just three cent and four cent stamps. We can then form postage of k+1 cents by replacing one three cent stamp with a four cent stamp or by replacing two four cent stamps by three three cent stamps. 4. Prove the following using strong induction: 1. Any amount of change over seven cents can be made out of three cent. and four cent coins. 2. Any positive integer n can be written as a sum of distinct powers of two. For example, 4=22 and 19=20+21+24. 1. Prove that P(A)=2A for any set A. 2. For which positive integers are the following propositional functions true? 1. P(1) is true. For all positive integers n,P(n)P(n+1). 2. P(1) is true. For all positive integers n,P(n)P(n+2). 3. P(1) and P(2) are true. For all positive integers n,P(n)P(n+2). 4. P(1) and P(2) are true. For all positive integers n,P(n) and P(n+1) imply P(n+2). 5. P(0) is true. For all positive integers n, P(0)P(1)P(n2)P(n1)P(n). 3. What is wrong with the following proof? Theorem: It is possible to form postage of three cents or more using just three cent and four cent stamps. Proof: Basis step: We can form postage of three cents with a single three cent. stamp and postage of four cents using a single four cent stamp. Inductive step: Assume that we can form postage of j cents for all nonnegative integers j with jk using just three cent and four cent stamps. We can then form postage of k+1 cents by replacing one three cent stamp with a four cent stamp or by replacing two four cent stamps by three three cent stamps. 4. Prove the following using strong induction: 1. Any amount of change over seven cents can be made out of three cent. and four cent coins. 2. Any positive integer n can be written as a sum of distinct powers of two. For example, 4=22 and 19=20+21+24
