Evaluate $\displaystyle\sum_{k=1}^n \left(\frac{{n-1 \choose k-1}}{k}\right)$

Question

Evaluate : $\displaystyle\sum_{k=1}^n \left(\frac{{n-1 \choose k-1}}{k}\right)$

Alright so I'm completely stumped, I've never evaluated a summation of $\displaystyle{n \choose k}$.

My best guess is to use the binomial theorem, but I don't know how to change this into a form I could use the theorem on.

A little guidance please?

Answer 1

Hint:

Use the recurrence relation $$\binom nk=\frac nk\binom{n-1}{k-1}$$ and remember that $\displaystyle\sum_{k=0}^n\binom nk=\cdots$

Answer 2

The hint given is already good.
In alternative you can proceed as follows $$ \eqalign{ & \sum\limits_{k = 1}^n {{1 \over k}\left( \matrix{ n - 1 \cr k - 1 \cr} \right)} \quad \left| {\;1 \le n} \right.\quad = \cr & = \sum\limits_{k = 0}^{n - 1} {{1 \over {\left( {k + 1} \right)}}\left( \matrix{ n - 1 \cr k \cr} \right)} = {1 \over n}\sum\limits_{k = 0}^{n - 1} {{n \over {\left( {k + 1} \right)}}\left( \matrix{ n - 1 \cr k \cr} \right)} = \cr & = {1 \over n}\sum\limits_{k = 0}^{n - 1} {\left( \matrix{ n \cr k + 1 \cr} \right)} = {1 \over n}\sum\limits_{k = 1}^n {\left( \matrix{ n \cr k \cr} \right)} = {1 \over n}\left( {\sum\limits_{k = 0}^n {\left( \matrix{ n \cr k \cr} \right)} - 1} \right) = \cr & = {1 \over n}\left( {2^{\,n} - 1} \right) \cr} $$

Answer 3

Another alternative is to somehow see the function $\frac{x^k}{k}$ in the series and use a bit of calculus:

$$\frac{d}{dx}\displaystyle\sum_{k=1}^n \binom{n-1}{k-1} \frac{x^k}{k}=\displaystyle\sum_{k=1}^n \frac{d}{dx} \binom{n-1}{k-1} \frac{x^k}{k}=\displaystyle\sum_{k=1}^n \binom{n-1}{k-1}x^{k-1}=(1+x)^{n-1}$$ by the Binomial Theorem, so $$\displaystyle\sum_{k=1}^n \binom{n-1}{k-1} \frac{x^k}{k}=\int (1+x)^{n-1} dx=\frac{(1+x)^n}{n}+\mathcal{C}.$$ Plugging in $x=0$ tells us that $\mathcal{C}=-\frac{1}{n}$, so we have the more general result $$\displaystyle\sum_{k=1}^n \binom{n-1}{k-1} \frac{x^k}{k}=\frac{(1+x)^n-1}{n}.$$ In particular, taking $x=1$ gives the desired result.