I am building a set of sensor nodes which can communicate via a wireless radio. This means that the nodes must be addressed. Rather than assinging the address in software, I will add pin headers which can be jumped with 2-prong jumpers to create an address based off the jumper configuration (I know what you're thinking... yes, this really is a math problem).
So the conditions are:
- any pin may be left open
- Any two adjacent pins may be jumped
This lead me to wonder if there is a closed form way to count the number of addresses given the number of pins.
Note: This can be re-imagined as a tiling problem: "for a $1 \times n$ board, how many unique tilings are there using $1 \times 2$ tiles?"
I wrote down the first few values for the sequence fitting the above definition, and saw that it was the Fibonacci sequence (at least, the first 9 values match).
So my question is, is this observation correct? How to prove/explain the reason for this?
How many ways $f_n$ are there to cover a $1 \times n$ board with $1 \times 2$ tiles (where each space has the option to remain uncovered)? There are two cases: the first space is covered by a tile or it isn't. If it is, then you have the remaining $n - 2$ spaces to cover with tiles (the second space is also covered by your first $1 \times 2$ tile), and there are $f_{n-2}$ ways to do this. If the first space isn't covered, then you have the remaining $n - 1$ spaces to cover (or leave uncovered) with tiles, and there are $f_{n-1}$ ways to do this. Thus the total number of ways to tile the $1 \times n$ board is $f_n = f_{n-1} + f_{n-2}$. Since the $f_n$ satisfy the same recurrence relation that the Fibonacci numbers do, the numbers of tilings are the Fibonacci numbers.