2
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ Thanks for the answer! Clear and concise! $\endgroup$ – Vladar Akos Jun 18 at 7:05
1
$\begingroup$

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)

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