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

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.

• yes, sorry my formatting is off – Brownie Mar 15 at 22:07

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$$

• Alright, so does it make sense if I multiplied $\displaystyle\sum_{k=1}^n \left(\frac{{n-1 \choose k-1}}{k}\right)$ by n, and then took that summation, and then divided by n at the end? – Brownie Mar 15 at 22:12
• It would be perfect! – Bernard Mar 15 at 22:13
• So dividing by n after taking the summation is correct? Or would I have to divide by the summation of n since I already took the summation of $\displaystyle\sum_{k=1}^n \left(\frac{n{n-1 \choose k-1}}{k}\right)$ – Brownie Mar 15 at 22:14
• It's correct since multiplication (and division) is distributive w.r.t. addition. – Bernard Mar 15 at 22:16
• Thank you that clears it up! – Brownie Mar 15 at 22:16

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.

• nice and clean approach – G Cab Mar 15 at 22:38

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}

• So you solution brings up a few question for me. Going off of the hint above, the way I solved it was multiplying the summation by n turning it into $\displaystyle\sum_{k=0}^n\binom nk$. I took that summation giving me $2^{n}$, and then divided by n to undo my previous multiplication giving me ${2^{n} \over n}$ which is different from you answer. Where did i go wrong? – Brownie Mar 15 at 22:29
• Edit - I see i took the summation at the wrong index – Brownie Mar 15 at 22:35
• @Brownie: you did not take into proper consideration the summation bounds. – G Cab Mar 15 at 22:37