Math 574
Final Exam
Show All Work

1. Prove by induction: For n >= 1, f_3n is even, where f_k denotes the kth Fibonacci number.

2. (a). How many 3-element subsets are there of the 9-element set
   A = {1, 2, 3, 4, 5, 6, 7, 8, 9} Express your answer as a decimal.
   
   (b). How many subsets (of any size) of A contain exactly 3 odd integers?

3. The number of derangement's of n objects is given by
   D_n = (n-1)(D_n-1 + D_n-2) (n >=3) and D₁ = 0, D₂ = 1.
   How many derangements are there of 6 objects?

4. (a). How many ways are there to arrange 6 A's 9'B's and 4 C's in a row.
   (b). Answer (a) if no two A's are to be adjacent.

5. (a). If G is a plane graph on 12 vertices and 24 edges, then G has _____ regions.
   
   (b). If G is a graph having 8 vertices of degree 3 and 6 vertices of degree 5, then G has ____ edges.
   

6. How many arrangements of {1, 2, 3, 4, 5, 6, 7, 8, 9} have no even integer in its proper position?
   

7. Suppose a dozen eggs are painted using the colors red, blue, green and yellow.
   Each color must be used for at least one egg. How many ways are there to color the eggs?
   (Example: 3 red, 3 blue, 2 green, and 4 yellow or 5 red, 2 blue, 2 green, and 3 yellow)
   

8. (a). Let a_n denote the number of sequences of {a, b, c, d, e, 1, 2, 3, 4} of length n in which no two numbers are adjacent. (Example: db5c3d4eea2 ) Determine a recurrence relation for a_n along with appropriate initial conditions.
   
   (b). Let a_n denote the number of sequences of {1, 2, 3, 4} of length n in which no 2 appears to the right of a 1. (so once a 1 appears, only 1's, 3's and 4's can follow)
   Determine a recurrence relation for a_n along with appropriate initial conditions.
   

9. Suppose that a sequence of numbers is defined by
                   a_n = 5a_n-1 - 3a_n-2 , (n>=3) a₀ = 1, a₁ =2.
   Find the generating function for a_n.
   (Express your answer as a simplified rational function. )
   

10. Let a_n = 9a_n-1 - 14a_n-2 and a₀ = 4, a₁ = 13. Find a closed-form formula for a_n using the characteristic equation.

11. (a). How many graphs are there on {1, 2, 3, 4, 5, 6 } in which 2 is adjacent to 5, and 6 is not adjacent to 3.
    
    (b). If G is a tree on 8 vertices, explain how you know that the complement of G can not be a planar graph. (Hint: How many edges in G? in the complement of G?
    How many edges can three be in a planar graph on 8 vertices?)
    

12. How many permutations are there of a, b, c, d, e, f and g in which b, c, d must appear together in some order?
    

13. Consider the relation R = { (a, b), (a, a), (c, c), (c, a), (a, c) } on {a, b, c}. Then R is:
    
    not Reflexive since                not Symmetric since
    
    
    not Antisymmetric since                not Transitive since

14. How many ways are there to place 4 (identical) red marbles and 8 (identical) blue marbles into 12 distinct boxes? (Hint: Place the red marbles first)
    

15. (a). Let a_n have the generating function . Let .
    Find the generating function for c_n. Express your answer as a simplified rational function.
    
    
    (b). Suppose that the generating function for a_n is .
    What is the value of a₈?
    

16. Express the answer to each of the following integer equations as the coefficient of some power of x in the expansion of some rational function - but do not solve further.
            (a). x₁ + x₂ + x₃ + x₄ <= 20 0 <= x_i <= 8
    
            (b). x₁ + x₂ + x₃ + x₄ = 12 x₁ is even, 0 <= x₂ <= 4, 0 <= x₃, 0 <= x₄.
    

17. If ten fair coins are flipped, what is the probability they show exactly 5 heads?
    

18. (a). If 17 cards are drawn at random from a standard deck of 52, what is the probability that they consist of 5 of one suit, 5 of a second suit, 4 of a third suit and 3 of a fourth suit? (Example: 5 hearts, 5 diamonds, 4 clubs and 3 spades.)
    
    (b). Suppose that 5 cards are drawn from a standard deck of 52, what is the probability that they consist of at most two suits?
    (Example: 5 hearts or 3 spades, 2 clubs or 4 diamonds, 1 heart))
    

19. (a). What is the coefficient of x¹⁰ in the expansion of (1 + x + x² + x³)¹⁰?
    
    (b). What is the coefficient of x³ in the expansion of (1 + 2x + 3x² +4x³)⁸?
    

20. Prove log₃5 is not a rational number.

    
    

Extra Credit (hard): Show that any sequence of 32 letters consisting of only a's, b's, c's, d's, and e's must contain a consecutive block of letters in which each of a, b, c, d, and e appears an even number of times.