8
$\begingroup$

I'm trying to prove the following: $$\sum_{k=0}^n 2^k\binom{2n-k}{n}=4^n$$

I've thought about induction, but there's not a very nice way to change the LHS from the $n$ case to the $n+1$ case by multiplying by $4$, at least, none that I can see.

I've also thought about trying to put a combinatorial argument together, by somehow arguing that the LHS counts $n$-letter words made from a $4$-letter alphabet, but I can't get the set being counted to partition in a way that sensibly represents the different terms of the sum.

I believe the identity is true, not only because I've tried a few small values of $n$, but also because Wolfram Alpha simplifies it for me. It just won't tell me how.

Thanks in advance for any insights.

Additional context: This identity arose while studying answers to this probability question: Expected number of draws to find a match

Improve this question
$\endgroup$
  • 3
    $\begingroup$ After a change of variables we get a (I think?) famous exercise. Anywho, other solutions are here math.stackexchange.com/questions/1128085/… $\endgroup$ – Countingstuff Apr 23 '18 at 23:34
  • $\begingroup$ Indeed, these two identities are the same. If we simply switch the roles of $k$ and $n-k$, and divide both sides of mine by $2^n$, we get that other one. Cool observation! $\endgroup$ – G Tony Jacobs Apr 24 '18 at 1:36
5
$\begingroup$

There is a nice combinatorial proof involving walks in the 2D plane.

Consider $4^n$ as the set of strings of $2n$ symbols, each of which is either $U$ or $R$, for "up" and "right". This determines a walk in a 2D lattice, starting at $(0,0)$ and ending at some point $(m,2n-m)$ for some $0\le m \le 2n$.

Let $S$ be the following set of points: $$ S=\{(n,n-k):0\le k\le n\}\cup\{(n-k,n):0\le k\le n\} $$ That is, $S$ consists of the lattice points on the top and right boundary of the square $[0,n]\times[0,n]$.

Every walk must eventually hit $S$. Consider the last point in $S$ that the walk visits. Whenever $k>1$, I claim that the number of walks for which the last point in $S$ they hit is $(n,n-k)$ is equal to $$ \binom{2n-k}{n}2^{k-1} $$ Namely, such a walk is determine by a path from $(0,0)$ to $(n,n-k)$, the number of which is $\binom{n+n-k}{n}$, followed by a "right" step, followed by ${k-1}$ arbitrary steps.

Combining this with the cases where the last visited point is on the top boundary of the square, $(n-k,n)$, and the case where the last visited point is $(n,n)$, your summation is attained.

Improve this answer
$\endgroup$
  • $\begingroup$ This is wonderful; thank you! Really elegant and clear :) $\endgroup$ – G Tony Jacobs Apr 24 '18 at 21:36

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.