How to prove $f(n)=\sum_{k=0}^n\binom{n+k}{k}\left(\frac{1}{2}\right)^k=2^n$ without using the induction method? [duplicate]

Solution 1:

I don’t know that there’s a really easy combinatorial argument, but certainly combinatorial arguments can be made. The one that I offer below is essentially the same as Phicar’s (which I’ve upvoted, and which you should definitely examine), but I’ve phrased it in slightly more elementary terms and gone into more detail, given your comment about being kind of a beginner.

As Thomas Andrews suggested in the comments, it’s a good idea to multiply both sides by $2^n$ to get rid of the fractions. I will also use the fact that $\binom{n+k}k=\binom{n+k}n$, since having a constant lower number is likely to make life a little easier. This turns the desired identity into the equivalent identity

$$\sum_{k=0}^n\binom{n+k}n2^{n-k}=2^{2n}\tag{1}$$

The most straightforward interpretation of $2^{2n}$ is that it is the number of subsets of the set $[2n]=\{1,2,\ldots,2n\}$. In that context the general term

$$\binom{n+k}n2^{n-k}$$

looks like the number of ways to choose $n$ members of the set $[n+k]$ together with any subset of $[2n]\setminus[n+k]=\{n+k+1,\ldots,2n\}$; every subset of $[2n]$ that has exactly $n$ elements in $[n+k]$ is counted here. There are two problems with this idea. First, even after we sum over $k$ we are counting only subsets of $[2n]$ that have at least $n$ elements, while the $2^{2n}$ on the righthand side counts all subsets of $[2n]$. Secondly, when we sum over $k$ we end up counting some subsets more than once. For instance, the subset $[n]$ is counted once for each $k$ from $0$ through $n$, because it has exactly $n$ members in $[n+k]$ for each $k$. Somehow we have to make $k$ tell us a bit more about the subset.

For starters, since we seem to be counting only subsets of $[2n]$ with at least $n$ elements, let’s do it right. For each $k\in\{0,1,\ldots,n\}$ we’ll count the subsets of $[2n]$ that have at least $n$ elements and whose $n$-th element is exactly $n+k$. There are $\binom{n+k-1}{n-1}$ ways to choose $n-1$ members of $[2n]$ that are smaller than $n+k$; those $n-1$ elements together with $n+k$ itself give us a set of $n$ elements of $[2n]$ whose $n$-th element is $n+k$, and we can then pad that with any subset of $[2n]\setminus[n+k]$ and still have a subset of $[2n]$ whose $n$-th element is $n+k$. There are $n-k$ elements of $[2n]$ bigger than $n+k$, so there are $2^{n-k}$ ways to choose some set of these to throw in with our first $n$ elements, and there are therefore

$$\binom{n+k-1}{n-1}2^{n-k}$$

ways to choose at least $n$ elements of $[2n]$ so that the $n$-th is $n+k$. Summing over the possible values of $k$, we see that there are exactly

$$\sum_{k=0}^n\binom{n+k-1}{n-1}2^{n-k}\tag{2}$$

subsets of $[2n]$ with at least $n$ elements.

To finish the job of counting subsets of $[2n]$, we need to count the subsets that have fewer than $n$ elements. We’d like to count these in a way that looks as much as possible like what we’ve already done, so that with luck we can combine our calculation with $(2)$ and simplify to get $(1)$. One way to do that is to count the complements of these sets instead, so that we’re counting the subsets of $[2n]$ that have strictly more than $n$ elements: after all, each set has a unique complement, so the total number will be the same.

Each subset of $[2n]$ with more than $n$ elements has at minimum $n+1$ elements, and we can mimic what we did before by counting them according to their $(n+1)$-st element. How many of these sets have $n+k$ as their $(n+1)$-st element? We must choose $n$ members of $[2n]$ that are smaller than $n+k$, which we can do in $\binom{n+k-1}n$ ways, and then we can throw in any subset of the $n-k$ members of $[2n]$ that are bigger than $n+k$, so there must be

$$\binom{n+k-1}n2^{n-k}$$

subsets of $[2n]$ with more than $n$ elements and whose $(n+1)$-st element is $n+k$. Summing over the possible values of $k$, we find that $[2n]$ has

$$\sum_{k=1}^n\binom{n+k-1}n2^{n-k}=\sum_{k=0}^n\binom{n+k-1}n2^{n-k}$$

subsets with more than $n$ elements. (Clearly $k=0$ is impossible this time, but there’s no harm in including it, since $\binom{n-1}n=0$, and the $k=0$ term therefore doesn’t change the sum anyway.) The complements of these sets are the subsets of $[2n]$ with fewer than $n$ elements, so there are

$$\sum_{k=0}^n\binom{n+k-1}n2^{n-k}$$

of those as well. It follows that $[2n]$ has

$$\sum_{k=0}^n\binom{n+k-1}{n-1}2^{n-k}+\sum_{k=0}^n\binom{n+k-1}n2^{n-k}$$

subsets.

Now just combine the two summations into one and apply Pascal’s identity, and you’re home free.

Solution 2:

Keeping in mind what Andrews has told you, you know that $2^{2n}$ counts the binary strings (String as $x=x_1x_2\ldots x_{2n}$) of length $2n$ (i.e., Set $\{0,1\}^{2n}$).

Note that you have either two possibilities for a string $x$ in that set. Either, $|x|_1\geq |x|_0$ or $|x|_1<|x|_0$, where $|x|_a$ is defined to be the number of times $a$ appears in the string. So $\{0,1\}^{2n}=A\bigcup B$, where $A=\{x\in \{0,1\}^{2n}:|x|_1\geq |x|_0\}$ and $B=\{x\in \{0,1\}^{2n}:|x|_1< |x|_0\}$ (Note that $A\bigcap B=\emptyset$, so $2^{2n}=|\{0,1\}^{2n}|=|A|+|B|$). It is not difficult to see that if $x\in A$, then $|x|_1\geq n$ so let's define a family of strings $$A_i = \left\{x\in \{0,1\}^{2n}:\sum _{k=0}^{n+i}x_k=n \wedge \sum _{k=0}^{n+i-1}x_k=n-1 \right\}\;,$$ which partitions $A$ because if $x\in A$ there must be an index $m$ such that $x_1x_2\cdots x_m$ contains $n$ 1's. and there is no prefix of it that contains $n$ 1's.

Now, $|A_i|=\binom{n+i-1}{n-1}2^{n-i}$ because we know that before $n+i$ there are $n-1$ ones, and we do not know what is after $n+i$ (there are $2n-n-i$ positions to fill). So

$$\begin{align*}|A|&=\sum _{i=0}^n |A_i|\\ &=\sum _{i=0}^n \binom{n+i-1}{n-1}2^{n-i}\\ &=\sum _{i=0}^n\left( \binom{n+i}{n}-\binom{n+i-1}{n}\right)2^{n-i}\\ &=\sum _{i=0}^n \binom{n+i}{n}2^{n-i}-\sum _{i=0}^n\binom{n+i-1}{n}2^{n-i}\;, \end{align*}$$

where the last step is by Pascal's recursion.

Note that $2^{2n}=|A|+|B|$ and $|A|=\sum _{i=0}^n \binom{n+i}{n}2^{n-i}-\sum _{i=0}^n\binom{n+i-1}{n}2^{n-i}$, so if you prove $|B|=\sum _{i=0}^n\binom{n+i-1}{n}2^{n-i}$ you are done.

Hint: Do exactly the same analysis as in $A$ but you know that, in this case, $|x|_0\geq n+1$.

Solution 3:

Here is a generating function proof that avoids (or hides) the induction. $$ \begin{align} f(x) &=\sum_{n=0}^\infty\sum_{k=0}^n\binom{n+k}{k}\left(\frac12\right)^{n+k}x^n\tag{1}\\ &=\sum_{n=0}^\infty\sum_{k=0}^n\left[\binom{n+k-1}{k}+\binom{n+k-1}{k-1}\right]\left(\frac12\right)^{n+k}x^n\tag{2}\\ &=\sum_{n=0}^\infty\sum_{k=0}^n\binom{n+k-1}{k}\left(\frac12\right)^{n+k}x^n+\sum_{n=0}^\infty\sum_{k=0}^{n-1}\binom{n+k}{k}\left(\frac12\right)^{n+k+1}x^n\tag{3}\\ &=\frac12+\sum_{n=0}^\infty\sum_{k=0}^{n-1}\binom{n+k-1}{k}\left(\frac12\right)^{n+k}x^n+\sum_{n=0}^\infty\sum_{k=0}^n\binom{n+k}{k}\left(\frac12\right)^{n+k+1}x^n\tag{4}\\ &=1+\sum_{n=0}^\infty\sum_{k=0}^{n-1}\binom{n+k-1}{k}\left(\frac12\right)^{n+k-1}x^n\tag{5}\\ &=1+\sum_{n=0}^\infty\sum_{k=0}^n\binom{n+k}{k}\left(\frac12\right)^{n+k}x^{n+1}\tag{6}\\[9pt] &=1+x\,f(x)\tag{7} \end{align} $$ Explanation:
$(2)$: Pascal's Triangle relation
$(3)$: substitute $k\mapsto k+1$ in the right-hand sum
$(4)$: use $\binom{2n-1}{n}\left(\frac12\right)^{2n}=\binom{2n}{n}\left(\frac12\right)^{2n+1}$ for $n\ge1$ to move $x^n$ term from the left to the right sum
$(5)$: twice $(4)$ minus $(1)$
$(6)$: substitute $n\mapsto n+1$
$(7)$: compare $(1)$ and $(6)$

Note that $(7)$ implies that $$ \begin{align} f(x) &=\frac1{1-x}\\ &=\sum_{n=0}^\infty x^n\tag{8} \end{align} $$ Comparing the coefficients of $(1)$ and $(8)$ yields $$ \bbox[5px,border:2px solid #C0A000]{\sum_{k=0}^n\binom{n+k}{k}\left(\frac12\right)^{n+k}=1}\tag{9} $$

Postscript

I think it is interesting to note that $$ \begin{align} \sum_{k=0}^\infty\binom{n+k}{k}x^{n+k} &=\sum_{k=0}^\infty(-1)^k\binom{-n-1}{k}x^{n+k}\\ &=\frac{x^n}{(1-x)^{n+1}}\tag{10} \end{align} $$ Setting $x=\frac12$ in $(10)$ yields $$ \sum_{k=0}^\infty\binom{n+k}{k}\left(\frac12\right)^{n+k}=2\tag{11} $$ Thus, exactly half of the sum resides in the first $n+1$ terms.