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

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