1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ yes, sorry my formatting is off $\endgroup$ – Brownie Mar 15 at 22:07
3
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Brownie Mar 15 at 22:12
  • 1
    $\begingroup$ It would be perfect! $\endgroup$ – Bernard Mar 15 at 22:13
  • $\begingroup$ 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)$ $\endgroup$ – Brownie Mar 15 at 22:14
  • 1
    $\begingroup$ It's correct since multiplication (and division) is distributive w.r.t. addition. $\endgroup$ – Bernard Mar 15 at 22:16
  • $\begingroup$ Thank you that clears it up! $\endgroup$ – Brownie Mar 15 at 22:16
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ nice and clean approach $\endgroup$ – G Cab Mar 15 at 22:38
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brownie Mar 15 at 22:29
  • $\begingroup$ Edit - I see i took the summation at the wrong index $\endgroup$ – Brownie Mar 15 at 22:35
  • $\begingroup$ @Brownie: you did not take into proper consideration the summation bounds. $\endgroup$ – G Cab Mar 15 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.