Math: a recursive function word problem
The tutor shares a solution to a problem from Grimaldi’s Discrete and Combinatorial Mathematics.
Last night I encountered the problem (p. 481) that paraphrases as follows:
Imagine a car takes two spaces, a motorbike one. Find a recursive function that determines the number of ways to fill n parking slots with motorbikes and cars (assuming no empty slots).
I played around with the problem for a while, then tried this approach:
| Number of slots | Ways to fill them |
| 0 | 1 (no parking at all) |
| 1 | 1 (one motorbike) |
| 2 | 2 (2 mbs or 1 car) |
| 3 | 3 (3 mbs or 1 car, 1 mb (two ways)) |
| 4 | 5 (4 mbs or 1 car, 2mbs (three ways) or 2 cars) |
The right column in the table above is the Fibonacci (F) sequence: an+2=an+1+an. However, it’s advanced by 1: Typically, F(0)=0, while for this case, F(0)=1. Fibonacci takes the previous number in the sequence, then adds it to the one before that, to give the current one.
In a coming post I’ll discuss the general solution to the sequence above:)
Source:
Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-Wesley, 1994.
Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.
Leave a Reply
You must be logged in to post a comment.