# Proving $\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n$ [duplicate]

Some background.

I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that there are two solutions $\pm f$ and that $f$ is multiplicative. Next, I would have to evaluate $f$ at prime powers. I constructed a few values and my conjecture is that $$f(p^n)=\frac{2n-1\choose n}{2^{2n-1}}$$ for $p$ prime and $n>0$. To prove this, I only need to show that

$$\sum_{k=1}^n{2k-1\choose k}{2n-2k+1\choose n-k+1}=4^n-{2n+1\choose n+1}\qquad\text{for }\;n\geq0.$$ (This is simply expressing $(f*f)(p^{n+1})=1$ explicitly, plugging in the conjecture.)

For readers who don't really understand what I'm talking about and who are merely interested in the proof of the identity, you can just start reading from here.

Hoping for a combinatorial proof, I interpreted the summation as follows. Given a set of $n+1$ indistinguishable marbles and $n+1$ distinguishable bags (say $b_1,\ldots,b_{n+1}$), the term ${2k-1\choose k}{2n-2k+1\choose n-k+1}$ counts the number of ways to put the marbles in the bags such that there are exactly $k$ marbles in the first $k$ bags $b_1,\ldots,b_k$.

Equivalently, if we identify a configuration of the marbles with a monotonic path in a $n+1\times n+1$ grid such that the path starts in the bottom left corner and ends in the upper right corner, the sum $${2n+1\choose n+1}+\sum_{k=1}^n{2k-1\choose k}{2n-2k+1\choose n-k+1}$$ counts the number of times a path 'crosses' or 'touches' the main diagonal in a point that is not the 'origin', if we summate over all possible paths. (There are ${2n+2\choose n+1}$ such paths in total.) For example, the following path touches the main diagonal $4$ times: At $(2,2)$, $(3,3)$, $(4,4)$ and $(7,7)$.

(We do not count $(0,0)$ because the summation doesn't.) However, interpreting the summation like this I can't get any further. Any other ideas or suggestions on how to approach this problem?

Edit: There are some errors in my reasoning above, let's try again.

Using the identity ${2n-1\choose n}=\frac12{2n\choose n}$ it can be rewritten as $$\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n$$ which looks much better and holds for all $n\geq0$, making it more naturally. This form may give some ideas for combinatorial proofs but I don't really see any.

The term ${2k\choose k}{2n-2k\choose n-k}$ counts the number of $n\times n$ monotonic paths intersecting the diagonal at $(k,k)$. So the summation counts the number of intersection points with the diagonal (all of them this time, including the origin) summing over all paths.

As in Arthur's comment, it would suffice to find a bijection between all $2n$-monotonic paths (no matter their width or height) and the pairs $(p,s)$ where $p$ is a $n\times n$ path and $s$ an intersection point with the diagonal. Perhaps there is a weird bijection which would then solve the question.

For the sake of a proof with induction, I considered all paths that intersect the diagonal for the first time at $(k,k)$ and all possible continuations and their intersection points, summed for $k$ from $1$ to $n$ using the induction hypothesis and a trick with Catalan numbers. (Writing out the details would be tedious, I think the reasoning becomes clear when you see the sum.)

It turns out to be sufficient to prove

$$\sum_{k=1}^n2C_{k-1}\left(4^{n-k}+{2n-2k\choose n-k}\right)=4^n$$ where $C_n=\frac1{n+1}{2n\choose n}$ denotes the $n$th Catalan number. However this doesn't seem to be a simplification.

## marked as duplicate by punctured dusk, Community♦Apr 8 '15 at 15:31

• The term $\binom{2n + 1}{n + 1}$ fits into your sum as the term for $k = n + 1$. And $4^n = 2^{2n}$ is the total number of length $2n$ monotonic paths, regardless of end point (that is, monitonic paths that end up along a diagonal). Maybe you can work $$\binom{2k-1}{k}\binom{2n-2k + 1}{n-k+1}$$ into the number of paths with end point at $(k-1, 2n-k + 1)$ or $(2n-k + 1, k-1)$? – Arthur Feb 23 '14 at 15:39
• @Arthur I was aware that we can include that term in the summation but I didn't want to make it confusing with ${-1\choose0}$. I don't think counting something with $2n$-monotonic paths will be easy. Could you explain what you intend with that last sentence? – punctured dusk Feb 23 '14 at 15:47
• What I mean with that last sentence is that there are $2n + 1$ possible end points, but we sum from $1$ to $n+1$, so each term in the sum should in that case cover two end points, except the last one. I haven't sat down with the binomials to see if it makes sense, I'm just babbling on about the first ideas I get. – Arthur Feb 23 '14 at 18:53
• – punctured dusk Nov 10 '14 at 11:20
• – darij grinberg Feb 10 '15 at 19:14

Here's an elementary combinatorial proof. Let $$q(m)=\sum_{k=0}^m{2k\choose k}{2m-2k\choose m-k}.$$ As in the question, $q(m)$ counts the number of times a monotonic $m$-path (by which we mean a lattice path from $(0,0)$ to $(m,m)$ consisting of unit steps to the east and unit steps to the north) touches the diagonal (including at its beginning and its end), summed over all paths. We will prove that $q(m)=4^m$ for all $m$. It clearly is for $m=0$. Suppose $q(m)=4^m$ is true for all $m$ up to $n-1$, where $n\geqslant1$.

The induction hypothesis allows us to count the number of times a monotonic $n$-path touches the diagonal in a cleaner way: Any path touches the diagonal in the origin. For a path $p$ denote $t_p$ the x (or y) coordinate of the next meeting point with the diagonal. (So $t_p\in\{1,\ldots,n\}$ for any $n$-path $p$.) The number of paths from $(0,0)$ to $(k,k)$ with $t_p=k$ is $2C_{k-1}$ (see Wikipedia; note that in our case the path should not only stay at the same side of the diagonal but it shouldn't even touch it, which is why we have $C_{k-1}$ and not just $C_k$). Here as usual $C_n=\frac1{n+1}{2n\choose n}$ denotes the $n$th Catalan number.

A monotonic $n$-path from $(0,0)$ to $(n,n)$ with $t_p=k$ touches the diagonal once at the origin and then follows a monotonic $n-k$-path. For fixed $k$, the number of touches with the diagonal, counting only those $n$-paths that satisfy $t_p=k$, is $2C_{k-1}\cdot q(n-k)$ plus the number of possible paths with $t_p=k$ (because of that one touch in the origin), which is $2C_{k-1}\cdot\binom{2n-2k}{n-k}$. Summing over $k$ gives $$q(n)=\sum_{k=1}^n2C_{k-1}\left(q(n-k)+\binom{2n-2k}{n-k}\right).$$

By the induction hypothesis, $$q(n)=\sum_{k=1}^n2C_{k-1}\left(4^{n-k}+\color{red}{\binom{2n-2k}{n-k}}\right).$$ What follows is an algebraic manipulation to show that this is indeed equal to $4^n$. Using the identity $2C_k=\frac 2{k+1}\binom{2k}{k}=\color{green}{4\binom{2k}{k}}-\color{blue}{\binom{2k+2}{k+1}}$ this can be rewritten as $$\underbrace{\color{green}4\sum_{k=1}^n\color{green}{\binom{2k-2}{k-1}}\color{red}{\binom{2n-2k}{n-k}}}-\underbrace{\sum_{k=1}^n\color{blue}{\binom{2k}{k}}\color{red}{\binom{2n-2k}{n-k}}}+\underbrace{\sum_{k=1}^n\left(\color{green}{4\binom{2k-2}{k-1}}-\color{blue}{\binom{2k}{k}}\right)4^{n-k}}$$ which is $$\underset{\text{(Ind. Hyp.}\\\text{for }m=n-1)}{\underbrace{4\cdot4^{n-1}}}-\underset{\text{(Def. of }q(n))}{\underbrace{q(n)+{2n\choose n}}}+\underset{\text{(Telescoping)}}{\underbrace{4^n-{2n\choose n}}}=2\cdot4^n-q(n).$$ Hence $$q(n)=2\cdot4^n-q(n)$$ and the conclusion follows.

• Nice argument! I have tried to improve the writing a bit. – darij grinberg Feb 11 '15 at 15:38

I will prove your edited formula, which is much nicer.

There is a simple solution (two lines) via generating functions. In particular, read the 2nd example which uses convolutions.

Consider the generating functions which gives us $a_n = { 2n \choose n }$. Let this be denoted by $a(x)$.

Consider the generating functions which gives us $b_ n = 4 ^n$. Clearly, this is generated by $b(x) = \frac{1}{1-4x}$.

Then, the statement claims that

$$a(x) ^ 2 = b( x).$$

All that is left to do, is to show that

$$a(x) = \frac{1}{ \sqrt{ 1 - 4 x } }$$

This is obvious / well known.

Consider the taylor series expansion $$(1/(1-x))^\frac12=\sum_{k \ge 0} \frac{(2k-1)!!}{(2k)!!}x^k,\tag{1}$$ whose square is of course the desired sequence of all coefficients $1$ in front of the $x$ powers, and whose coefficients are successively $1,1/2,3/8,5/16,35/128,$ which match your values for $f(p^n).$ [I think it should be easy to manipulate the double factorial term format of the coefficients in $(1)$ to your version of $2n-1$ choose $n$ over $2^(2n-1).$] In $(1)$ the double factorials are as usual by successively decreasing terms by $2$, e.g. $5!!=5\cdot 3 \cdot 1.$ The explicit form of $(1)$ in terms of the double factorial ratios for coefficients comes from a formula in Gradshteyn & Ryzhic, which in the 1980 edition of "Tables of Integrals, Series, and Products" appears on page 21, and is formula 1.112 (4) with its $x$ replaced by $-x.$

Anyway given that the expansion $(1)$ is the correct one for that squareroot, and also given that its coefficients match up with the ones you have conjectured, it follows by the way ordinary series multiply that the terms are correct for the Dirichlet square of that part of the product for powers of $p$ to wind up as the ordinary series of $1$ in front of each power.

I realize I'm missing some details as to setting this all up. But I think it interesting that the usual taylor series of the squareroot of $1/(1-x)$ has its coefficients matching your $f(p^n)$, and in one book on analytic number theory I have consulted, such switching back and forth between Dirichlet series and ordinary ones is justified when the given function is prime-independent and multiplicative. I'll add more on this eventually but wanted to enter the answer now in case it's of any immediate use.

• The question comes from a book on Analytic number theory too. In one of the next chapters this question is repeated but then it is explicitly asked to use Dirichlet series. So I suppose it can be done without. – punctured dusk Feb 24 '14 at 7:39
• @barto Yes, without Dirichlet the identity can be (after a lot of algebra) be shown to follow from the above taylor series for squareroot of $1/(1-x).$ By the way your conjectured term has also the more symmetric form $C(2n,n)/4^n$ and using this one doesn't encounter the problem of the $C(-1,0)$ term. – coffeemath Feb 24 '14 at 7:54