Let $S(n,k)$ denote the number of surjective functions from a set of size $n$ to a set of sive $k$, where $n \geq k$.
Prove the following using a combinatorial proof:
$S(n+1,n) = nS(n,n-1) + n(n!)$
LHS counts the number of surjections from a set of size $n+1$ to size $n$ or $S(n+1,n)$
Suppose you have a set of surjections of size $n$ to size $n-1$. This is $S(n,n-1)$ and you want to count the number of surjections from $n+1$ to $n$.
Now I'm not sure on what to do next any help will be appreciated.