Recursion: all problems

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?

Arjun and Beth play a game in which they take turns removing one brick or two adjacent bricks from one "wall" among a set of several walls of bricks, with gaps possibly creating new walls. The walls are one brick tall. For example, a set of walls of sizes $4$ and $2$ can be changed into any of the following by one move: $(3, 2)$, $(2, 1, 2)$, $(4)$, $(4, 1)$, $(2, 2)$, or $(1, 1, 2)$.

Arjun plays first, and the player who removes the last brick wins. For which starting configuration is there a strategy that guarantees a win for Beth?

There are $2^{10} = 1024$ possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.

For each positive integer $n$, let $S(n)$ be the number of sequences of length $n$ consisting solely of the letters $A$ and $B$, with no more than three $A$s in a row and no more than three $B$s in a row. What is the remainder when $S(2015)$ is divided by 12?

Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \le a_{k+1} + 2$ for each $1 \le k \le n-1$. For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1, 2, 3, 4, 5$, but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1, 2, \ldots, 7$.

The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and you will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color.

Let $\triangle A_0B_0C_0$ be a triangle whose angle measures are exactly $59.999^\circ$, $60^\circ$, and $60.001^\circ$. For each positive integer $n$, define $A_n$ to be the foot of the altitude from $A_{n-1}$ to line $B_{n-1}C_{n-1}$. Likewise, define $B_n$ to be the foot of the altitude from $B_{n-1}$ to line $A_{n-1}C_{n-1}$, and $C_n$ to be the foot of the altitude from $C_{n-1}$ to line $A_{n-1}B_{n-1}$. What is the least positive integer $n$ for which $\triangle A_nB_nC_n$ is obtuse?

Find the number of permutations of $1, 2, 3, 4, 5, 6$ such that for each $k$ with $1 \le k \le 5$, at least one of the first $k$ terms of the permutation is greater than $k$.