Suppose you owe 10 dollars to a friend. Each week you pay your friend at least 1 dollar back.

Question

Sometimes however you might pay your friend back 2 dollars in a week and other times you might pay your friend 5 dollars in a week. How many different payment sequences are possible? Here are a couple possible sequences:

1-1-1-1-1-1-1-1-1-1 , 5-5, 5-2-2-1, 2-2-1-5, etc.

Hint: Try to find a recursive function that answers this question for n-dollars and then use it on an n-value of 10.

Part b: Give another function to answer the first part o the question above, this time your function must NOT be recursive. Hint: Think about the counting theory.

Answer 1

a0 = 1

a1 = 1

an = an-1 + an-2 n = 2,3,4

an = an-1 + an-2 +an-5 n >= 5

For n = 10, an = 128

The counting solution is the coefficient of xⁿ in ∑_k=0^∞ (x + x² + x⁵)^k , or

fⁿ(0)/n! , where f(x) = 1/(1 - x - x² - x⁵)