Trains
How many different ways are there to build a train of length 12 using cars of length either 1 or 2?
I am in the business of constructing trains. A train is made up of a series of cars strung together. These cars are either 1 unit long or 2 units long. Here’s an example of a train of length 12.
Note that a train has a front and a back, so that the mirror image of the train we have just seen is counted as a separate train.
So how many trains of length 12 are there? There are lots of ways of answering this question and one of them is certainly listing all the possibilities! But here we develop the powerful idea of recursive thinking—discovering elegant ways to build long trains out of short trains. Early in the journey (who would have guessed?) the wonderful Fibonacci numbers appear.
But that’s just the beginning. Have you ever rounded a bend and there before your eyes is the most spectacular waterfall you have ever seen? Well take a look at the cascade on the right.
It suggests that the sum of the squares of two consecutive Fibonacci numbers is always a Fibonacci number. Well that’s true but it’s devilishly difficult to prove.
Just wait till you discover the “Trains” proof of this enticing result.
Finally we end this story with some wonderful “trains” problems that enhance the development of recursive thinking. One of these is the following.
A coin problem
A fair coin is tossed n times producing a sequence of heads and tails. Find the probability that the sequence has two consecutive heads for the first time on the last two tosses.