4
$\begingroup$

Prove using combinatorics $\sum\limits_{r=0}^n2^{n-r}*\binom{n+r}{n}=2^{2n}$

The right side is choosing some persons from $2n$ people but I can't find a way to explain the left side it has both combination and power of $2$.Any hints?

$\endgroup$
1
$\begingroup$

Consider the set $S$ of all possible bitstrings of length $2n$. Given a bitstring $s \in S$, define $k$-prefix of $s$ as the shortest prefix bitstring of $s$ with either exactly $k$ $0$s or exactly $k$ $1$s. Since we are considering the shortest prefix, a $k$-prefix with exactly $k$ 1s ends with bit $1$; a $k$-prefix with exactly $k$ 0s ends with bit $0$.

Now, consider $(n+1)$-prefixes. Any $(n+1)$-prefix must be of length at least $n+1$ and at most $2n$. For a given length $n+1+r$ of $(n+1)$-prefixes ($0 \le r \le n-1$), there are $2 \cdot {{n+r}\choose{n}}$ possible such $(n+1)$-prefixes. Each $s \in S$ has a unique $(n+1)$-prefix, unless $s$ has exactly $n$ 0s and $n$ 1s. There are $2^{n-r-1}$ bitstrings in $S$ that share a given $(n+1)$-prefix of length $n+1+r$. The total number of bitstrings in $S$ is therefore: $$ {{2n}\choose{n}} + \sum_{r=0}^{n-1}2{{n+r}\choose{n}}\cdot 2^{n-r-1} = \sum_{r=0}^{n}{{n+r}\choose{n}}\cdot 2^{n-r} $$

$\endgroup$
0
$\begingroup$

Hint:

Consider monotonic lattice paths from $(0,0)$ to the line $y=2n-x$ that pass through the line $\smash{x=n+\frac{1}{2}}$ and that pass through the line $\smash{y=n+\frac{1}{2}}$ and those directly to the point $(n,n)$.

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