1) Use a proof by cases to show that every perfect square is either a multiple of four or one more than a multiple of eight.

2) Use a proof by contradiction to show that in any group of 100 people, there must exist a group of nine or more them who were all born in the same month.

3) Use a constructive proof to show that there exists a sequence one million consecutive natural numbers, none of which is prime. Hint: The first number will be the factorial of something plus 2.

4) Prove by induction that n² 2ⁿ for any integer that's greater than or equal to 4.

5) Draw the state diagram for a finite automaton that recognizes base 10 numbers that are multiples of 3.

6) Describe the transition function for the automaton in question 5 using a table like is done for M1 on pg. 36. You'll need 10 columns since there are 10 symbols in the alphabet (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). You'll need as many rows as your automaton has states.

6) Sipser 1.4g

7) Sipser 1.5g

8) Sipser 1.6l