## 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)