I recently discovered the following formula. (I'm probably not the first person to figure it out but I couldn't find it anywhere).

For all \(n \in \mathbb{W}\), the following holds:

\[\sum_{k=0}^{n}\binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n\]

See if you can prove it :)

## Comments

Sort by:

TopNewestThere is a simple solution (two steps) via generating functions. In particular, read the 2nd example (in the wiki link) 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} \) from Taylor Series.

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 well known. Simply prove that

\[ { 2n \choose n } = ( -4) ^n { - \frac{1}{2} \choose n } \]

Note I have seen this formula before. In fact, I believe that (but am not certain) it's in Koh Khee Meng's book, which is why that is my immediate approach. – Calvin Lin Staff · 2 years, 1 month ago

Log in to reply

– Ishan Singh · 7 months, 2 weeks ago

Nice solution. Some other ways would be to use Snake Oil method or Beta Function.Log in to reply

– Ariel Gershon · 2 years, 1 month ago

I don't understand what is \(\binom{-1/2}{n}\)?Log in to reply

Binomial coefficients. There are negative and fractional binomial coefficients. This allows us to evaluate \( ( 1 + x) ^ r \) even when \( r \) is not a positive integer. We have

\[ ( 1 + x ) ^ r = 1 + { r \choose 1 } x + { r\choose 2 } x ^ 2 + \ldots \] – Calvin Lin Staff · 2 years, 1 month ago

Log in to reply

From a paper on inverse elliptic functions and Legendre polynomials, we have

\(\dfrac { 2 }{ \pi } \displaystyle \int _{ 0 }^{ \dfrac { \pi }{ 2 } }{ { \left( { x }^{ 2 }{ Sin }^{ 2 }\theta +{ Cos }^{ 2 }\theta \right) }^{ n }d\theta =\dfrac { 1 }{ { 4 }^{ n } } } \displaystyle \sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} 2k \\ k \end{matrix} \right) \left( \begin{matrix} 2(n-k) \\ n-k \end{matrix} \right) { x }^{ 2k } \right) } \)

and so, for \(x=1\), your identity immediately follows. It's left as an exercise to the reader to derive the integral. ;)

Of course, the real challenge is to find another way to prove this very un-obvious identity. – Michael Mendrin · 2 years, 1 month ago

Log in to reply

Can you advise me on becoming more knowledgeable (like you) ? And some sources to study Discrete calculus ?

Thanks for the same \(\ddot\smile\) – Azhaghu Roopesh M · 2 years, 1 month ago

Log in to reply

What I can tell you is that in spite of owning a library of books on math and physics, I've come to rely more on the internet to improve on my skills. So, my advice to you would be, "get very good at finding information on the internet". You know, kind of like how I found that integral. Doing a search on "discrete calculus" immediately returns quite a wealth of material, far more than what I can find in my library of books, and, you know, already I'm getting interested in this subject, in looking over this material---that can be had right now and for free on the internet. – Michael Mendrin · 2 years, 1 month ago

Log in to reply

– Azhaghu Roopesh M · 2 years, 1 month ago

Actually sir, instead of me looking in the wrong place, you can maybe help me search in the right place ?Log in to reply

– Michael Mendrin · 2 years, 1 month ago

Give me a chance to get back to you on this, with some recommendations. It's a lot of material to go over.Log in to reply

– Azhaghu Roopesh M · 2 years, 1 month ago

I see you are back sir :) Anything that you would like to share with me , sir ?Log in to reply

– Azhaghu Roopesh M · 2 years, 1 month ago

Oh yes , sir . Please take your time , I'll wait .Log in to reply

@Ariel Gershon Just out of curiousity, what was your method? – Ishan Singh · 7 months, 2 weeks ago

Log in to reply

– Ariel Gershon · 7 months, 1 week ago

My method was similar to what Calvin posted. I wrote this note in the hope that someone had a combinatorial proof or proof by induction which I couldn't figure out.Log in to reply