SOLUTION: Part a: Suppose you owe 10 dollars to a friend. Each week you pay your friend at least 1 dollar back. Sometimes however you might pay your friend back 2 dollars in a week and other

Question 1176883: Part a: Suppose you owe 10 dollars to a friend. Each week you pay your friend at least 1 dollar back. 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 part a, but this time your function must NOT be recursive. Hint: Think about the counting theory we learned this term.

Answer by CPhill(1959) (Show Source): You can put this solution on YOUR website!
Absolutely, let's break down this problem into parts.
**Part a: Recursive Function**
**1. Define the Recursive Function**
Let `f(n)` be the number of different payment sequences to pay back `n` dollars.
**2. Base Cases**
* `f(0) = 1` (If you owe 0 dollars, there's 1 way: do nothing.)
* `f(n) = 0` if `n < 0` (You can't pay back a negative amount.)
**3. Recursive Step**
To pay back `n` dollars, you can make the last payment 1, 2, or 5 dollars. So:
* `f(n) = f(n-1) + f(n-2) + f(n-5)`
**4. Calculate f(10)**
Let's compute the values iteratively:
* `f(0) = 1`
* `f(1) = f(0) = 1`
* `f(2) = f(1) + f(0) = 1 + 1 = 2`
* `f(3) = f(2) + f(1) = 2 + 1 = 3`
* `f(4) = f(3) + f(2) = 3 + 2 = 5`
* `f(5) = f(4) + f(3) + f(0) = 5 + 3 + 1 = 9`
* `f(6) = f(5) + f(4) + f(1) = 9 + 5 + 1 = 15`
* `f(7) = f(6) + f(5) + f(2) = 15 + 9 + 2 = 26`
* `f(8) = f(7) + f(6) + f(3) = 26 + 15 + 3 = 44`
* `f(9) = f(8) + f(7) + f(4) = 44 + 26 + 5 = 75`
* `f(10) = f(9) + f(8) + f(5) = 75 + 44 + 9 = 128`
**Answer (Part a):** There are 128 different payment sequences.
**Part b: Non-Recursive Function (Counting Theory)**
**1. Break Down the Problem**
We need to find the number of ways to express 10 as a sum of 1s, 2s, and 5s.
**2. Consider Possible Combinations**
We can systematically list the possible combinations:
* **Only 1s:** 10 ones (1 way)
* **Using 5s:**
* Two 5s (1 way)
* One 5:
* One 5, five 1s (1 way)
* One 5, two 2s, one 1 (number of ways to arrange them)
* **Using 2s (without 5s):**
* Five 2s (1 way)
* Four 2s, two 1s (number of ways to arrange them)
* Three 2s, four 1s (number of ways to arrange them)
* Two 2s, six 1s (number of ways to arrange them)
* One 2, eight 1s (number of ways to arrange them)
* Ten 1s (1 way)
**3. Use Combinations**
We'll use combinations to count the arrangements:
* **Two 5s:** 1 way
* **One 5:**
* One 5, five 1s: 6! / (5!1!) = 6 ways
* One 5, two 2s, one 1: 4! / (1!2!1!) = 12 ways
* **Only 2s:**
* Five 2s: 1 way
* Four 2s, two 1s: 6! / (4!2!) = 15 ways
* Three 2s, four 1s: 7! / (3!4!) = 35 ways
* Two 2s, six 1s: 8! / (2!6!) = 28 ways
* One 2, eight 1s: 9! / (1!8!) = 9 ways
* Ten 1s: 1 way
**4. Sum the Combinations**
1 + 6 + 12 + 1 + 15 + 35 + 28 + 9 + 1 = 128
**Answer (Part b):** There are 128 different payment sequences.
**Non-Recursive Function (Conceptual)**
More generally, you'd need to:
1. Enumerate all possible combinations of 1s, 2s, and 5s that sum to 10.
2. For each combination, use the multinomial coefficient formula to determine the number of distinct arrangements: `n! / (n1! * n2! * n3!)` where `n` is the total number of payments, and `n1`, `n2`, and `n3` are the numbers of 1s, 2s, and 5s, respectively.
3. Sum up the results from step 2.

RELATED QUESTIONS
you borrow $200 from a friend to help pay for a new laptop computer. you pay your friend... (answered by josmiceli)

You owe your friend $35. You work for 4 hours, earning $7 an hour. Did you make enough... (answered by josgarithmetic)

1. A friend of yours has a dog walking business. For every dog she walks she earns $5.... (answered by Boreal)

you begin with $90 in your savings account and your friend begins with $35 in her savings (answered by Danielshinmath)

On a road trip with a friend, you drive about 70 miles per hour and your friend drives 60 (answered by Theo)

You want to buy a computer but have no money. You borrow $1000 from your dad but you lose (answered by ankor@dixie-net.com)

You and a friend are 400 m away from school, walking together toward home at a speed of... (answered by mananth)

please help me answer the following question, showing all your work and at least 5... (answered by rothauserc,josgarithmetic)

You have 160 dollars and you receive 7 dollars a week. Your friend has 210 dollars and... (answered by JulietG)