Starting at the origin in the coordinate plane, you are allowed to follow a path where each step
is one unit up, down, left, or right, but the *y*-coordinate of any point on the path
must be non-negative. A path is allowed to cross itself or retrace part of itself. There
are three such paths of length 1 and ten such paths of length 2. How many paths of length *n*
are there?

**
Source: Bill Sands
**