I am struggling with computing the following sums:
$$\sum_{k=1}^{n}k\binom{n}{k}=\binom{n}{1}+2\binom{n}{2}+...+n\binom{n}{n}$$
and
$$\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\binom{n}{0}+\frac{1}{2}\binom{n}{1}+\frac{1}{3}\binom{n}{2}+\dots+\frac{1}{n+1}\binom{n}{n}$$
At first, I tried just rewriting the general terms in a form where the Binomial Theorem could be applied, but could not do so. ($k$ should be in the exponent of something with $n-k$ in the exponent of something else.)
Then, for the first sum, I re-wrote it in the following manner:
\begin{align} S &=\binom{n}{n}+\dots+\binom{n}{3}+\binom{n}{2}+\binom{n}{1}\\ &+\binom{n}{n}+\dots+\binom{n}{3}+\binom{n}{2}\\ &+\binom{n}{n}+\dots+\binom{n}{3}\\ &\quad\vdots\\ &+\binom{n}{n} \end{align}
Noting that:
$$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}=\sum_{k=0}^{n}\binom{n}{k}1^k1^{n-k}=(1+1)^n=2^n,$$
I can rewrite the first line in $S$ as $2^n-1$ (the $-1$ is there because I'm over-counting the $\binom{n}{0}=1$).
Then I tried to say that if all the "blanks" were filled (if all the lines were like the first line), since there are $n$ lines, then I have $n(2^n-1)$. From this point, we should have:
$$S+\text{blanks}=n(2^n-1)\Longrightarrow S=n(2^n-1)-\text{blanks}$$
However, the problem of finding the value of "blanks" seems as hard as the original problem and I can't get to the right answer of $n2^{n-1}$ (according to WA). In one of my attempts, I ended up with a geometric series but that still didn't work.
I have not spent much time on the second sum as I feel I should be able to do the first one before even tackling the second one. Am I going in the right direction with this? Is there a more intelligent way of working this out?
Thanks in advance for any help/hints.
One of my preferred methods of proof for these types of identities is to use a combinatorial proof which generally takes the form of describing a counting problem and finding the answer using two different methods thereby proving that the expressions achieved by each answer must be equal.
Suppose we have a committee of $n$ distinct people. We ask, in how many ways may we choose a subcommittee of any size where the subcommittee has one member designated as the leader (including the case of the leader being the only person on the subcommittee by himself)?
Let us first break into cases based on the number of members on the committee. Since the committee must have a leader, the committee size must be at least $1$ and can be at most $n$. Let $k$ be the number of people on the subcommittee
Next, let us select all of the members of the subcommittee (including the leader). This can be done in $\binom{n}{k}$ ways.
Then, from those people selected, let us choose one of them to be the leader. This can be done in $k$ ways.
Applying multiplication principle and summing over all possible cases gives us the total number of subcommittees possible as being:
$$\sum\limits_{k=1}^nk\binom{n}{k}$$
Let us before anything else select a person to serve as the leader for the subcommittee. This can be done in $n$ ways.
From the remaining $n-1$ people, let us choose some subset (possibly empty) to act as the followers in the subcommittee. This can be done in $2^{n-1}$ ways.
Applying multiplication principle, we arrive at a total number of subcommittees as being:
$$n2^{n-1}$$
We have as a result the identity:
$$\sum\limits_{k=1}^nk\binom{n}{k}=n2^{n-1}$$