Combinatorial proof of identity involving central binomial coefficients

The identity I am interested in reads, $$ \sum_{k=0}^{n-1} {2k \choose k} \cdot 2^{2(n-k)} = 2n \cdot {2n \choose n}. $$ It is not hard to prove using the generating functions, but it seems that there should be a combinatorial argument. I tried different ideas with lattice path counting, but without success.

Update: I found a related discussion here, however, among the many arguments there is no combinatorial one.

Update 2: it seems I have found a combinatorial proof (quite indirect), but will post it only after the bounty expires. I hope someone comes up with an answer before this so that the bounty is not wasted.

Solution 1:

At the risk of adding even more verbiage to an already long post, I've appended a section on the intuitive ideas behind the bijective proof. It seemed to me that my original explanation did not make it sufficiently clear how simple and natural the bijection is.

A forward-moving walk is a walk on a square grid in which every step is either upward or towards the right. Such a walk is balanced if it has an equal number of up steps and right steps. Forward-moving walks will be represented as strings of the letters $r$ (for "right") and $u$ (for "up"). Let $w_1\vee w_2$ denote the concatenation of walks $w_1$ and $w_2$ and let $\overline{w}$ denote the walk in which every $r$ in $w$ is changed to a $u$ and every $u$ is changed to an $r$. If $w$ is balanced then if $w$ and $\overline{w}$ start at the same grid point, they will also end at the same grid point.

The right side of the identity counts forward-moving balanced walks of $2n$ steps with one marked step. We will represent such walks as pairs $(v,i)$ where $v$ is the walk and $i$ is the index of the marked step. Call this set of pairs $\mathcal{V}$.

The left side counts pairs of forward-moving walks in which the first element of the pair is a walk of $2n-2k$ steps and the second element is a balanced walk of $2k$ steps, where $k$ satisfies $0\le k\le n-1$. Call this set of pairs $\mathcal{W}$.

Now define a bijection between $\mathcal{V}$ and $\mathcal{W}$. The maps $f$ and $g$ defined below are invertible, and, in fact, inverses of each other.

Let $f:\mathcal{V}\to\mathcal{W}$ be defined as follows: let $(v,i)\in V$ and split $v$ as $v_1\vee v_2\vee v_3$, where $v_1$ has length $i$ and where $v_2$ is a balanced walk chosen to have greatest possible length (which may be $0$). Then let $f(v)=(v_1\vee\overline{v}_3,v_2)$. Letting $2k$ denote the number of steps in $v_2$, we see that $0\le k\le n-1$ since $v_1$ has length greater than or equal to $1$. Hence $f(v)$ is indeed an element of $\mathcal{W}$.

Let $g:\mathcal{W}\to\mathcal{V}$ be defined as follows: let $(w,x)\in\mathcal{W}$ with $w$ a forward-moving walk of length $2n-2k$ and $x$ a forward-moving balanced walk of length $2k$ for some $k$ satisfying $0\le k\le n-1$. Split $w$ as $w_1\vee w_2$, where $w_2$ is the shortest walk (possibly of length $0$) with the property that $w_1\vee\overline{w}_2$ is balanced. Then let $g((w,x))=(w_1\vee x\vee \overline{w}_2,\lvert w_1\rvert)$, where $\lvert w_1\rvert$ denotes the length of $w_1$. That is, the last step of $w_1$ is the marked step.

To see that $w_2$ always exists note that the imbalance of $w$ is the difference between the number of $r$ steps and the number of $u$ steps. Since $\lvert w\rvert$ is even, this difference is even. The imbalance of $\overline{w}$ is equal in magnitude and opposite in sign to that of $w$. As $w$ is transformed into $\overline{w}$ by changing $r$ to $u$ and $u$ to $r$ one step at a time, starting with the last step and working back to the first step, the imbalance changes by $\pm2$ each time, and hence must at some point be $0$. Furthermore, this must happen before the first step is reached since either the imbalance is initially $0$, in which case $w_2$ can be taken to be the empty walk, or else the imbalance of both $w$ and $\overline{w}$ is non-zero, and balance must therefore occur at some intermediate step.

Added (intuition) In the following, "walk" will always mean "forward-moving walk". Since $2^{2k}$ counts walks of $2k$ steps and $\binom{2k}{k}$ counts balanced walks of $2k$ steps, the identity is evidently telling us something about the relationship between walks and balanced walks.

To get a feel for the problem, first consider some inequalities. Obviously the number of walks exceeds the number of balanced walks of the same length, since the latter are a subset of the former. On the other hand, the number of balanced walks with one marked step exceeds the number of (unmarked) walks of the same length since $\binom{2k}{j}$ is sharply peaked around $j=k$ and therefore $\sum_{j=0}^{2k}\binom{2k}{j}$, which counts the walks, is generally far smaller than $1+2k\binom{2k}{k}$, which, if the $1$ is omitted, equals the number of balanced walks with marked step.

Now for how to interpret the identity?

Key transformation: Any walk can be turned into a balanced walk of the same length by reflecting a tail, that is, reflecting all steps after a certain point in the walk about the $45^\circ$ line through the point (equivalently, swapping $r$ steps and $u$ steps after the point). Why this is always possible is explained in the last paragraph of my original answer. It can happen that it is possible to do this in more than one way, but there will be an outermost reflection point, which is the one that requires reflecting the shortest possible tail. If there is more than one reflection point, the part of the walk between two reflection points will be a balanced walk. Reflecting these parts of the walk is optional as their effect on the balance is neutral.

Toward a bijective proof: To find a bijective proof, the obvious thing to do is a is to explore alternative ways of representing balanced walks with one marked step. One way would be simply to split the walk after the marked step and to use the resulting pair to represent the walk. But the resulting walks don't have any simple characterization.

Another possibility is to transform the walk somehow so that the location of the marked step is implicit in the structure of the transformed walk and can be deduced from it, rather than being explicitly given. The key transformation suggests that one try reflecting the part of the walk that comes after the marked step, the thought being that one might deduce the position of the mark by locating the reflection point that restores balance. The problem with this, of course, is that it can happen that there are multiple such reflection points, leaving the position of the mark ambiguous.

So this second method fails, but the manner in which it fails suggests the fix, which is to use the reflection idea and the splitting idea together. If we end up with a walk for which balance can be restored in multiple ways, it must be because a part of the original walk immediately following the marked step is a balanced walk. So we excise this part—specificially, we cut out the longest balanced section following the marked step that we can. We then reflect the remaining part of the tail. The reflection point of the resulting walk that restores balance is now unambiguous. Of course, we also have to record the part of the walk that we excised so that we can recover the original balanced walk.

Solution 2:

Here is my combinatorial proof (which I like less than that by Will Orrick, since it involves a transformation of the original formula).

Lemma The number of permutations of $2n$ elements having only even cycles is $((2n-1)!!)^2$.

Proof. Take the minimal element (this is $1$ currently). There are $2n - 1$ choices for its image $x=\sigma(1)$, and $2n-1$ choices for the image $\sigma(x)$ of $x$. If $\sigma(x) = 1$, then the cycle closes, and we take the element $y$ which is minimal among the rest. Otherwise, denote $y=\sigma(x)\neq 1$, and the cycle continues. In any case, there are $2n-3$ choices for $z=\sigma(y)$, $2n-3$ choices for $\sigma(z)$ etc.

Now rewrite the identity in question as $$ \sum_{k=1}^n 2^{2k} {2(n-k) \choose n-k} = 2n\cdot {2n \choose n}, $$ multiply by $(2n-1)!$ and divide by $2^{2n}$. Then, the right-hand side becomes $$ \biggl(\frac{(2n)!}{2^n n!}\biggr)^2 = \bigl((2n-1)!!\bigr)^2, $$ which, as we have shown, counts permutations of $2n$ elements having even cycles. The left-hand side becomes $$ \sum_{k=1}^{n} \frac{(2n-1)!}{(2(n-k))!}\biggl(\frac{(2(n-k))!}{2^{n-k} (n-k)!}\biggr)^2 = \sum_{k=1}^{n} \frac{(2n-1)!}{(2(n-k))!} \cdot \bigl((2(n-k)-1)!!\bigr)^2, $$ which counts the same, since $$ \frac{(2n-1)!}{(2(n-k))!} $$ is the number of ways one can form a cycle of length $2k$, $k=1,\dots,n$, containing $1$, and $((2(n-k)-1)!!)^2$ is the number of permutations with even cycles on the remaining $2(n-k)$ elements.