1
$\begingroup$

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

Now the way I solved this was by multiplying by n and turning it into

$\displaystyle\sum_{k=1}^n\binom nk$

my mistake was that I took the summation when $k=0$ to give me an easy $2^{n}$ which I divide by n to get a final answer of

${2^{n} \over n}$ when it is actually supposed to be ${2^{n} -1 \over n}$

My question is how would I find that changing $\displaystyle\sum_{k=1}^n\binom nk$ to $\displaystyle\sum_{k=0}^n\binom nk$ would change the numerator to ${2^{n} -1}$.

$\endgroup$
  • $\begingroup$ You seem to be missing a factor $\tfrac1n$ in your summations. $\endgroup$ – Servaes Mar 15 at 22:48
1
$\begingroup$

Changing the bottom index simply omits the first term in the sum, which is $\binom{n}{0}=1$. So $$\displaystyle\sum_{k=1}^n\binom nk=\displaystyle\sum_{k=0}^n\binom nk-1.$$

$\endgroup$
  • $\begingroup$ alright so since it omits the first term which is equal to 1, i would just subtract 1 from the summation. That make sense. Now sorry if this is a really obvious question, but I am completely new to this, $\binom{n}{0}=1$ is this from pascals triangle? or is just whenever you "choose" 0 its always equal to 1? $\endgroup$ – Brownie Mar 15 at 22:49
  • 2
    $\begingroup$ There are many ways to see it, and what is the easiest way depends on your definition. You could read it off from Pascals triangle; these are all the $1$'s at the beginning of every row. Or from the combinatiorial interpretation; there is precisely $1$ way to choose nothing from $n$ elements. Or algebraically $$\binom n0=\frac{n!}{0!n!}=1.$$ $\endgroup$ – Servaes Mar 15 at 22:51
0
$\begingroup$

Isn’t it just that $$\sum_{k=0}^n c_k=c_0 +\sum_{k=1}^n c_k$$ and noting that your $c_0=1$?

$\endgroup$

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.