I like to solve combinatorics problems recreationally. I recently thought of the following and am having a lot of trouble wrapping my head around this:
Suppose you have a staircase with n many steps. For n seconds, you'll walk up and down this staircase, taking one step at a time. During the first second, you always begin on the first step. During each subsequent second, you can walk up one step, down one step, or stay where you are. The only exceptions are that if you are on the first step you cannot walk down any further, and if you are on the nth step you cannot walk up any further.
How many different ways can you walk up and down the steps?
Example: If n = 3, there are four ways. They are represented as 1-1-1, 1-2-1, 1-2-2, and 1-2-3.