Calculate the sum: $C_{2n}^n+2C_{2n-1}^n+4C_{2n-2}^n+...+2^nC_n^n$

Question

Calculate this sum:$$C_{2n}^n+2C_{2n-1}^n+4C_{2n-2}^n+...+2^nC_n^n.$$

What I tried:

$$ C^n_{2n}=\frac{(2n)!}{(n!)^2}$$

$$ 2C^n_{2n-1}=\frac{2(2n-1)!}{n!(n-1)!}=\frac{2n(2n)!}{n!n!(2n)}=\frac{(2n)!}{(n!)^2}$$

$$ 4C^n_{2n-2}=\frac{4(2n-2)!}{n!(n-2)!}=\frac{4(2n)!(n)(n-1)}{(2n)(2n-1)(n!)^2}=\frac{2(2n)!(n-1)}{(2n-1)(n!)^2}$$

$$ 2^nC_n^n=2^n$$

So our original sum is equal to this:

$$C_{2n}^n\left( 1+1+\frac{2(n-1)}{(2n-1)}+\frac{2^2(n-1)(n-2)}{(2n-1)(2n-2)}+...+\frac{2^n}{C_{2n}^n} \right)$$

$$=C_{2n}^n\sum_{k=1}^n \frac{2^k(n-1)!(2n-k)!}{(n-k)!(2n-1)!}$$

$$=C_{2n}^n\sum_{k=1}^n \frac{2n}{n-1}=C_{2n}^n2n\sum_{k=1}^n\frac{1}{n-1}=C_{2n}^n \left( \frac{2n(n-1)}{n-1} \right) = 2nC_{2n}^n$$

So... how do I go from here? Also, I'm not sure if the last 2 steps are correct.

Edit: I was starting the sum at $k=0$, fixed it to $k=1$, and then changed the rest after that.

Edit: I found the answer on a book, it's $2^{2n}$, so my answer is wrong... Still, I don't know what I did wrong, or how to correctly solve this.

Are you sure $C_k^n$ denotes $\binom{k}{n}$ instead of $\binom{n}{k}$? It's the latter I've seen used, but it trivially makes the answer $2^n$, as all but the last term vanishes. — J.G., Dec 15 '19 at 13:04
Yes, in Russia they use $C_n^k$ to denote $\binom{n}{k}$. I double checked since I get confused with this. — Belen, Dec 15 '19 at 13:09
This is equivalent to showing that $$\sum_{k=0}^n\frac{(n+k)!}{2^kk!}=2^nn!$$ — ə̷̶̸͇̘̜́̍͗̂̄︣͟, Dec 15 '19 at 14:41

score 2 · Accepted Answer · answered Dec 15 '19 at 15:52

Let \begin{align} f(n) &=\sum_{k=0}^n2^k\binom{2n-k}{n}\\ &=\sum_{h=0}^n2^{n-h}\frac{(n+h)!}{n!h!} \end{align} Then \begin{align} f(n+1) &=\sum_{h=0}^{n+1}2^{n+1-h}\frac{(n+1+h)!}{(n+1)!h!}\\ &=\sum_{h=0}^{n+1}2\frac{n+1+h}{n+1}2^{n-h}\frac{(n+h)!}{n!h!}\\ &=2\sum_{h=0}^{n+1}2^{n-h}\frac{(n+h)!}{n!h!}+2\sum_{h=0}^{n+1}\frac{h}{n+1}2^{n-h}\frac{(n+h)!}{n!h!}\\ &=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+2\sum_{h=1}^{n+1}2^{n-h}\frac{(n+h)!}{(n+1)!(h-1)!}\\ &=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+\frac 12\sum_{h=1}^{n+1}2^{(n+1)-(h-1)}\frac{((n+1)+(h-1))!}{(n+1)!(h-1)!}\\ &=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+\frac 12\sum_{u=0}^{n}2^{(n+1)-u}\frac{((n+1)+u)!}{(n+1)!u!}\\ &=2f(n)+\frac{(2n+1)!}{n!(n+1)!}+\frac 12f(n+1)-\frac 12\frac{(2n+2)!}{(n+1)!(n+1)!}\\ \end{align} from which \begin{align} \frac 12f(n+1) &=2f(n)+\frac{(2n+1)!}{n!(n+1)!}-\frac 12\frac{(2n+2)!}{(n+1)!(n+1)!}\\ &=2f(n)+\frac{(2n+1)!}{n!(n+1)!}\left(1-\frac 12\frac{2n+2}{n+1}\right)\\ &=2f(n) \end{align} from which $f(n+1)=4f(n)$, hence $f(n)=4^n$.

score 1 · Answer 2 · answered Dec 15 '19 at 20:08

1

The number of binary numbers of length $2n$ whose $n+1^{th}$ 1 is in position $2n-k+1$ is ${2n-k\choose n}2^{k-1}$. Sum over $k$

answered Dec 15 '19 at 20:08

Empy2

50,853

Z Ahmed · Answer 3 · 2019-12-17T14:37:27.480

0

The given sum is nothing but $$S_n=\sum_{k=0}^{n} {2n-k\choose n} 2^k= \sum_{k=0}^{n} \left [ {2n-k-1\choose n} 2^k + {2n-k-1\choose n-1} 2^k \right] $$ $$\implies S_n=\frac{1}{2}S_n-\frac{1}{2} {2n \choose n}+ 2 S_{n-1}+\frac{1}{2} {2n \choose n} \implies S_n=4S_{n-1} \implies S_n =4^n$$

edited Dec 17 '19 at 14:37

answered Dec 16 '19 at 06:12

Z Ahmed

43,235

Calculate the sum: $C_{2n}^n+2C_{2n-1}^n+4C_{2n-2}^n+...+2^nC_n^n$

3 Answers3