Stirling numbers: Show that $S(n+1, r)=rS(n, r)+S(n, r-1)$.

Question

I know that the Stirling numbers of the second kind are the number of partitions of an $n$-set with $r$ non-empty parts, and that they can be denoted $S(n,r)$.

How would I then show $S(n+1, r)=rS(n, r)+S(n, r-1)$? Could anyone provide me with any tips or hints? Thanks.

Answer 1

Hint: Suppose you have a partition of $n+1$ into $r$ parts. Order your parts in a line and locate the part that contains $n+1$ and take it out. There will be two options (Notice that perhaps you took out all elements of the part!!)

Answer 2

I see you already received an answer, but I wanted to share this video with you that covers the recursive formula you posted in a visual: https://youtu.be/hKYc9mwPJBA Basically, you want to think about what happens when you add the additional element (+1) to the set of (n) elements to get (n + 1) elements; specificially, think about which former subdivisions of n into k still hold for n+1 into k.