Proof of recurrence relation of partitions

[simmonj7]

Homework Statement

Let T_{n} denote the number of different partitions of {1,2,...,n}. Thus, T_{1} = 1 (the only partition being {1}) and T_{2} = 2 (the only partitions being {1,2} and {1},{2}). show that T_{n+1} = 1 + \sum^{n}_{k=1} (^{n}_{k}) T_{k}.

Homework Equations

Let S be a given set. If, for some k \geq0, S_{1}, S_{2},...,S_{k} are mutually exclusive nonempty subsets of S such that \bigcup^{i=1}_{k} S_{i} = S, then we call the set {S_{1}, S_{2},...,S_{k}} a partition of S.

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_{n}= 1 + \sum^{n-1}_{k=1} (^{n-1}_{k})T_{k} as my inductive hypothesis. So now I have to show that this relationship holds for the T_{n+1} case. So I started with the left hand side of the equation (T_{n+1} =) however I couldn't figure out how to go from here since I didn't know how to break up T_{n+1}. So I figured I would try working backwords and that was when things got really weird...
Starting from my final step:
T_{n+1} = 1 + \sum^{n}_{k=1} (^{n}_{k}) T_{k}
T_{n+1} = 1 + \sum^{n-1}_{k=1} (^{n-1}_{k}) T_{k} + (^{n}_{n})T_{n}
Evaulating the binary coefficient (^{n}_{n}), we find that it is equal to 1. So we now have:
T_{n+1} = 1 + \sum^{n-1}_{k=1} (^{n-1}_{k}) T_{k} + T_{n}
However, by our induction hypothesis, we know that T_{n} = 1 + \sum^{n-1}_{k=1} (^{n-1}_{k}) T_{k}. Therefore, we can simplify this last express to be:
T_{n+1} = T_{n} + T_{n}
However, it is not correct to say that T_{n+1} = 2T_{n} (just solve for T_{1}, T_{2}, T_{3} and you will find that T_{1} = 1, T_{2} = 2, and T_{3} = 5.
Where am I going wrong?

Please help. Thank you.

 

[Stephen Tashi]

T_{n+1} = 1 + \sum^{n}_{k=1} (^{n}_{k}) T_{k}
T_{n+1} = 1 + \sum^{n-1}_{k=1} (^{n-1}_{k}) T_{k} + (^{n}_{n})T_{n}

It would be T_{n+1} = 1 + \sum_{k=1}^{n-1} { n \choose k } T_k + {n \choose n}T_n

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