A walk is made up of diagonal steps from left to right, starting at the origin and ending on the x-axis as in the example illustrated which shows 8 steps? How many paths are there for 4 steps, for 6 steps, for 8 steps? Draw the paths on a diagram. Compare your answers to the values of


1
2
(3[(n - 2)/2] + 1 )

where n = 2, 4, 6, 8. What about n = 10?

See also the problems One Basket and Counting Binary Ops