In a single-file queue of $n$ people with distinct heights, define a blocker to be someone who is either taller than the person standing immediately behind them, or the last person in the queue. For example, suppose that Ashanti has height $a,$ Blaine has height $b,$ Charlie has height $c,$ Dakota has height $d,$ and Elia has height $e,$ and that $a<b<c<d<e.$ If these five people lined up in the order Ashanti, Elia, Charlie, Blaine, Dakota (from front to back), then there would be three blockers: Elia, Charlie, and Dakota. For integers $n \ge 1$ and $k \ge 0,$ let $Q(n,k)$ be the number of ways that $n$ people can queue up such that there are exactly $k$ blockers.
Show that $$Q(3,2)= 2 \cdot Q(2,2)+ 2 \cdot Q(2,1).$$
Show that for $n \ge 2$ and $k \ge 1,$ $$Q(n,k)=k \cdot Q(n-1,k)+(n-k+1) \cdot Q(n-1,k-1).$$
Assume that $Q(1,1)=1,$ and that $Q(n,0)=0$ for all $n.$
For the first part of the problem, can we just bash certain values as our proof? (e.g. $Q(3, 2)$)
Part $2$ so far: For every queue of $n-1$ people with $k$ blockers, there are $k$ corresponding queues with $n$ people and $k$ blockers. For every queue of $n-1$ people with $k-1$ blockers, there are $n-k+1$ corresponding queues with $n$ people and $k$ blockers; and that these queues together make up all queues with $n$ people and $k$ blockers.