# 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
4 years, 10 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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.

Staff - 4 years, 10 months ago

I don't understand what is $\binom{-1/2}{n}$?

- 4 years, 10 months ago

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$

Staff - 4 years, 10 months ago

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

- 3 years, 3 months ago

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.

- 4 years, 10 months ago

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$

- 4 years, 10 months ago

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.

- 4 years, 10 months ago

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

- 4 years, 10 months ago

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

- 4 years, 10 months ago

Oh yes , sir . Please take your time , I'll wait .

- 4 years, 10 months ago

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

- 4 years, 9 months ago

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

- 3 years, 3 months 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.

- 3 years, 3 months ago