1

We are given two hints: consider $(n+1)S$; and use the Binomial Theorem. But we are not to use calculus.

My consideration of $(n+1)S$ goes like this: \begin{align*} \sum\limits_{k=1}^{n}\frac{2^{k+1}}{k+1}{n \choose k} &= \frac{1}{n+1}\sum\limits_{k=1}^{n}(n+1)\frac{2^{k+1}}{k+1}{n \choose k} \\ &= 2\frac{1}{n+1}\sum\limits_{k=1}^{n}2^k{n+1 \choose k+1} \\ &= 2\frac{1}{n+1}\sum\limits_{k=1}^{n}(1+1)^k{n+1 \choose k+1} \\ \end{align*} Now I think I'm in a position to use the Binomial Theorem, giving \begin{equation*} 2\frac{1}{n+1}\sum\limits_{k=1}^{n}\sum\limits_{i=0}^{k}{k \choose i}{n+1 \choose k+1} \end{equation*} I don't know if I am on the right track, but I do know that I'm stuck. Can anyone offer any advice on how to proceed?

Adam
  • 97

4 Answers4

1

Observe that $$\frac1{k+1}{n\choose k}=\frac{n!}{(k+1)\cdot k!\cdot(n-k)!}=\frac{n!}{(k+1)!\cdot(n-k)!}=\frac{1}{n+1}\cdot{n+1\choose k+1}$$ Then \begin{align*}\frac{2^2}{2}{n\choose 1}+\frac{2^3}{3}{n\choose 2}+\ldots+\frac{2^{n+1}}{n+1}{n\choose n}&=\frac1{n+1}\left[\sum_{k=1}^n2^{k+1}{n+1\choose k+1}\right]\\ &=\frac1{n+1}\left[(1+2)^{n+1}-2{n+1\choose1}-1\right] \end{align*}

Ángel Mario Gallegos
  • 19,882
1

HINT:

Like Determine: $S = \frac{1}{2}{n \choose 0} + \frac{1}{3}{n \choose 1} + \cdots + \frac{1}{n+2}{n \choose n}$,

$$\sum_{k=1}^n\dfrac{a^{k+1}}{k+1}\binom nk=\dfrac1{n+1}\sum_{k=1}^n\binom{n+1}{k+1}a^{k+1}$$

Now $$\sum_{k=-1}^n\binom{n+1}{k+1}a^{k+1}=(a+1)^{n+1}$$

Community
  • 1
lab bhattacharjee
  • 274,582
  • Thanks. In fact I used the advice in the linked question to get the term ${n+1 \choose k+1}$. What I don't understand is how you got $(a+1)^{n+1}$. I know I'm probably being silly but could you expand on that, please? – Adam Mar 05 '17 at 15:42
  • Yes. I was definitely being silly. That's the binomial theorem applied to $(a+1)^{n+1}$, with a change of dummy $[i:=i+1]$. – Adam Mar 05 '17 at 17:01
1

Note that

$$\sum_{k=1}^n2^{k+1}{n+1\choose k+1}=\sum_{m=2}^{n+1}2^m{n+1\choose m}$$ So $$\sum_{k=1}^n\frac{2^{k+1}}{k+1}{n\choose k}=\frac{1}{n+1}\sum_{m=2}^{n+1}2^m{n+1\choose m}=\frac{1}{n+1}\left((1+2)^{n+1}-1-2(n+1)\right)=\frac{3^{n+1}-3-2n}{n+1}$$

uniquesolution
  • 18,541
1

The trick is to get rid of the factors $1/(k+1)$.

You do so by absorbing $k+1$ in $k!$, and

$$\frac{\binom nk}{k+1}=\frac{n!}{(k+1)k!(n-k)!}=\frac{n!}{(k+1)!(n+1-k-1)!}=\frac{\binom{n+1}{k+1}}{n+1}.$$

Now,

$$S=\sum\limits_{k=1}^{n}\frac{2^{k+1}}{k+1}{n \choose k}=\frac1{n+1}\sum\limits_{k=1}^{n}2^{k+1}{n+1 \choose k+1}.$$

The summation is $3^{n+1}$ from wich the terms $k=-1$ and $0$ have been removed. Hence

$$S=\frac{3^{n+1}-1-2(n+1)}{n+1}.$$

  • Thanks. How did you see that the summation was a fragment of $3^{n+1}$? – Adam Mar 05 '17 at 15:50
  • A binomial sum immediately calls for the binomial theorem. –  Mar 05 '17 at 15:53
  • 1
    I see it! Familiarity with the identity $\sum\limits_{k=0}^n {n \choose k} 2^k = 3^n$ helps! Then we can change the dummy in our summation by $k:=k+1$ and then the fragment is revealed. – Adam Mar 05 '17 at 16:15