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

Question

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!

Answer 1

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

Answer 2

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)