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