I have been working on this problem for a long time before I decided to post it here. If you don't want to help, don't help me.
Firstly, I tried to use the following identity, the definition of a Stirling number of the second kind:
but it was of no use, since the summations index differ...
Then, i tried using some of the identities for Stirling numbers I found, and eventually realized that this problem is expressed as identities no. 6.15 and 6.22 in Knuth, Patashnik "Concrete Matematics" book. So, I'm not sure if I'm allowed to use all the other identities that I found there to prove this one...
I guess the best way to prove it would be by induction, but it also doesn't work.
I've also tried to calculate right and left handsides in WolframAlpha, but the results were just what we have here, no middle-steps.
If you could just give me a clue...
You are the one who simply posted the question without any explanation as to what you did not understand. Do you understand what the Stirling Numbers of the second kind count? ,
counts the number of ways to place n distinguishable objects into k indistinguishable cells where no cells may be empty.
It would seem as if these problems are calling for combinational proofs.
Do you know this recursion?
so that gives
where if , and if .