Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proving an identity related to Sterling Numbers of the 2nd Kind

  1. Nov 28, 2011 #1
    1. The problem statement, all variables and given/known data

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

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

    2. Relevant equations

    [tex]S(n,1) = 1[/tex]
    [tex]S(n,2) = 2^{n-1}-1[/tex]

    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?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted