1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Note that $$\sum_{k=1}^n2^{k+1}{n+1\choose k+1}=\sum_{m=2}^{n+1}2^m{n+1\choose m}$$ $\endgroup$ – uniquesolution Mar 5 '17 at 15:20
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks. How did you see that the summation was a fragment of $3^{n+1}$? $\endgroup$ – Adam Mar 5 '17 at 15:50
  • $\begingroup$ A binomial sum immediately calls for the binomial theorem. $\endgroup$ – Yves Daoust Mar 5 '17 at 15:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Adam Mar 5 '17 at 16:15
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Adam Mar 5 '17 at 15:42
  • $\begingroup$ 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]$. $\endgroup$ – Adam Mar 5 '17 at 17:01
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The OP specifically asked "No Calculus" $\endgroup$ – uniquesolution Mar 5 '17 at 15:22
  • $\begingroup$ @uniquesolution: this is why this answer is perfectly valid. $\endgroup$ – Yves Daoust Mar 5 '17 at 15:33
  • $\begingroup$ @YvesDaoust after several edits, it is. $\endgroup$ – uniquesolution Mar 5 '17 at 15:36
1
$\begingroup$

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

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