Description
1. You have 2 parents, 4 grandparents, 8 great-grandparents, and so forth. If all of your
ancestors were distinct, what would be the total number of your ancestors for the
past 40 generations, counting your parent’s generation as number 1? Hint: What
kind of sequence is this? Use the sum formula for that sequence to solve the
problem. Show your work. (3 marks).
2. Give a proof by contradiction to show that there does not exist a constant c such
that for all integers n≥1, (n+1)2
-n2
3. Given the fact that ⌈x⌉ < x + 1, give a proof by contradiction that if n items are placed
in m boxes then at least one box must contain at least ceiling(n/m) items. (3 marks)
4. Use mathematical induction to prove the following statement is true for all integers
n≥2. Clearly identify the base case, the induction hypothesis and the induction step
you are using in your proof. (3 marks)
5. Use the Euclidian Algorithm (outlined in Epp pages 220 – 224) to hand-calculate the
greatest common denominator (gcd) of 832 and 10933 (2 marks)
6. Prove, by contraposition, that if (n(n-1) + 3(n-1) – 2) is even then n is odd. Assume
only the definition of odd/even. (3 marks)
7. Use mathematical induction to prove that
n
i=1 (5i-4)=n(5n−3)/2. Clearly identify
the base case, the induction Hypothesis and the induction step you are using in your
proof. (3 marks)
