Recursion: all problems

Jeff is climbing a 7 step staircase. If he can climb 1 or 2 steps at a time, in how many ways can he get to the top?

Everyday at school, Jo climbs a flight of 6 stairs. Jo can take the stairs 1, 2, or 3 at a time. For example, Jo could climb 3, then 1, then 2. In how many ways can Jo climb the stairs?

Brandon is trying to reach the top of a 7 step staircase. For each jump except the last jump, he can either jump 1 or 3 steps forward. On the last jump, he can jump 1, 2, or 3 steps forward. How many different ways can he reach the top of the staircase?

Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $\{1, 2, 3, \ldots, 12\}$, including the empty set, are spacy?

A collection of 8 cubes consists of one cube with edge-length $k$ for each integer $k$, $1 \le k \le 8$. A tower is to be built using all 8 cubes according to the following rules: Any cube may be the bottom cube in the tower. The cube immediately on top of a cube with edge-length $k$ must have edge-length at most $k + 2$. How many towers can be constructed?

Jeff is climbing a 10 step staircase. However, there are spiders on the 3rd and 9th steps, and he refuses to step on those stairs. If he can climb 1 or 2 steps at a time, in how many different ways can he get to the top?