# How to find the formula to this summation and the prove it by induction?

I need to find the formula of the sum below and the prove it by induction. Sadly so far I have not been able to succed. My problem is finding the formula.

The formula: $$\sum_{k = 0}^n (2k + 1)*C_n^k = ?$$

What I have done so far: $$\sum_{k = 0}^n C_n^k * x^k = (x + 1)^n$$ For $$x = 1:$$ $$\sum_{k = 0}^n C_n^k = 2^n$$

Then I multiplied both sides by $$\sum_{k = 0}^n (2k + 1)$$ And then I get that: $$\sum_{k = 0}^n (2k + 1) * C_n^k = 2^n * (n + 1)^2$$

But sadly I messed up somewhere because for $$n = 1$$ this is not true.. Maybe I am not allowed to multiply with a summation like that. Please help me find the formula and explain what I did wrong!

Edit 1: $$C_n^k$$ = binomial coefficient. I learned to write it this way. Edit 2: Thank your for the help!

• The last step is incorrect since the product of the sums need not be the sum of the products. – Viktor Glombik Jun 16 at 10:52
• @ViktorGlombik $C^k_n$ is another way of writing the binomial coefficient $$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$ – N. F. Taussig Jun 16 at 10:54

We have $$\sum_{k = 0}^{n} (2k + 1) \binom{n}{k} = 2 \sum_{k = 0}^{n} k \binom{n}{k} + \sum_{k = 0}^{n} \binom{n}{k} = 2 \underbrace{\sum_{k = 0}^{n} k \binom{n}{k}}_{:= S} + 2^n$$ Since $$(x + 1)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$$ we have $$n (x + 1)^{n - 1} = \frac{d}{dx} (x + 1)^n = \sum_{k = 0}^{n} \binom{n}{k} \frac{d}{dx} x^k = \sum_{k=0}^{n} \binom{n}{k} k x^{k-1}$$ With $$x = 1$$ you find $$S = n 2^{n - 1}$$ and therefore $$\sum_{k = 0}^{n} (2k + 1) \binom{n}{k} = 2n 2^{n - 1} + 2^n = n 2^n + 2^n = 2^n (n + 1).$$
Hint: Apply $$\frac{\mathrm d}{\mathrm d x}$$ to $$(x+1)^n=\sum_{k=0}^nC^k_nx^k$$. (However, this will lead to a direct proof, not a proof by induction)