Bài tập 10, § 5

Gọi $q_{n,\,k}$ là số các ánh xạ tăng ngặt $u$ từ $[1, k]$ vào $[1, n]$ sao cho với mọi $x$ chẵn (tương ứng, lẻ), $u(x)$ là chẵn (tương ứng, lẻ). Chứng minh rằng $q_{n,\,k} = q_{n-1,\,k-1} + q_{n-2,\,k}$ và suy ra rằng