Waste less time on Facebook — follow Brilliant.
×

Interesting formula from combinatorics

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

Note by Ariel Gershon
2 years, 1 month ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

There 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

@Calvin Lin Nice solution. Some other ways would be to use Snake Oil method or Beta Function. Ishan Singh · 7 months, 2 weeks ago

Log in to reply

@Calvin Lin I don't understand what is \(\binom{-1/2}{n}\)? Ariel Gershon · 2 years, 1 month ago

Log in to reply

@Ariel Gershon 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

@Michael Mendrin 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\) Azhaghu Roopesh M · 2 years, 1 month ago

Log in to reply

@Azhaghu Roopesh M 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. Michael Mendrin · 2 years, 1 month ago

Log in to reply

@Michael Mendrin Actually sir, instead of me looking in the wrong place, you can maybe help me search in the right place ? Azhaghu Roopesh M · 2 years, 1 month ago

Log in to reply

@Azhaghu Roopesh M Give me a chance to get back to you on this, with some recommendations. It's a lot of material to go over. Michael Mendrin · 2 years, 1 month ago

Log in to reply

@Michael Mendrin I see you are back sir :) Anything that you would like to share with me , sir ? Azhaghu Roopesh M · 2 years, 1 month ago

Log in to reply

@Michael Mendrin Oh yes , sir . Please take your time , I'll wait . Azhaghu Roopesh M · 2 years, 1 month ago

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

@Ishan Singh 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. Ariel Gershon · 7 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...