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 :)

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## 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.

Log in to reply

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

Log in to reply

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 \]

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.

Log in to reply

Sir, you really are worth your title of Mr Mathopedia .

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

Thanks for the same \(\ddot\smile\)

Log in to reply

Eh, Azhaghu, I found the integral, I didn't derive it. It's still a tough problem, and I haven't figured out another way to prove it. But I think I can use that integral to help me find a way.

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.

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

@Ariel Gershon Just out of curiousity, what was your method?

Log in to reply

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