This problem shows that if you spot a pattern which correctly gives a sequence of answers for a few terms it may not always provide the right answer and it has to be proved that the result holds in general.

This 'pyramid' diagram shows all the results for the number of walks with 2, 4, 6, 8 and 10 steps. It shows that the formula suggested, which works for 2, 4, 6 and 8 steps and gives the sequence 1, 2, 5, 14, 41, ... , does not work for 10 steps. Many congratulations to Jessica Kilpatrick, Natasha Barnes Smith, Laura Starling and Katie Redman,at King Edward VI Upper School, Bury St Edmunds for this splendid diagram and very good solution. They also drew the 42 paths for 10 steps proving conclusively that the formula does not give the correct answer for 10 steps and you might like to try this for yourself.

Why does it work? The arrows show the possible directions for the walks, always from left to right. The number on each segment gives the number of possible routes which include that segment. At each junction (or node) the number of routes which can go along the segments on the right of the junction is given by the sum of the numbers of routes into the junction from the left. Applying this rule gives all the numbers shown in the diagram. The diagram can of course be extended for 12 or 14 steps or $2n$ steps for any whole number $n$.

From this pattern you could construct a spreadsheet to produce the sequence of Catalan numbers:

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...

The same sequence arises, in the question from June 2000 called One Basket , as the number of arrangements of $2n$ people posing for a photograph in height order in two rows.