Proof of recurrence relation of partitionsby simmonj7 Tags: partitions, proof, recurrence, relation 

#1
Jun2311, 04:44 PM

P: 66

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]^{n1}_{k=1}[/itex] ([itex]^{n1}_{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]^{n1}_{k=1}[/itex] ([itex]^{n1}_{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]^{n1}_{k=1}[/itex] ([itex]^{n1}_{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]^{n1}_{k=1}[/itex] ([itex]^{n1}_{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
Jun2311, 08:20 PM

Sci Advisor
P: 3,177

(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.) 


Register to reply 
Related Discussions  
Derangement Recurrence Relation Proof Doesn't Seem To Make Sense  Set Theory, Logic, Probability, Statistics  8  
Recurrence Relation  Calculus & Beyond Homework  1  
Recurrence Relation  Calculus & Beyond Homework  0  
Recurrence relation  General Math  7  
Recurrence Relation  General Math  11 