Do Not Look Just Yet. Solutions to Odd-Numbered Exercises. 395
Now let us divide both sides by [n − 1]! to obtain
[n]=[k]q
n−k
+[n −k],
which follows directly from the definition of [m].
23. This can be proved by repeated applications of the result of Exercise 21,
but we prefer a combinatorial argument. The left-hand side provides
the generating function for all k-subsets of [m] according to their subset
sums.
A typical term of the right-hand side is of the form q
m−k−j+1
m−j
k−1
,
where j ∈ [m − k]. We claim that this term will provide the generating
function for those k-subsets of [m] whose largest element is equal to
m − j + 1. Indeed, the rest of such a subset is a (k − 1)-subset of the
set [m − j]. The term q
m−j−k+1
corrects the shift in the definitio