A sequence $u_{1}, u_{2}, \ldots, u_{n}$ composed of the integers $1,2, \ldots, n$ is quasi-increasing if, for every index $k, u_{k} \leq u_{k+1}+2$. For example, the sequence $1,6,4,2,5,3$ is quasi-increasing but the sequence $1,4,6,2,5,3$ is not. Determine the number of quasi-increasing sequences of $n$ terms.
We notice that a quasi-increasing sequence of $n+1$ integers can be obtained from a quasi-increasing sequence of $n$ integers by adding $n+1$ either before $n$, or before $n+1$, or in the last position (one needs to think a bit to be convinced of this point).

Thus, the number $s_{n}$ of quasi-increasing sequences of $n$ integers satisfies $s_{n+1}=3 \times s_{n}$ for all $n \geq 2$. Since $s_{2}=2$, we deduce by induction that $s_{n}=2 \times 3^{n-2}$ for $n \geq 2$ (and $s_{1}=1$).

## Binomial Coefficients

## Definition

## Definition

The binomial coefficient $\binom{n}{p}$ is the number of subsets with $p$ elements of a set with $n$ elements.

## Remark

If $p>n,\binom{n}{p}=0$ because there are no subsets with $p$ elements in a set with $n$ elements.