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 $\geq$0, 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.)