1. For all integers we define
(a) Find an explicit formula for
(b) Prove the correctness of the formula you obtain in (a) by mathematical induction.
2. Find an explicit formula for the sequence defined by the recurrence:
3. Find an explicit formula for the sequence defined by the recurrence:
4. Can you find a simple graph on 8 vertices that has an Euler circuit, but does not have a Hamiltonian circuit?
5. Is there a fully binary tree on 18 vertices? on 25 vertices? If your answer is ``Yes'', find the number of internal vertices. If your answer is ``No'', state why.
6. Are they isomorphic? If so, give a 1-1 edge-preserving correspondence from V(G) to V(H). If not, list one property that G has, but H does not.
7. Find a minimum spanning tree in the following graph.
(a) By Prim’s Algorithm. Start at the vertex b.
(b) By Kruskal’s Algorithm.
8. (a) How many cards must be selected from a standard deck of 52 cards to guarantee that at least 4 spades are chosen?
(b) How many cards must be selected from a standard deck of 52 cards to guarantee that at least 4 cards of the same suit are chosen?
9. (a) How many bit strings of length 8 are there which contain at most 3 ones?
(b) How many bit strings of length 8 are palindromes? A palindrome is a string which, when reversed it is identical to the original string, eg. 010010 is a palindrome.
10. Show that if there are 30 students in a class, then at least two have last names that begin with the same letter. [Hint: Generalized Pigeonhole Principle]
11. Find the coefficient of the term x2y4z5 in the expansion of ?
12. How many nonnegative integer solutions to the following system of inequalities ?
13. How many positive integers less than 1,000 have the sum of their digits equal to 25?
14. How many different 3-letter words (real or imaginary) can be formed from the...