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

#### 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?

Related Calculus and Beyond Homework News on Phys.org

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

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving