Combinatorial proof: $\sum_k {n+1 \brack k}k = {n+2 \brack 2}$ I need to prove that: $$\sum_k  {n+1 \brack k}k = {n+2 \brack 2}$$
I know that this can be done by induction, but this is a bit tedious. Can you think of a combinatorial proof of this theorem? 
Literally, the right hand side calculates in how many ways we can seat $n+2$ people at $2$ round tables. 

The left hand side calculates in how many ways we can seat $n+1$ people at $k$ circular tables and then add the last person to one of the tables already occupied and then add them together with respect to $k$. 
To be honest, I don't see any straightforward connection between these two. Any hints?
 A: Let $A=\{a_1,\cdots,a_m \} $ be a finite set, that does not contain the element $n+1$. We begin by noting a one to one correspondence between permutations of this set and the conjugacy class of $A \cup \{n+1 \}$.
Given an element $\pi \in S_A$ ($\pi(a_i)=\pi_{a_i}$) we form an element of $S_{A \cup \{n+1 \}}$ by
\begin{eqnarray*}
\pi \rightarrow (\pi_{a_1}, \cdots , \pi_{a_m},n+1 ).
\end{eqnarray*}
We shall now use this to establish the following formula
\begin{eqnarray*}
\sum_{k=j}^{n}  {n \brack k} \binom{k}{j}  = {n+1 \brack j+1}.
\end{eqnarray*}
Let $ \sigma$ be an element of $S_n$ with $k$ cycles. Choose $j$ of these cycles and let $A$ be the set of elements in the other $k-j$ cycles. Now form an element of $S_{n+1}$ consisting of the $k$ chosen cycles and a cycle formed by the correspondence $S_A \rightarrow  S_{A \cup \{n+1 \}}$ defined above. Now let $k$ vary over its admissable values and the formula is proven.
To recover the result you require, replace $n$ with $n+1$ and let $j=1$.
A: I don't have a combinatorial proof but I thought the following algebraic proof is interesting. 
Let $$c(x) = x^{\bar n}$$
We have by definition, $\sum_k {n \brack k}x^k = c(x)$
Differentiating, we get:
$$\sum_{k=1}^n k{n \brack k}x^{k-1} = c'(x) = c(x)\left(\frac{1}{x+n-1} + \frac{1}{x+n-2} + ... + \frac{1}{x}\right)$$
Plugging $x=1$, we get
$$\sum_{k=1}^n k{n \brack k} = c(1)\left(\frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{1}\right)$$
We know $c(1) = n!$
So $$\sum_{k=1}^n k{n \brack k} = n!\left(\frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{1}\right)$$
Now there is a completely separate proof for:
$$n!\left(\frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{1}\right) = {n+1 \brack 2}$$
A: HINT: Your interpretation of the left side doesn't match the expression.  Here's a different way:
The LHS is the number of ways to pick a permutation of $n+1$ elements and color a cycle.
How can you get this to match the RHS?  Notice that the non-colored cycles form a permutation by themselves.  Is there a bijection between $m+1$ cycles and $m$ permutations?
