Exercise 10, § 5

Let $q_{n,\,k}$ be the number of strictly increasing mappings $u$ of $[1, k]$ into $[1, n]$ such that for each even (resp. odd) $x$, $u(x)$ is even (resp. odd). Show that $q_{n,\,k} = q_{n-1,\,k-1} + q_{n-2,\,k}$ and deduce that