(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**

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

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