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: Proof of recurrence relation of partitions

  1. Jun 23, 2011 #1
    1. The problem statement, all variables and given/known data
    Let T[itex]_{n}[/itex] denote the number of different partitions of {1,2,...,n}. Thus, T[itex]_{1}[/itex] = 1 (the only partition being {1}) and T[itex]_{2}[/itex] = 2 (the only partitions being {1,2} and {1},{2}). show that T[itex]_{n+1}[/itex] = 1 + [itex]\sum[/itex][itex]^{n}_{k=1}[/itex] ([itex]^{n}_{k}[/itex]) T[itex]_{k}[/itex].

    2. Relevant equations
    Let S be a given set. If, for some k [itex]\geq[/itex]0, S[itex]_{1}[/itex], S[itex]_{2}[/itex],...,S[itex]_{k}[/itex] are mutually exclusive nonempty subsets of S such that [itex]\bigcup[/itex][itex]^{i=1}_{k}[/itex] S[itex]_{i}[/itex] = S, then we call the set {S[itex]_{1}[/itex], S[itex]_{2}[/itex],...,S[itex]_{k}[/itex]} a partition of S.

    3. The attempt at a solution
    I figured I would prove this by induction. Since the base case is easy, I won't discuss it. The inductive step is where I am having problems. So I have been assuming that T[itex]_{n}[/itex]= 1 + [itex]\sum[/itex][itex]^{n-1}_{k=1}[/itex] ([itex]^{n-1}_{k}[/itex])T[itex]_{k}[/itex] as my inductive hypothesis. So now I have to show that this relationship holds for the T[itex]_{n+1}[/itex] case. So I started with the left hand side of the equation (T[itex]_{n+1}[/itex] =) however I couldn't figure out how to go from here since I didn't know how to break up T[itex]_{n+1}[/itex]. So I figured I would try working backwords and that was when things got really weird...
    Starting from my final step:
    T[itex]_{n+1}[/itex] = 1 + [itex]\sum[/itex][itex]^{n}_{k=1}[/itex] ([itex]^{n}_{k}[/itex]) T[itex]_{k}[/itex]
    T[itex]_{n+1}[/itex] = 1 + [itex]\sum[/itex][itex]^{n-1}_{k=1}[/itex] ([itex]^{n-1}_{k}[/itex]) T[itex]_{k}[/itex] + ([itex]^{n}_{n}[/itex])T[itex]_{n}[/itex]
    Evaulating the binary coefficient ([itex]^{n}_{n}[/itex]), we find that it is equal to 1. So we now have:
    T[itex]_{n+1}[/itex] = 1 + [itex]\sum[/itex][itex]^{n-1}_{k=1}[/itex] ([itex]^{n-1}_{k}[/itex]) T[itex]_{k}[/itex] + T[itex]_{n}[/itex]
    However, by our induction hypothesis, we know that T[itex]_{n}[/itex] = 1 + [itex]\sum[/itex][itex]^{n-1}_{k=1}[/itex] ([itex]^{n-1}_{k}[/itex]) T[itex]_{k}[/itex]. Therefore, we can simplify this last express to be:
    T[itex]_{n+1}[/itex] = T[itex]_{n}[/itex] + T[itex]_{n}[/itex]
    However, it is not correct to say that T[itex]_{n+1}[/itex] = 2T[itex]_{n}[/itex] (just solve for T[itex]_{1}[/itex], T[itex]_{2}[/itex], T[itex]_{3}[/itex] and you will find that T[itex]_{1}[/itex] = 1, T[itex]_{2}[/itex] = 2, and T[itex]_{3}[/itex] = 5.
    Where am I going wrong?

    Please help. Thank you.
  2. jcsd
  3. Jun 23, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    It would be [itex] T_{n+1} = 1 + \sum_{k=1}^{n-1} { n \choose k } T_k + {n \choose n}T_n [/itex]

    (It might be simpler to use a verbal argument than a purely algebraic approach and you don't need so many itex tags in your LaTex.)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook