# Compute $\sum_{k=1}^n \binom nk k 3^k$

I'm trying to compute

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

but don't know how. Would anyone be able to show me?

The only thing that I can possibly think of is that

$$\sum_{k=1}^n \binom nk k 3^k = \frac{1}{\ln 3}\sum_{k=1}^n \binom nk \frac{d}{dk}\left[3^k\right]$$

Thanks

• Holy moly, 4 answers within 1 minute – Kenny Lau Sep 27 '17 at 12:21

$$\begin{array}{rcl} \displaystyle \sum_{k=1}^n \binom nk k 3^k &=& \displaystyle \sum_{k=1}^n \frac{n!}{(n-k)!k!} k 3^k \\ &=& \displaystyle \sum_{k=1}^n \frac{n!}{(n-k)!(k-1)!} 3^k \\ &=& \displaystyle \sum_{k=1}^n n \frac{(n-1)!}{(n-k)!(k-1)!} 3^k \\ &=& \displaystyle \sum_{k=1}^n n \binom{n-1}{k-1} 3^k \\ &=& \displaystyle n \sum_{k=1}^n \binom{n-1}{k-1} 3^k \\ &=& \displaystyle n \sum_{k=0}^{n-1} \binom{n-1}{k} 3^{k+1} \\ &=& \displaystyle 3n \sum_{k=0}^{n-1} \binom{n-1}{k} 3^k \\ &=& \displaystyle 3n (1+3)^{n-1} \\ &=& \displaystyle 3n \cdot 4^{n-1} \\ \end{array}$$

• Thanks, that is very helpful :) – sadlyfe Sep 27 '17 at 14:31

Hint: Differentiate $(1+x)^{n}$.

Hint: Your differentiation idea is a good one. Try writing $$f(x) = \sum_{k=1}^n {n \choose k} k x^k$$ (so your aim is to calculate $f(3)$). Then notice that $$f(x) = \sum_{k=1}^n {n \choose k} \left(x \cdot\frac{d}{dx} (x^k)\right).$$

$(1+x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k;$

$x\frac{d}{dx} (1+x)^n= \sum_{k=0}^{n}\binom{n}{k}kx^k.$

$xn(1+x)^{n-1} = \sum_{k=1}^{n}\binom{n}{k}kx^k.$

You can write the binomial coefficient as: $$\sum_{k=1}^n \binom nk k 3^k = 3n\sum_{k=1}^{n} \binom{n-1}{k-1} 3^{k-1}$$

Now note the binomial expansion of $(1+3)^{n-1}$