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.

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 - BSolve 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.**

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)

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.