Let f(n, k) be the number of ways the set {1, 2, . . . , n} on k non-empty subsets, where the order of the subsets and t

[answerhappygod]

Let f(n, k) be the number of ways the set {1, 2, . . . , n} on knon-empty subsets, where the order of the subsets and the orderwithin each subset does not matter.
For example, f(3, 2) = 3 because we can partition the set {1, 2,3} into 2 subsets in 3 different ways:
{1} {2, 3}{2} {1, 3}{3} {1, 2}
Prove that f(n, k) = k f(n − 1, k) + f(n − 1, k − 1)