# Combinatorial binomial

Calculate the sum value: $$\sum_ {k = 0} ^ {n} k \cdot 3 ^ {k} \cdot \binom {n} {k}$$ Tip: $$\binom {n} {k} = \binom {n-1} {k-1} \cdot \frac {n} {k}$$ I can get here: $$\sum_ {k = 0} ^ {n} 3 ^ {k} \cdot \binom {n-1} {k-1} \cdot n$$ After that, the original resolution takes 'n' out of the sum and places it outside in the '3n' form. I have no idea where this three came from. Then they rewrite the expression this way: $$3n \cdot \sum_ {k = 1} ^ {n} 3 ^ {k} \binom {n-1} {k-1}$$$$3n \cdot (3 + 1) ^ {n-1}$$$$3n \cdot 4 ^ {n-1}$$ Could someone simply elude the above steps or develop a workaround? Original source of the problem: https://portaldosaber.obmep.org.br/uploads/material/dgr8vm27u08os.pdf

• Which steps don't you understand ? Dec 12, 2019 at 14:50
• You seem to have a typo going to the step you don't understand. The summation should have been $\sum\limits_{k=1}^n3^{\color{red}{k-1}}\binom{n-1}{k-1}$. You incorrectly had $3^k$ instead of $3^{k-1}$. The $3$ came from factoring out a common factor of $3$ from every summand. Now, let's rename the indexing variable $j$ instead, letting $j=k-1$ and we have $\sum\limits_{j=0}^{n-1}3^j\binom{n-1}{j}$ Dec 12, 2019 at 14:50
• @user "and so the starting value of the sum is adjusted", no, this adjustment comes from different reasons, namely that $\binom{n-1}{-1}=0$ in this context, and so we don't need to include a term which we know to be zero in our summation, or alternatively worded, we skip over this term and handle it separately so as to avoid the division by zero errors. Dec 12, 2019 at 14:52
• @DonaldSplutterwit After my comment in part two Dec 12, 2019 at 16:10

We obtain \begin{align*} \color{blue}{\sum_{k=0}^nk\,3^k\binom{n}{k}}&=\sum_{k=1}^nk\,3^k\binom{n}{k}\tag{1}\\ &=\sum_{k=1}^nk\,3^k\frac{n}{k}\binom{n-1}{k-1}\tag{2}\\ &=n\sum_{k=1}^n3^k\binom{n-1}{k-1}\tag{3}\\ &=n\sum_{k=0}^{n-1}3^{k+1}\binom{n-1}{k}\tag{4}\\ &=3n\sum_{k=0}^{n-1}3^{k}\binom{n-1}{k}\tag{5}\\ &\,\,\color{blue}{=3n4^{n-1}}\tag{6}\\ \end{align*} and the claim follows.

Comment:

• In (1) we skip the index $$k=0$$ which does not contribute anything.

• In (2) we apply the binomial identity $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$$.

• In (3) we cancel $$k$$ and factor out $$n$$.

• In (4) we shift the index and start with $$k=0$$. We compensate the shift of the index $$k$$ by replacing in the summand each occurrence of $$k$$ with $$k+1$$.

• In (5) we factor out $$3$$.

• In (6) we apply the binomial theorem to $$4^{n-1}=(1+3)^{n-1}$$.

You are right, but another way is: $$(1+x)^{n}=\sum_{k=0}^{n} {n \choose k} x^k$$, D.w.r.t.x we get $$n(1+x)^{n-1}=\sum_{k=0}^{n} k {n \choose k} x^{k-1}$$ By putting $$x=3$$, we get the sum as $$3n 4^{n-1}$$

• Where did n and k come from? Dec 12, 2019 at 19:42