1. Verify that an = 6 is a solution to the recurrence relation an = 4an-1 - 3an-2

2. Find a recurrence relation with initial condition(s) satisfied by the sequence

an = 2n + 1

3. Prove that Nk is countable, where k is some ?xed positive integer.

4. Prove or disprove: If A is countable and B uncountable, then B -A is uncountable.

5. Solve the below questions.

a)  Find gcd(20!, 12!) and gcd(289, 2346) by directly finding the largest divisor of both numbers

b)  Find  lcm(20!,  12!)  and  lcm(289,  2346)  by  directly  finding  the  smallest

positive multiple of both numbers

c)  Suppose that the lcm of two numbers is 400 and their gcd is 10. If one of the numbers is 50, find the other number.

d)  Use the Euclidean Algorithm to find gcd(580, 50).

6.Either find an integer x such that x ≡ 2 (mod 6) and x ≡ 3 (mod 9) are both true, or else prove that there is no such integer.

7.  Find the result of the following arithmetic operations. (10101)2 + (1110)2

(10101)2 × (1001)2

8. Find the octal and hexadecimal expansions of the following integers. (2000)10

(1138)10