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

#Combinatorics

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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

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

Ariel Gershon - 6 years, 4 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$

Calvin Lin Staff - 6 years, 4 months ago

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

Ishan Singh - 4 years, 10 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.

Michael Mendrin - 6 years, 4 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$

A Former Brilliant Member - 6 years, 4 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.

Michael Mendrin - 6 years, 4 months ago

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

A Former Brilliant Member - 6 years, 4 months ago

@A Former Brilliant Member – 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 - 6 years, 4 months ago

@Michael Mendrin – Oh yes , sir . Please take your time , I'll wait .

A Former Brilliant Member - 6 years, 4 months ago

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

A Former Brilliant Member - 6 years, 3 months ago

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

Ishan Singh - 4 years, 10 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.

Ariel Gershon - 4 years, 9 months ago

Math	Appears 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}$