Register to reply

Proof of recurrence relation of partitions

by simmonj7
Tags: partitions, proof, recurrence, relation
Share this thread:
simmonj7
#1
Jun23-11, 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]^{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.
Phys.Org News Partner Science news on Phys.org
Apple to unveil 'iWatch' on September 9
NASA deep-space rocket, SLS, to launch in 2018
Study examines 13,000-year-old nanodiamonds from multiple locations across three continents
Stephen Tashi
#2
Jun23-11, 08:20 PM
Sci Advisor
P: 3,296
Quote Quote by simmonj7 View Post
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]
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.)


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