Here's an example of why the Fibonacci numbers are the answer

What is the Fibonacci series?

One way to explain that the Fibonacci series is the correct answer is to show that the problem satisfies the three conditions of the Fibonacci (Recursive) Definition:

where f(n) now means "the number of solutions to the puzzle of size n".

On its own, the formula above is satisifed by many series that are not "the" Fibonacci numbers because we have not given any starting numbers.
For example, we could start with two 2's as the first pair in the series and then apply the formula above to get 2+2=4 as the next, (the series is now 2,2,4) and then 2+4=6 as the next one (the series is now 2,2,4,6) as so on to get:
[In fact, this particular series is closely related the "the" Fibonacci series 0,1,1,2,3,5,8,... - can you spot that relationship?]

So we will need starting values as well as the formula above.

So there are several ways to get the Fibonacci series but all of them involve the following: Wehave seen that both conditions must be true if the series is to be "the" Fibonacci series.

The Brick Wall Puzzle

For this puzzle, f(n) means "the number of patterns for walls of height 2 and length n" and the solutions we have at present are

walls of lengths 1,2,3

Two starting cases Usually it is quite easy to verify the STARTING CASES for a puzzle because we can find all the solutions and just count them.
For this puzzle we can show that f(1)=1 and that f(2)=2 as follows, using the picture of the solutions above:


There is just one pattern for a wall of length 1 (the single brick is placed upright), so f(1)=1.


There are 2 patterns if we have a wall of length 2 as we have seen in the diagrams of the puzzle page, so f(2)=2 "the number of patterns for walls of height 2 and length 2 is 2".

Now for the general case: f(n)=f(n-1)+f(n-2)

What about f(n) - the number of patterns for walls of height 2 and length n?
This is the general case and we must be sure that our reasoning applies to ALL n bigger than 1 (we have covered the two cases for not bigger than 1 above).

Consider what happens at the left end of the wall....

.... either there is a brick on its end
....or else there is a brick on its side - in which case there must be another one on top of it as there is no other way to make the height of 2.
There are no more cases and these two cases cover all possible ways of starting a wall of length bigger than 1.
Let's look at these two cases: So all the ways of finding walls of length n are covered by the two cases:
an upright brick first and then any pattern of length n-1
or else the two-flat-bricks followed by any pattern of length n-2.

So the number of patterns of length n is the sum of the number of patterns of length (n-1) and the number of patterns of length (n-2). In terms of the "f" notation in mathematics, we have

f(n) = f(n-1) + f(n-2) generally
and so the f(n) numbers are indeed the Fibonacci numbers!

With thanks to Mats Lofkvist for helping make this page more accurate.

Return to the Brick Wall Puzzle on the Fibonacci Puzzles page

© 1996-2006 Dr Ron Knott
updated: 13 February 2001