80-310/610 Logic and Computation Fall 2001

Homework #2

Due Wednesday, September 5

Note that a star (⋆) next to a problem means that you are required to turn in a written solution. A circle (∘) next to a problem means that this problem is for your edification and entertainment. You should do the remaining problems; though you do not have to turn in written solutions, they are fair game for the exams.

1. Read section 1.1 of the van Dalen text (and section 1.2 if you have time).

2. Use the least element principle to prove the induction principle, and vice-versa.

3. ⋆ Prove by induction that ∑_{i=0}^{n} 2^{i} = 2^{n+1} − 1. Keep in mind that ∑_{i=0}^{n} 2^{i} is an abbrevation for 2^{0} + 2^{1} + 2^{2} + … + 2^{n}.

4. ∘ Can you find a formula for ∑_{i=0}^{n} i^{2}?

5. Prove by induction that whenever n ≥ 4, n! > 2^{n}. Recall that n!, read “n factorial,” is defined to be n · (n − 1) · . . . · 1.

6. ⋆ Prove by induction that whenever n ≥ 5, 2^{n} > n^{2}.

7. ⋆ A “binary string of length n” is a sequence of n 0’s and 1’s; for example, 011101 is a binary string of length 6. Prove by induction that for every n there are 2^{n} binary strings of length n. How many binary strings are there having length at most n?

8. ⋆ Prove that there are 2^{n} subsets of a set having n elements. (Hint: you can use the preceding problem.)

9. Let “HiLo” be the following children’s game: Player 1 picks a natural number between 1 and M (inclusive), and Player 2 tries to guess it. After each incorrect guess, Player 1 responds “higher” or “lower.” Assuming Player 2 has n guesses, what is the largest value of M for which there is an algorithm that guarantees success? Describe the algorithm, and use induction to prove that it works.

10. ∘ Show that the algorithm you gave in response to the previous question is optimal, i.e. for larger values of M there will be numbers for which the algorithm fails to determine the correct number after n guesses.

11. Use the least element principle to prove that all numbers are interesting.