(adsbygoogle = window.adsbygoogle || []).push({}); 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proof of recurrence relation of partitions

**Physics Forums | Science Articles, Homework Help, Discussion**