If $S \left( n , k \right)$ is the number of partitions with $k$ blocks we can make from a set with $n$ elements, is the formula $$ S \left( n + 1, k \right) = \sum_{i = 0} ^{n} \binom{n}{i} S \left( i, k - 1 \right)$$ correct?
I ask because I have to prove the right-hand side counts the same thing as the left-hand side, but my strategy is not working and I think it is correct.
Yes, it’s correct.
HINT: Use the fact that $$\binom{n}iS(i,k-1)=\binom{n}{n-i}S(i,k-1)\;.$$ Think about first picking the block that will contain $n+1$, then splitting up the rest of $[n]$.