#### Question 1: (5 marks)

You are a credit card user with two very simple rules. You are fortunate enough to receive a one month grace period but without fail, sometime near the beginning of each month you must pay 10% of the previous month's (not the month just completed) final balance (or else there are extremely high interest charges added (but you are smart enough to pay!)). In addition, you ALWAYS charge \$100 per month (new charges) to your card.

The sequence, {a_n}, we would like to know is the credit card balance owing at the end of each month from the time you got your card.

Part 1: Determine the values of a_0, a_1, a_2, a_3, a_4 (where a_0 is the amount you owe at the beginning of the first month).

Part 2: State a suitable recurrence relation together with an explanation for its validity.

I honestly don't understand why this was so hard to understand. At the beginning of July you receive a bill from the credit card company stating that your current balance is some amount and that the amount you must pay is equal to 10% of the account balance from the end of May (as above: the previous month and not the month just completed). During the month of July you first pay the amount it says you must pay and then you charge an additional \$100 to the credit card.

Part 1 Answer: a_0=0, a_1 = 100.
Thinking about a_2 breaks open the whole problem (if not just reading the previous paragraph)
At the beginning of the second month we receive our statement which says that our balance is 100 and we must pay \$0 because this is 10% of what we owed as of a month ago.
So a_2 = 200
In the third month we receive a statement saying our balance is \$200 and that we must pay 10% of the first month's balance:
so a_3 = 300 - .1(100) = 290

Finally a_4 = 290+100 - .1(200) = 390-40 = 350.

Part 2 Answer: It should be pretty clear that a_n = a_(n-1) + 100 - (.1)*(a_(n-2)).
Explanation: what happens during month n: we must pay 10% of the balance as of the end of month n-2 (hence (.1)*a_(n-2)) and we charge \$100 and our current balance is a_(n-1). Thus the balance as of the end of month n-1 is lowered by the payment of (.1)a_(n-2) and increased by the spending of \$100.

#### Question 2: (5 marks)

Consider the recurrence relation a_n = 4 a_{n-1} + 5 a_{n-2} for n > 1.

Part 1: Given that a_0= 4 and a_1=26, give an explicit solution for a_n in a form where the only unknown or variable is n (and which is valid for each non-negative integer n). Part 2: (YES or NO) Is there a solution to this same recurrence, i.e. a_n = 4 a_{n-1}+ 5a_{n-2}, which has a_0 = 0, a_1=4, and a_2 = 9?

Part 1 Answer: characteristic equation is r^2 - 4r - 5 = 0.

This factors as (r-5)(r+1)=0, hence r=5 and r=-1 are the roots.

We set a_n = A * 5^n + B * (-1)^n for all n, and we try to fulfill the initial conditions:

```   a_0 = A + B                     hence      4 = A + B
a_1 = A * (5)^1  + B * (-1)^1,  hence     26 = 5A - B

```
Solve for A,B. E.g. add the two equations together to yield 30=6A, hence A=5. Then plug in A=5 into one of the two equations to deduce that B=-1.

Final result: a_n = 5 * (5)^n + (-1) * (-1)^n.

Part 2 answer: Does a_0 = 0, a_1=4, and a_2 = 9 satisfy the equation: a_2 = 4 a_1 + 5a_0?

NO.

#### Question 1: (5 marks)

Consider the collection of sets (possibly empty) of integers which do NOT contain a consecutive pair, i.e. 1,2 or 23,24 etc. are not permitted to both be in the same set. Let S_n denote the number of such subsets of {1,2,... , n} .

Part 1: Explicitly find the values of S_0 , S_1 , S_2 , S_3 , S_4 .

Part 2: State a suitable recurrence relation for the sequence {S_n} together with an explanation for its validity.

Part 1 Answer: S_0 is the number of subsets of the empty set, hence it is equal to 1.

S_1 is the number of subsets of {1}, so it is equal to 2, namely the set {} and the set {1}.

S_2 is the number of subsets of {1,2} which do not have a consecutive pair: {}, {1}, {2}, so it is 3.

S_3 is the number of subset of {1,2,3} which satisfy the condition: hence it counts the following sets:
{}, {1}, {2}, {3}, {1,3}

S_4 counts the sets: {}, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}, i.e. S_4 = 8

Part 2 Answer: S_n counts the subsets of {1,2,..., n} and we want to see it in terms of the subsets of {1,2,..., n-1} or {1,2,..., n-2}.

Well as usual which sets can we add the singleton n to without introducing a consecutive pair. Obviously a set which does not have a consecutive pair and which does not have n-1 in it. This gives us S_(n-2) sets which have n in them. Also we can take any subset of {1,2,..., n-1} and NOT add n to it. This gives another S_(n-1) sets.

Answer: S_n = S_(n-1) + S_(n-2)

#### Question 2: (5 marks)

Consider the recurrence relation a_n = a_{n-1} + 5 a_{n-2} for n > 1 .

Part 1: Given that a_0= 1 and a_1=13 , give an explicit solution for a_n in a form where the only unknown or variable is n (and which is valid for each non-negative integer n ).

Part 2: (YES or NO) Is there a solution to this same recurrence, i.e. a_n = a_{n-1}+ 5a_{n-2} , which has a_0 = 2 , a_1=-19 , and a_2 = -9 ?

Characteristic equation: r^2 - r - 5 = 0 (Very sorry that 5 was supposed to have been a 6!?)

Quadratic formula will give the roots: 1/2 + (1/2)*SQRT(21) and 1/2 - (1/2)*SQRT(21)

The general solution: a_n = A * (1/2 + (1/2)*SQRT(21))^n + B * (1/2 - (1/2)*SQRT(21) )^n.

To satisfy the initial conditions we set:

```   a_0 = A + B         hence  1  = A + B
a_1 = A(1/2 + 1/2 SQRT(21)) + B(1/2 - 1/2 SQRT(21)
hence   13 = A(1/2 + 1/2 SQRT(21)) + B(1/2 - 1/2 SQRT(21))
```

(Full marks if you got to here and realized that you solve these two equations in two unknowns to find A, B). It's not that hard

From the first equation: B=1-A, so plug this for B into the second: (also for simplicity multiply second equation by 2)

26 = A(1+ SQRT(21)) + (1-A)(1-SQRT(21))

26 = A + A*SQRT(21) - A + A*SQRT(21) + (1-SQRT(21))

25 + SQRT(21) = 2A * SQRT(21), thus A = (25+SQRT(21))/2*SQRT(21).

Then B = SQRT(21) - 25 / 2*SQRT(21) (i.e. 1-A).

Solution: a_n = [ (25+SQRT(21))/2*SQRT(21)] * (1/2 + 1/2 * SQRT(21))^n + [ SQRT(21) - 25 / 2*SQRT(21) ] * (1/2 - 1/2 * SQRT(21) )^n.

Part 2 Answer: It really asks if a_2 = a_1 + 5 a_0 where a_0 = 2 , a_1=-19 , and a_2 = -9 ? YES

More detailed explanation: given the initial conditions there is a unique solution and it will satisfy the recurrence relation for n>1, hence a_2 will be -9 as required.