Question

6)a) A money launderer is illegally transferring money weekly to a particular offshore account. He transfers money in the following amounts: $1000, S2000, 83000, $5000, and $10000. To avoid suspicion by the authorities, he cannot transfer amounts larger than $5000 two weeks in a row. Find a recurrence relation for the number S_n, of different sequences of transfers he can make in n weeks.

b) What is S₁? S₂? Find these by inspection without using the recurrence relation.

c) Solve the recurrence relation. You do not need to find c₁ or c₂.

Answer 1

Part a)

Let and represent the number of sequences of transfers in n weeks that do not end in $5000 and that end in $5000 respectively.

Now, the total of sequences in n weeks is given as :

Now, the transfer in the nth week can be any of $1000, $2000, $83000, $10000 irrespective of the transfer in (n-1)th week. Thus,

Let us call this equation (1)

the transfer in the nth week can be $5000 only if the transfer in (n-1)th week is not $5000. Thus,

Also, using equation(1)

Thus the recurrence relation is:

Part(b)

In the first week the transaction can be any of the 5 values, thus S1 = 5

Possible number of sequences for 2 weeks = 5*5 = 25

The only sequence in which $5000 occurs twice in a row is $5000, $5000. Thus, the number of invalid sequences = 1

Thus, the number of valid sequences for two weeks = Total sequences - Invalid sequences = 25-1=24

Thus, S2=24

Part(c)

The recurrence relation is:

The characteristic equation is:

Thus, the recurrence relation is: