MATH3U03 Assignment 1

Question 1. (1.2.7) Let Rn be the sequence defined by

R0 := 0,                             R1 := 1,                     Rn = 5Rn−1 − 6Rn−2 for n ≥ 2.

Show that Rn = 3n − 2 n .

Question 2. Here is a left-justified Pascal’s Triangle.

Observe that the sums of the diagonals are Fibonacci numbers. In other words, we have the relation

Use the first proof technique we introduced in class, and the interpretation of Fibonacci numbers counting tilings to establish this relation. Pose a question (“How many tilings...”), and answer it in two ways.

Hint: Think about the number of dominoes.

Question 3. (1.3.16) Let A and B be sets. Prove that A ∪ B = (A − (A ∩ B)) ∪ B.

Question 4.

(1.3.13) At a barbecue, each guest had either a hamburger or a hot dog, possibly both. Twenty-five guests had a hamburger, eighteen had a hot dog, and ten had both. How many guests were at the barbecue?

(1.4.7) Let A = [4] and B = [3]. Which of the following functions are injective? Which are onto B? Which are bijections from A to itself?

Question 5. (1.5.8) Suppose that Billie paints at least one picture per day and paints no more than 12/13 pictures per day over a period of 36 days. Show that there exists a period of consecutive days when they complete exactly 31 pictures.

Question 6.

(1.6.4) In chess, a king is attacking another piece if it is on an adjacent square. Find a recurrence relation and initial values for k(n), the number of ways of placing non-attacking kings on an n × 1 chessboard.

(1.6.7) Find a recurrence relation and initial values for W(n), the number of words of length n from the alphabet {a, b, c} with no adjacent a’s.