# Proving an identity related to Sterling Numbers of the 2nd Kind

1. Nov 28, 2011

### BraedenP

1. The problem statement, all variables and given/known data

I am to prove, by induction, that $$S(n,2)=\sum_{m=1}^{n-1}\cdot S(m,1) + \sum_{m=2}^{n-1}\cdot S(m,2)$$

where the S function is the Sterling function (S(n,k) is the number of k-partitions of an n-set)

2. Relevant equations

$$S(n,1) = 1$$
$$S(n,2) = 2^{n-1}-1$$

3. The attempt at a solution

Creating a base case is easy, and using the first given equation, the first sum in the problem evaluates to simply n-1. So then I'll need to get the second sum into a form that can help me prove this equality by induction.

Since I'm using induction, at some point I'll need to get the right side into a form that I can equate with the second given equation.

How can I start simplifying this to lead me to an answer?