UVa 900

From Algorithmist

Very trivial. The formula is the fibonacci sequence.

To prove it, let f_n be the number of ways to assembly a wall of length n.

There are two ways of assembling a wall of size n. We either place a vertical bar at its beginning and assemble a wall of length n - 1 or we place two horizontal bars on top of one another and assemble then a wall of length n - 2. That is,

f_n: = f_{n - 1} + f_{n - 2}.

That would be it except for the lack of reference to the base cases. To assemble a wall of length 0, we can only do nothing, leaving us only one possibility. To do it to a one space wall, only one way is left to us too: put a vertical bar there. Then

--Schultz 21:20, 26 May 2007 (EDT)