Important note: When writing your solutions, you must follow the guidelines below. The answers should be concise, clear and neat. When presenting proofs, every step should be justied. Assignments should be stapled or placed in an unsealed envelope. All questions carry equal marks. Substantial departures from the above guidelines will not be graded. Question 1: On the rst page of your assignment, write your name, student number, and course number COMP 2804. Question 2: A small computer network consists of 6 computers. Each computer is directly connected to 0 or more computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers. Is the statement true if we have 10 computers instead of 6? Question 3: Show that an = n2 + n + 1 satises a0 = 1 ak = ak1 + 2k for k > 0. (1) Question 4: Consider the following recursive function dened for positive values of n M (n) = if n > 100 n 10 M (M (n + 11)) if n 100 (2) Evaluate M (120), M (111), M (97), M (94). Do you observe something interesting for the value of M (n) for n 100? Question 5: Let dn denote the number of ways that n-letters can be put into n-envelopes so that no letter goes into the correct envelope. Show that d1 = 0, d2 = 1, d3 = 2, and in general for n 3, dn = (n 1)(dn1 + dn2 ). Question 6: Using induction for n 1, show that dn in the previous question can be expressed as 1 1 1 1 1 1 dn = n! + + + + (1)n . 0! 1! 2! 3! 4! n! 1 Question 7: Exercise 4.36 from the Course Text Book by Michiel Smid. Question 8: Give a recursive denition of the set of integers that are multiples of 3. Show that your denition indeed generates all the elements of the set {. . . , 9, 6, 3, 0, 3, 6, 9, . . .}. Question 9: Show that an = 1 rn+1 ,r = 1 1r satises the recurrence relation a0 = 1 ak = ak1 + rk for k > 0. (3) Question 10: A binary tree is - either one single node - or a node whose left subtree is a binary tee and whose right subtree is a binary tree. Show that any binary tree with n leaves has exactly 2n 1 nodes. Question 11: (Bonus Problem:) Assume you have a set A = {a1 , a2 , . . . , an+1 } of n + 1 positive numbers such that n+1 ai = 2n. Prove or disprove that for any integer k, where i=1 1 k 2n, we can always nd a subset B A such that the sum of elements of B equals k. 2