Dtjytyk

Why Shazam when there is already Superman?

Open a doc from terminal, but not by its name

Is it safe to use olive oil to clean the ear wax?

Not using 's' for he/she/it

Removing files under particular conditions (number of files, file age)

Is it possible to have a strip of cold climate in the middle of a planet?

Why did the EU agree to delay the Brexit deadline?

Count the occurrence of each unique word in the file

What is this called? Old film camera viewer?

What should you do when eye contact makes your subordinate uncomfortable?

Creepy dinosaur pc game identification

Offered money to buy a house, seller is asking for more to cover gap between their listing and mortgage owed

It grows, but water kills it

Is there a name for this algorithm to calculate the concentration of a mixture of two solutions containing the same solute?

The screen of my macbook suddenly broken down how can I do to recover

The IT department bottlenecks progress. How should I handle this?

How could a planet have erratic days?

Which one is correct as adjective “protruding” or “protruded”?

why `nmap 192.168.1.97` returns less services than `nmap 127.0.0.1`?

Loading commands from file

250 Floor Tower

Drawing ramified coverings with tikz

Why do we read the Megillah by night and by day?

Is it better practice to read straight from sheet music rather than memorize it?

Identity involving product of two binomial coefficients

Strehl identity for the sum of cubes of binomial coefficientsProof of an identity involving binomial coefficientsBinomial coefficients identityChecking an identity involving binomial coefficientsAlternating sum of binomial coefficients identityBinomial coefficients identityAn identity involving binomial coefficients and rational functionsIdentity involving binomial coefficientsIdentity involving sums of binomial coefficientsProving a binomial identity involving the sum of a product of four binomial coefficients

5

4

$begingroup$

Emprically it looks like the following identity holds, but I haven't been able to prove it. Can anyone find a proof?
$$
binom{m+k}{k}binom{n+k}{k}=sum_{igeq0}binom{m}{i}binom{n}{i}binom{m+n+k-i}{k-i}
$$
For some context, a corollary would be that the generating function for the LHS keeping $m$ and $n$ fixed is
$$
sum_{kgeq0}binom{m+k}{k}binom{n+k}{k}x^k=frac{sum_{igeq0}binom{m}{i}binom{n}{i}x^i}{(1-x)^{m+n+1}}
$$

combinatorics binomial-coefficients generating-functions

share|cite|improve this question

asked Mar 14 at 0:00

Ben RobertsBen Roberts

284

$endgroup$

add a comment | 

5

4

$begingroup$

Emprically it looks like the following identity holds, but I haven't been able to prove it. Can anyone find a proof?
$$
binom{m+k}{k}binom{n+k}{k}=sum_{igeq0}binom{m}{i}binom{n}{i}binom{m+n+k-i}{k-i}
$$
For some context, a corollary would be that the generating function for the LHS keeping $m$ and $n$ fixed is
$$
sum_{kgeq0}binom{m+k}{k}binom{n+k}{k}x^k=frac{sum_{igeq0}binom{m}{i}binom{n}{i}x^i}{(1-x)^{m+n+1}}
$$

combinatorics binomial-coefficients generating-functions

share|cite|improve this question

asked Mar 14 at 0:00

Ben RobertsBen Roberts

284

$endgroup$

add a comment | 

$begingroup$

Emprically it looks like the following identity holds, but I haven't been able to prove it. Can anyone find a proof?
$$
binom{m+k}{k}binom{n+k}{k}=sum_{igeq0}binom{m}{i}binom{n}{i}binom{m+n+k-i}{k-i}
$$
For some context, a corollary would be that the generating function for the LHS keeping $m$ and $n$ fixed is
$$
sum_{kgeq0}binom{m+k}{k}binom{n+k}{k}x^k=frac{sum_{igeq0}binom{m}{i}binom{n}{i}x^i}{(1-x)^{m+n+1}}
$$

combinatorics binomial-coefficients generating-functions

share|cite|improve this question

asked Mar 14 at 0:00

Ben RobertsBen Roberts

284

$endgroup$

share|cite|improve this question

asked Mar 14 at 0:00

Ben RobertsBen Roberts

284

share|cite|improve this question

asked Mar 14 at 0:00

Ben RobertsBen Roberts

284

asked Mar 14 at 0:00

Ben RobertsBen Roberts

284

asked Mar 14 at 0:00

Ben RobertsBen Roberts

284

2 Answers
2

active

oldest

votes

3

$begingroup$

We seek to prove that

$${m+kchoose k} {n+kchoose k}
= sum_{qge 0} {mchoose q} {nchoose q} {m+n+k-qchoose k-q}.$$

We start on the RHS with

$$sum_{qge 0} {mchoose q}
{nchoose n-q} {m+n+k-qchoose k-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
sum_{qge 0} {mchoose q} z^q w^q (1+w)^{-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
left(1+frac{zw}{1+w}right)^m
\ = [z^n] (1+z)^n [w^k] (1+w)^{n+k}
(1+w+zw)^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
(1+w(1+z))^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
sum_{q=0}^m {mchoose q} w^q (1+z)^q
\ = [w^k] (1+w)^{n+k}
sum_{q=0}^m {mchoose q} {n+qchoose q} w^q
\ = sum_{q=0}^k {mchoose q} {n+qchoose q}
{n+kchoose k-q}.$$

Observe that

$${n+qchoose q} {n+kchoose k-q}
= frac{(n+k)!}{q!times n!times (k-q)!}
= {n+kchoose k} {kchoose q}.$$

We get

$${n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose q}
= {n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose k-q}
\ = {n+kchoose k} [z^k] (1+z)^k
sum_{q=0}^k {mchoose q} z^q.$$

We may extend $q$ to infinity owing to the coeffcient extractor in
$z$:

$${n+kchoose k} [z^k] (1+z)^k
sum_{qge 0} {mchoose q} z^q
\ = {n+kchoose k} [z^k] (1+z)^{m+k}
= {n+kchoose k} {m+kchoose k}.$$

This is the claim.

share|cite|improve this answer

answered Mar 14 at 17:30

Marko RiedelMarko Riedel

40.8k340110

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Nice proof Marko. I'd not encountered coefficient extraction techniques before - very neat. Btw, once we reach $binom{n+k}{k}sum_{q=0}^kbinom{m}{q}binom{k}{k-q}$ the final step follows immediately from Vandermonde's identity, right?
  $endgroup$
  – Ben Roberts
  Mar 15 at 5:20
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes it would seem so.
  $endgroup$
  – Marko Riedel
  Mar 15 at 14:13
  

  
  
  
  

add a comment | 

3

$begingroup$

That is known as Suranyi's formula, and you can find
a demonstration in this paper.

Also interesting is the context in which it is analyzed
in this other paper.

share|cite|improve this answer

answered Mar 14 at 3:04

G CabG Cab

20.4k31341

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3147371%2fidentity-involving-product-of-two-binomial-coefficients%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

We seek to prove that

$${m+kchoose k} {n+kchoose k}
= sum_{qge 0} {mchoose q} {nchoose q} {m+n+k-qchoose k-q}.$$

We start on the RHS with

$$sum_{qge 0} {mchoose q}
{nchoose n-q} {m+n+k-qchoose k-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
sum_{qge 0} {mchoose q} z^q w^q (1+w)^{-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
left(1+frac{zw}{1+w}right)^m
\ = [z^n] (1+z)^n [w^k] (1+w)^{n+k}
(1+w+zw)^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
(1+w(1+z))^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
sum_{q=0}^m {mchoose q} w^q (1+z)^q
\ = [w^k] (1+w)^{n+k}
sum_{q=0}^m {mchoose q} {n+qchoose q} w^q
\ = sum_{q=0}^k {mchoose q} {n+qchoose q}
{n+kchoose k-q}.$$

Observe that

$${n+qchoose q} {n+kchoose k-q}
= frac{(n+k)!}{q!times n!times (k-q)!}
= {n+kchoose k} {kchoose q}.$$

We get

$${n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose q}
= {n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose k-q}
\ = {n+kchoose k} [z^k] (1+z)^k
sum_{q=0}^k {mchoose q} z^q.$$

We may extend $q$ to infinity owing to the coeffcient extractor in
$z$:

$${n+kchoose k} [z^k] (1+z)^k
sum_{qge 0} {mchoose q} z^q
\ = {n+kchoose k} [z^k] (1+z)^{m+k}
= {n+kchoose k} {m+kchoose k}.$$

This is the claim.

share|cite|improve this answer

answered Mar 14 at 17:30

Marko RiedelMarko Riedel

40.8k340110

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Nice proof Marko. I'd not encountered coefficient extraction techniques before - very neat. Btw, once we reach $binom{n+k}{k}sum_{q=0}^kbinom{m}{q}binom{k}{k-q}$ the final step follows immediately from Vandermonde's identity, right?
  $endgroup$
  – Ben Roberts
  Mar 15 at 5:20
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes it would seem so.
  $endgroup$
  – Marko Riedel
  Mar 15 at 14:13
  

  
  
  
  

add a comment | 

3

$begingroup$

We seek to prove that

$${m+kchoose k} {n+kchoose k}
= sum_{qge 0} {mchoose q} {nchoose q} {m+n+k-qchoose k-q}.$$

We start on the RHS with

$$sum_{qge 0} {mchoose q}
{nchoose n-q} {m+n+k-qchoose k-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
sum_{qge 0} {mchoose q} z^q w^q (1+w)^{-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
left(1+frac{zw}{1+w}right)^m
\ = [z^n] (1+z)^n [w^k] (1+w)^{n+k}
(1+w+zw)^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
(1+w(1+z))^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
sum_{q=0}^m {mchoose q} w^q (1+z)^q
\ = [w^k] (1+w)^{n+k}
sum_{q=0}^m {mchoose q} {n+qchoose q} w^q
\ = sum_{q=0}^k {mchoose q} {n+qchoose q}
{n+kchoose k-q}.$$

Observe that

$${n+qchoose q} {n+kchoose k-q}
= frac{(n+k)!}{q!times n!times (k-q)!}
= {n+kchoose k} {kchoose q}.$$

We get

$${n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose q}
= {n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose k-q}
\ = {n+kchoose k} [z^k] (1+z)^k
sum_{q=0}^k {mchoose q} z^q.$$

We may extend $q$ to infinity owing to the coeffcient extractor in
$z$:

$${n+kchoose k} [z^k] (1+z)^k
sum_{qge 0} {mchoose q} z^q
\ = {n+kchoose k} [z^k] (1+z)^{m+k}
= {n+kchoose k} {m+kchoose k}.$$

This is the claim.

share|cite|improve this answer

answered Mar 14 at 17:30

Marko RiedelMarko Riedel

40.8k340110

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Nice proof Marko. I'd not encountered coefficient extraction techniques before - very neat. Btw, once we reach $binom{n+k}{k}sum_{q=0}^kbinom{m}{q}binom{k}{k-q}$ the final step follows immediately from Vandermonde's identity, right?
  $endgroup$
  – Ben Roberts
  Mar 15 at 5:20
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes it would seem so.
  $endgroup$
  – Marko Riedel
  Mar 15 at 14:13
  

  
  
  
  

add a comment | 

$begingroup$

We seek to prove that

$${m+kchoose k} {n+kchoose k}
= sum_{qge 0} {mchoose q} {nchoose q} {m+n+k-qchoose k-q}.$$

We start on the RHS with

$$sum_{qge 0} {mchoose q}
{nchoose n-q} {m+n+k-qchoose k-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
sum_{qge 0} {mchoose q} z^q w^q (1+w)^{-q}
\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k}
left(1+frac{zw}{1+w}right)^m
\ = [z^n] (1+z)^n [w^k] (1+w)^{n+k}
(1+w+zw)^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
(1+w(1+z))^m
\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n
sum_{q=0}^m {mchoose q} w^q (1+z)^q
\ = [w^k] (1+w)^{n+k}
sum_{q=0}^m {mchoose q} {n+qchoose q} w^q
\ = sum_{q=0}^k {mchoose q} {n+qchoose q}
{n+kchoose k-q}.$$

Observe that

$${n+qchoose q} {n+kchoose k-q}
= frac{(n+k)!}{q!times n!times (k-q)!}
= {n+kchoose k} {kchoose q}.$$

We get

$${n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose q}
= {n+kchoose k} sum_{q=0}^k {mchoose q}
{kchoose k-q}
\ = {n+kchoose k} [z^k] (1+z)^k
sum_{q=0}^k {mchoose q} z^q.$$

We may extend $q$ to infinity owing to the coeffcient extractor in
$z$:

$${n+kchoose k} [z^k] (1+z)^k
sum_{qge 0} {mchoose q} z^q
\ = {n+kchoose k} [z^k] (1+z)^{m+k}
= {n+kchoose k} {m+kchoose k}.$$

This is the claim.

share|cite|improve this answer

answered Mar 14 at 17:30

Marko RiedelMarko Riedel

40.8k340110

$endgroup$

share|cite|improve this answer

answered Mar 14 at 17:30

Marko RiedelMarko Riedel

40.8k340110

answered Mar 14 at 17:30

Marko RiedelMarko Riedel

40.8k340110

answered Mar 14 at 17:30

Marko RiedelMarko Riedel

40.8k340110

3

$begingroup$

That is known as Suranyi's formula, and you can find
a demonstration in this paper.

Also interesting is the context in which it is analyzed
in this other paper.

share|cite|improve this answer

answered Mar 14 at 3:04

G CabG Cab

20.4k31341

$endgroup$

add a comment | 

3

$begingroup$

That is known as Suranyi's formula, and you can find
a demonstration in this paper.

Also interesting is the context in which it is analyzed
in this other paper.

share|cite|improve this answer

answered Mar 14 at 3:04

G CabG Cab

20.4k31341

$endgroup$

add a comment | 

$begingroup$

That is known as Suranyi's formula, and you can find
a demonstration in this paper.

Also interesting is the context in which it is analyzed
in this other paper.

share|cite|improve this answer

answered Mar 14 at 3:04

G CabG Cab

20.4k31341

$endgroup$

share|cite|improve this answer

answered Mar 14 at 3:04

G CabG Cab

20.4k31341

answered Mar 14 at 3:04

G CabG Cab

20.4k31341

answered Mar 14 at 3:04

G CabG Cab

20.4k31341