"Stirling's number of the first kind $s(n,k)$ is the number of permutations of ${1,2,...,n}$ with $k$-cycles. Prove that $n! = \sum s(n,k)$ (from k = 1 to $\infty$) "
After checking a the first few 'n' I have managed to convince myself this is the case. As I didn't know where else to try, I attempted induction, showing true for n = 2 (I thought starting at 1 may be a little too general.) Then assumed true for n = t. Trying to work through n = t + 1 I am beginning to feel that induction in this method won't work, unless I can figure a method, in terms of n and k on summing up terms. Can someone let me know if I am on the right track, or if I am going about this proof in the wrong way, and thus a guide on where to go from there. Thanks in advance.
HINT: Use a combinatorial argument. How many permutations of $\{1,\ldots,n\}$ are there altogether? Does every permutation have a unique cycle structure?