A three variable binomial coefficient identity

I found the following problem while working through Richard Stanley's Bijective Proof Problems (Page 5, Problem 16). It asks for a combinatorial proof of the following: $$ \sum_{i+j+k=n} \binom{i+j}{i}\binom{j+k}{j}\binom{k+i}{k} = \sum_{r=0}^{n} \binom{2r}{r}$$ where $n \ge 0$, and $i,j,k \in \mathbb{N}$, though any proof would work for me.

I also found a similar identity in Concrete Mathematics, which was equivalent to this one, but I could not see how the identity follows from the hint provided in the exercises.

My initial observation was to note that the ordinary generating function of the right hand side is $\displaystyle \frac {1}{1-x} \frac{1}{\sqrt{1-4x}}$, but couldn't think of any way to establish the same generating function for the left hand side.

Solution 1:

Restating your question, you are seeking to find the generating function of the left-hand-side: $$ g(x) = \sum_{n=0}^\infty x^n \sum_{i+j+k=n}\binom{i+j}{i} \binom{j+k}{j} \binom{k+i}{k} = \sum_{i=0}^\infty \sum_{j=0}^\infty \sum_{k=0}^\infty x^{i+j+k} \frac{(i+j)! (i+k)! (j+k)!}{i!^2 j!^2 k!^2} $$ First, carry out summation over $i$: $$ g(x) = \sum_{j=0}^\infty \sum_{k=0}^\infty x^{j+k} \frac{(j+k)!}{j!\cdot k!} {}_2F_1\left(1+j, 1+k; 1; x\right) $$ Now use Euler's transformation ${}_2F_1\left(1+j, 1+k; 1; x\right) = (1-x)^{-j-k-1} \, {}_2F_1\left(-j, -k; 1, x\right)$, which gives $$ g(x) = \frac{1}{1-x} \sum_{j=0}^\infty \sum_{k=0}^\infty \left(\frac{x}{1-x}\right)^{j+k} \frac{(j+k)!}{j!\cdot k!} {}_2F_1\left(-j, -k; 1; x\right) = \\ \frac{1}{1-x} \sum_{j=0}^\infty \sum_{k=0}^\infty \left(\frac{x}{1-x}\right)^{j+k} \frac{(j+k)!}{j!\cdot k!} \sum_{r=0}^{\min(j,k)} \binom{j}{r}\binom{k}{r} x^r = \\ \frac{1}{1-x} \sum_{r=0}^\infty x^r \sum_{j=r}^\infty \sum_{k=r}^\infty \binom{k+j}{k} \binom{j}{r}\binom{k}{r} \left(\frac{x}{1-x}\right)^{j+k} $$ Using $$ \sum_{j=r}^\infty \sum_{k=r}^\infty \binom{k+j}{k} \binom{j}{r}\binom{k}{r} z^{j+k} = \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \sum_{k=0}^\infty \frac{(k+j+r)!}{j! r! k!} z^k =\\ \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \binom{j+r}{j} \sum_{k=0}^\infty \frac{(j+r+1)_k}{k!} z^k = \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \binom{j+r}{j} \left(1-z\right)^{-j-r-1} = \\ \frac{z^{2r}}{(1-z)^{2r+1}} \frac{1}{r!^2} \sum_{j=0}^\infty \frac{(j+2r)!}{j!} \left(\frac{z}{1-z}\right)^j = \frac{z^{2r}}{(1-z)^{2r+1}} \binom{2r}{r} \left(1-\frac{z}{1-z}\right)^{-1-2r} = \binom{2r}{r} z^{2r} \left(1-2z\right)^{-2r-1} $$ we continue: $$ g(x) = \frac{1}{1-x} \sum_{r=0}^\infty x^r \binom{2r}{r} \left(\frac{x}{1-x}\right)^{2r} \left(1 - 2 \frac{x}{1-x} \right)^{-1-2r} = \\ \frac{1}{1-x} \sum_{r=0}^\infty \binom{2r}{r} \frac{1-x}{1-3x} \left(\frac{x^3}{(1-3x)^2}\right)^r = \\ \frac{1}{1-3x} \sum_{r=0}^\infty \binom{2r}{r}\left(\frac{x^3}{(1-3x)^2}\right)^r = \frac{1}{1-3x} \left(1 - 4 \frac{x^3}{(1-3x)^2}\right)^{-1/2} = \frac{1}{1-3x} \left( \frac{(1-4x)(1-x)^2}{(1-3x)^2}\right)^{-1/2} = \frac{1}{1-x} \frac{1}{\sqrt{1-4x}} $$ which is exactly the generating function of the right-hand-side: $$ \sum_{n=0}^\infty x^n \sum_{r=0}^n \binom{2r}{r} \stackrel{n=r+k}{=} \sum_{k=0}^\infty x^r \sum_{r=0}^\infty \binom{2r}{r} x^r = \frac{1}{1-x} \cdot \frac{1}{\sqrt{1-4x}} $$

Solution 2:

Short summary: On the right we are summing the number of words of $r$ $a$s and $r$ $b$s over $0\le r\le n.$ Denote the set of words with $r$ $a$s and $r$ $b$s by $U_r.$ On the left we are computing the number of triples of words, the first with $i$ $a$s and $j$ $b$s, the second with $j$ $a$s and $k$ $b$s, the third with $k$ $a$s and $i$ $b$s, for all $i+j+k=n.$ Denote this set of triples $V_n.$

Let $(x,y,z)\in V_n.$ Define $(x,y,z)$ to be $0$-padded if $x$ does not end in $b$ or $y$ does not end in $a.$ Define $(x,y,z)$ to be $r$-padded if $(x,y,z)=(x'b^r,y'a^r,z)$ where $(x',y',z)\in V_{n-r}$ is $0$-padded.

Then any word $w\in U_r$ can be written in a unique way as $w=x'y'z$ where $(x',y',z)\in V_r$ is $0$-padded. (This is proved below.) Then $(x'b^{n-r},y'a^{n-r},z)\in V_n$ is $(n-r)-padded.$ This establishes a bijection between $V_n$ on the left, and $U_0\cup U_1\cup\ldots\cup U_n$ on the right, thereby proving the identity. The elements of $U_n$ correspond to $0$-padded elements of $V_n,$ the elements of $U_{n-1}$ correspond to $1$-padded elements of $V_n,$ and so on.

Detailed answer: The expression $\binom{2r}{r}$ counts words constructed from $r$ $a$s and $r$ $b$s. The sum on the right counts all such words of lengths ranging from $0$ to $2n.$

On the left, we have the product $\binom{i+j}{i}\binom{j+k}{j}\binom{k+i}{k},$ which counts all words constructed by concatenating a word with $i$ $a$s and $j$ $b$s to a word with $j$ $a$s and $k$ $b$s to a word with $k$ $a$s and $i$ $b$s. Such words contain $i+j+k$ $a$s and $i+j+k$ $b$s. The sum is over all $i+j+k=n,$ so these words all have $n$ $a$s and $n$ $b$s.

These observations hint at the possibility of a bijection, but a few questions arise:

1. Can any word of $n$ $a$s and $n$ $b$s be constructed by concatenating a word with $i$ $a$s and $j$ $b$s to a word with $j$ $a$s and $k$ $b$s to a word with $k$ $a$s and $i$ $b$s, for suitable $i,$ $j,$ $k$?
2. Is it possible for a word to be constructed in more than one way by such a procedure?
3. What about words of length less than $2n$?

In answering the first question, we will actually answer all three.

Given a word $w$ of $n$ $a$s and $n$ $b$s, let's see if we can find $i+j+k=n,$ a word $x$ of $i$ $a$s and $j$ $b$s, a word $y$ of $j$ $a$s and $k$ $b$s, and a word $z$ of $k$ $a$s and $i$ $b$s such that $xyz=w.$ Observe that if such words can be found then $\lvert x\rvert=i+j\le i+j+2k=(j+k)+(k+i)=\lvert y\rvert+\lvert z\rvert.$ So $\lvert x\rvert\le n.$

We proceed by splitting $w$ into three, possibly empty, parts as follows: let $X$ consist of the first $P$ letters of $w,$ with $0\le P\le n,$ and let $I$ equal the number of $a$s in $X$ and $J$ the number of $b$s in $X$ (so that $I+J=P$). Let $K=n-I-J.$ Let $Z$ equal the string of letters from position $Q+1$ to $2n$ of $w,$ with $Q$ chosen so that $Z$ has $K$ $a$s. Note that $Q\ge P$ automatically holds: since the number of $a$s in $X$ is $I,$ the number of $a$s in the remainder of $w$ is $n-I\ge n-P=K.$ If $n-I>K,$ then there are $a$s to the right of $X$ and to the left of $Z$ and so $Q>P.$ If $n-I=K,$ then $J=0,$ and $X$ is simply a string of $I$ $a$s. So $Z$ contains all of the remaining $a$s and possibly some $b$s as well. Since $X$ contains no $b$s, we have $Q\ge P.$ So we may let $Y$ equal the string of letters from position $P+1$ to $Q$ of $w,$ giving $w=XYZ.$

So far we have that $I+J+K=n,$ that $X$ contains $I$ $a$s and $J$ $b$s, that $Z$ contains $K$ $a$s and $B:=2n-Q-K$ $b$s, and that $Y$ contains $n-I-K=J$ $a$s and $n-J-B$ $b$s. In order to obtain our desired partition of $w,$ we need $B=I.$ We claim that with suitable choices of $P$ and $Q,$ this can always be achieved.

To verify that this is so, we need to understand what happens as $P$ increases in steps of $1$ from $0$ to $n.$ To emphasize that $I,$ $J,$ and $K$ are functions of $P,$ we write $I(P),$ etc. We have already seen that there is always at least one possible value of $Q$ (and hence $B$) compatible with a given value of $P.$ There may, however, be more than one such compatible value, so we write $Q_l(P)$ and $Q_u(P)$ for the lower and upper bounds on $Q$ for a given $P.$ We have corresponding lower and upper bounds on $B,$ $$B_l(P)=2n-Q_u(P)-K(P)=n+P-Q_u(P)$$ and $$B_u(P)=2n-Q_l(P)-K(P)=n+P-Q_l(P).$$

When $P$ increases by $1,$ $K$ decreases by $1$: $K(P+1)=K(P)-1.$ If the letter of $w$ at position $P+1$ is $a$ then $I(P+1)=I(P)+1$ and $J(P+1)=J(P)$; if that letter is $b$ then $I(P+1)=I(P)$ and $J(P+1)=J(P)+1.$ Since $K(P)=n-P,$ the $K(P)^\text{th}$ $a$ from the right in $w$ is the $(P+1)^\text{st}$ $a$ from the left. Let $u$ be the position of the $P^\text{th}$ $a$ from the left in $w$ ($u=0$ if $P=0$) and let $v$ be the position of the $(P+1)^\text{st}$ $a$ from the left in $w$ ($v=2n+1$ if $P=n$). Then $Q_l(P)=u$ and and $Q_u(P)=v-1.$ In other words, if $\lvert X\rvert=P$ then $Z$ may start anywhere between the position immediately following the $P^\text{th}$ $a$ and the position of the $(P+1)^\text{st}$ $a.$ Notice that $Q_l(P+1)=v$ and therefore, that $Q_l(P+1)=Q_u(P)+1.$ This implies that $$B_u(P+1)=n+P+1-Q_l(P+1)=n+P+1-1-Q_u(P)=n+P-Q_u(P)=B_l(P).$$ Therefore, if $I(P)<B_l(P),$ then, since $I(P+1)$ is at most $I(P)+1,$ we have $I(P+1)\le B_u(P+1).$ On the other hand, $B_l(P)$ is non-increasing as $P$ increases from $0$ to $n,$ and ultimately equals $0.$ Therefore there must eventually be a $P$ such that $B_l(P)\le I(P)\le B_u(P).$ Once we find such a $P,$ we set $i=I(P),$ $j=J(P),$ $k=n-P,$ $x=X,$ $y=Y,$ $z=Z.$

Will this be the only solution? Not in general. Let there be a solution $(i,j,k,x,y,z)$ corresponding to a particular $P$ and $Q.$ If $y$ begins with $b$ and $z$ begins with $a$ then we get an additional solution by increasing both $P$ and $Q$ by $1.$ This results in the first $b$ of $y$ becoming the last letter of $x$ and the first $a$ of $z$ becoming the last letter of $y,$ which increases $j$ by $1$ and decreases $k$ by $1$ while leaving $i$ unchanged. The process obviously also works in reverse. There are no other ways to obtain additional solutions, for if the first letter of $y$ is $a,$ adding it to $x$ would force us to add a $b$ to $z,$ but $z$ cannot increase in length when $x$ increases in length.

In summary, all solutions for a particular word $w$ have the same $i.$ Equivalently, $\lvert y\rvert=j+k=n-i$ is the same for all solutions. The solution with minimum $j$ must be such that $x$ ends in $a$ or $y$ ends in $b.$ The solution with maximum $j$ must be such that $y$ begins with $a$ or $z$ begins with $b.$

Consider an example. Let $w=baabbbaaabab.$ Here $n=6.$ Then we have $$ \begin{array}{ccc|ccc} P & I(P) & J(P) & K(P) & [B_l(P),B_u(P)] & [Q_l(P),Q_u(P)]\\ \hline 0 & 0 & 0 & 6 & [5,6] & [0,1]\\ 1 & 0 & 1 & 5 & [5,5] & [2,2]\\ 2 & 1 & 1 & 4 & [2,5] & [3,6]\\ 3 & 2 & 1 & 3 & [2,2] & [7,7]\\ 4 & 2 & 2 & 2 & [2,2] & [8,8]\\ 5 & 2 & 3 & 1 & [1,2] & [9,10]\\ 6 & 2 & 4 & 0 & [0,1] & [11,12] \end{array} $$ We get three solutions, corresponding to $(P,Q)=(3,7),$ $(4,8),$ $(5,9).$ These are $$ \begin{aligned} &(i,j,k,x,y,x)=(2,1,3,baa,bbba,aabab),\\ &(i,j,k,x,y,x)=(2,2,2,baab,bbaa,abab),\\ &(i,j,k,x,y,x)=(2,3,1,baabb,baaa,bab). \end{aligned} $$

We have answered questions $1$ and $2$ in the affirmative. This suggests a way of producing a bijective proof of the identity. Let $W$ be the set of words of length at most $2n$ containing equal numbers of $a$s and $b$s. Let $S$ be the set of sextuples $(i,j,k,x,y,z)$ where $i,$ $j,$ $k$ are nonnegative integers satisfying $i+j+k=n,$ $x$ is a word consisting of $i$ $a$s and $j$ $b$s, $y$ is a word consisting of $j$ $a$s and $k$ $b$s, and $z$ is a word consisting of $k$ $a$s and $i$ $b$s. The map from $S$ to $W$ that simply concatenates $x,$ $y,$ and $z$ is not onto, since it only produces words of length $2n,$ and not one-to-one, as we have seen above. By modifying this simple concatenation map, we obtain a map that is both onto and one-to-one.

The map: Let $s=(i,j,k,x,y,z)\in S.$ If the last letter of $x$ is $b$ and the last letter of $y$ is $a,$ delete the last letter of both words. Repeat until $x$ or $y$ is empty or the last letter of $x$ is not $b$ or the last letter of $y$ is not $a.$ Denote the resulting words $x',$ $y'.$ We define $f:S\to W$ by $f(s)=x'y'z.$

The inverse map, applied to a word $w\in W$ with $N$ $a$s and $N$ $b$s, $0\le N\le n,$ is computed

1. by applying the algorithm described above to write $w=x'y'z,$ where $x'$ is a word with $i$ $a$s and $j'$ $b$s, $y'$ is a word with $j'$ $a$s and $k$ $b$s, $z$ is a word with $k$ $a$s and $i$ $b$s, $i+j'+k=N,$ and $j'$ is as small as possible,
2. by appending $n-N$ $b$s to $x'$ to form $x,$ appending $n-N$ $a$s to $y'$ to form $y,$ and
3. by forming the sextuple $(i,j'+n-N,k,x,y,z).$

Example from original answer: I've replaced my original answer with what I hope is a more convincing presentation, but this example from that answer may be helpful, so I leave it.

Suppose that $n=3.$ The right hand side enumerates the union of the following sets $$ \begin{aligned} &\{e\},\\ &\{ab,ba\},\\ &\{aabb,abab,abba,baab,baba,bbaa\},\\ &\{aaabbb,aababb,aabbab,aabbba,abaabb,ababab,ababba,abbaab,abbaba,abbbaa,\\ &\ \ baaabb,baabab,baabba,babaab,bababa,babbaa,bbaaab,bbaaba,bbabaa,bbbaaa\}. \end{aligned} $$ Here $e$ denotes the empty word. The left hand side enumerates words constructed as follows.

• Let $A$ be the set of words containing $i$ $a$s and $j$ $b$s. ($\lvert A\rvert=\binom{i+j}{i}$)
• Let $B$ be the set of words containing $j$ $a$s and $k$ $b$s. ($\lvert B\rvert=\binom{j+k}{j}$)
• Let $C$ be the set of words containing $k$ $a$s and $i$ $b$s. ($\lvert C\rvert=\binom{k+i}{k}$)

$$ \begin{aligned} &(i,j,k)=(0,0,3),\ A=\{e\},B=\{bbb\},C=\{aaa\}:\\ &\ \longrightarrow\{bbbaaa\}\\ &(i,j,k)=(0,1,2),\ A=\{b\},B=\{abb,bab,bba\},C=\{aa\}:\\ &\ \longrightarrow\{babbaa,bbabaa,\dot{b}bb\dot{a}aa=bbaa\}\\ &(i,j,k)=(0,2,1),\ A=\{bb\},B=\{aab,aba,baa\},C=\{a\}:\\ &\ \longrightarrow\{bbaaba,b\dot{b}ab\dot{a}a=baba,\dot{b}\dot{b}b\dot{a}\dot{a}a=ba\}\\ &(i,j,k)=(0,3,0),\ A=\{bbb\},B=\{aaa\},C=\{e\}:\\ &\ \longrightarrow\{\dot{b}\dot{b}\dot{b}\dot{a}\dot{a}\dot{a}=e\}\\ &(i,j,k)=(1,0,2),\ A=\{a\},B=\{bb\},C=\{aab,aba,baa\}:\\ &\ \longrightarrow\{abbaab,abbaba,abbbaa\}\\ &(i,j,k)=(1,1,1),\ A=\{ab,ba\},B=\{ab,ba\},C=\{ab,ba\}:\\ &\ \longrightarrow\{ababab,ababba,a\dot{b}b\dot{a}ab=abab,a\dot{b}b\dot{a}ba=abba,baabab,baabba,babaab,bababa\}\\ &(i,j,k)=(1,2,0),\ A=\{abb,bab,bba\},B=\{aa\},C=\{b\}:\\ &\ \longrightarrow\{a\dot{b}\dot{b}\dot{a}\dot{a}b=ab,ba\dot{b}a\dot{a}b=baab,bbaaab\}\\ &(i,j,k)=(2,0,1),\ A=\{aa\},B=\{b\},C=\{abb,bab,bba\}:\\ &\ \longrightarrow\{aababb,aabbab,aabbba\}\\ &(i,j,k)=(2,1,0),\ A=\{aab,aba,baa\},B=\{a\},C=\{bb\}:\\ &\ \longrightarrow\{aa\dot{b}\dot{a}bb=aabb,abaabb,baaabb\}\\ &(i,j,k)=(3,0,0),\ A=\{aaa\},B=\{e\},C=\{bbb\}:\\ &\ \longrightarrow\{aaabbb\} \end{aligned} $$ A dot over a letter indicates that the letter is to be deleted.

Solution 3:

Turns out, this indeed follows (relatively) directly from Strehl's identity.

Let's rewrite LHS in terms of $i$, $k$ and $l=i+j$: $$ \text{LHS}= \sum_{l+k=n}\sum_{i=0}^l\binom li\binom{k+l-i}{l-i}\binom{k+i}i= \sum_{l+k=n}\sum_{i=0}^l(-1)^l\binom li\binom{-k-1}{l-i}\binom{-k-1}i; $$ application of Strehl's identity to the internal sum (in that post's notation, for $n=-k-1$, $m=l$) yields $$ \sum_{l+k=n}\sum_i(-1)^l\binom{-k-1}i\binom li\binom{2i}l= \sum(-1)^{l-i}\binom{k+i}i\binom li\binom{2i}l= \sum(-1)^{l-i}\binom{k+i}i\binom i{l-i}\binom{2i}i; $$ the $\binom{2i}i$ terms suggests that we're almost there — and indeed what we've got is $$ \sum_{i=0}^n\binom{2i}i\sum_j(-1)^j\binom{n-j}i\binom ij $$ and the internal sum is (always) equal to 1 by Vandermonde convolution. QED.

Remark. In principle, this is not that far from being bijective, since we have a bijective proof of Strehl's identity — but that proof works only for positive parameters...

Solution 4:

The sum $$\sum_{p+q+r=n} {p+q\choose p} {p+r\choose r} {q+r\choose q}$$ with $p,q,r\ge 0$ is equal to

$$\sum_{p=0}^n \sum_{q=0}^{n-p} {p+q\choose q} {p+n-p-q\choose p} {q+n-p-q\choose q}$$ which is $$\sum_{p=0}^n \sum_{q=0}^{n-p} {p+q\choose q} {n-q\choose p} {n-p\choose q}.$$

Re-write this as $$\sum_{0\le p,q\atop p+q\le n} {p+q\choose q} {n-q\choose p} {n-p\choose q}.$$

We have using the residue operator

$${n-q\choose p} = \;\underset{u}{\mathrm{res}}\; (1+u)^{n-q} \frac{1}{u^{n-p-q+1}}$$ and $${n-p\choose q} = \;\underset{v}{\mathrm{res}}\; (1+v)^{n-p} \frac{1}{v^{n-p-q+1}}.$$

Observe carefully that these are zero when $p+q\gt n$ so we may extend the summation in $p$ and $q$ to infinity.

We get for the sum $$\;\underset{u}{\mathrm{res}}\; \frac{(1+u)^n}{u^{n+1}} \;\underset{v}{\mathrm{res}}\; \frac{(1+v)^n}{v^{n+1}} \sum_{p,q\ge 0} {p+q\choose q} \frac{u^{p+q} v^{p+q}}{(1+u)^q (1+v)^p}.$$

The inner term is

$$\sum_{q\ge 0} \frac{u^q v^q}{(1+u)^q} \sum_{p\ge 0} {p+q\choose q} \frac{u^p v^p}{(1+v)^p} = \sum_{q\ge 0} \frac{u^q v^q}{(1+u)^q} \frac{1}{(1-uv/(1+v))^{q+1}} \\ = \frac{1}{1-uv/(1+v)} \frac{1}{1-uv/(1+u)/(1-uv/(1+v))} \\ = \frac{1}{1-uv/(1+v)-uv/(1+u)} = \frac{(1+u)(1+v)}{(1+u)(1+v)-uv(2+u+v)} \\ = \frac{(1+u)(1+v)}{(1-uv)(1+u+v)}.$$

Substituting this into the residues yields

$$\; \underset{u}{\mathrm{res}}\; \frac{(1+u)^{n+1}}{u^{n+1}} \; \underset{v}{\mathrm{res}}\; \frac{(1+v)^{n+1}}{v^{n+1}} \frac{1}{(1-uv)(1+u+v)}.$$

Now we put $u/(1+u)=z$ and $v/(1+v)=w$ so that $u = z/(1-z)$ and $v = w/(1-w)$ and $du = 1/(1-z)^2 \; dz$ and $dv = 1/(1-w)^2 \; dw$ to get (these are independent)

$$\; \underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} \; \underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1}} \\ \times \frac{1} {(1-zw/(1-z)/(1-w))(1+z/(1-z)+w/(1-w))} \\ \times \frac{1}{(1-z)^2} \frac{1}{(1-w)^2} \\ = \; \underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} \; \underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1}} \frac{1}{(1-z-w)(1-zw)} \\ = \; \underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} \frac{1}{1-z} \; \underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1}} \frac{1}{(1-w/(1-z))(1-zw)} \\ = \; \underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} \frac{1}{1-z} \sum_{q=0}^n \frac{z^{n-q}}{(1-z)^q} \\ = \sum_{q=0}^n [z^q] \frac{1}{(1-z)^{q+1}} = \sum_{q=0}^n {2q\choose q}.$$

This is the claim.