Assume \( k! | P(m,k) \) for all \(m+k\le n\). Now to show that \( k! | P(m,k) \) for all \( m+k \le n+1 \)

If \( m=1\) we are done since \( P(1,k) = 1\cdot 2\cdots k = k!\) and if \( k=1\)  then \( k! = 1!\), clearly divides \( P(m,k)\). So in the remainder

we may assume that \( m\ge  2\) and \( k \ge 2\). Also if \( m+k\le n\) we are done vacuously, so consider only that \( m+k = n+1\).

By the lemma we have $$P(m,k) = k\times P(m,k-1) + P(m-1,k)$$ so by the Induction hypothesis we have \( (k-1)! | P(m,k-1)\)

and thus also \( k! | k\times P(m,k-1)\) and also by the Induction hypothesis \( k! | P(m-1,k) \) and finally \( k! | P(m,k)\) QED