A nice Combinatorial IdentitySum involving binomial coefficientsSome combinatorial identity.A Finite...

Book with the Latin quote 'nihil superbus' meaning 'nothing above us'

Why doesn't 'd /= d' throw a division by zero exception?

Handling Disruptive Student on the Autism Spectrum

How to check whether a sublist exist in a huge database lists in a fast way?

Server Integrity Check CheckCommands question

Why are non-collision-resistant hash functions considered insecure for signing self-generated information

Boot Windows from SAN

What do these commands specifically do?

Higman's lemma and a manuscript of Erdős and Rado

Why do banks “park” their money at the European Central Bank?

How can I reorder triggered abilities in Arena?

Could this kind of inaccurate sacrifice be countered?

How is linear momentum conserved in case of a freely falling body?

Why is there a difference between predicting on Validation set and Test set?

Does Yeshayahu 43:10b / 43:13a imply HaShem was created?

To get so rich that you are not in need of anymore money

What does "rel" in `mathrel` and `stackrel` stands for?

Evaluated vs. unevaluated Association

Can RMSE and MAE have the same value?

Are the players on the same team as the DM?

Why is the UK so keen to remove the "backstop" when their leadership seems to think that no border will be needed in Northern Ireland?

What should come first—characters or plot?

Ordering a list of integers

How can I download a file through 2 SSH connections?



A nice Combinatorial Identity


Sum involving binomial coefficientsSome combinatorial identity.A Finite Combinatorial SumEquality of the sums $sumlimits_{v=0}^k frac{k^v}{v!}$ and $sumlimits_{v=0}^k frac{v^v (k-v)^{k-v}}{v!(k-v)!}$Evaluate $sum_{j=0}^n(-1)^{n+j}{nchoose j}{{n+j}choose j}frac{1}{(j+1)^2}$Summation of Legendre polynomials with two power functionsintegral of sum of function involving legendre polynomialsInfinite Series $sum_{n=1}^{infty}frac{4^nH_n}{n^2{2nchoose n}}$Orthogonal polynomials with respect to the weighting function $omega(x)=frac{x}{e^x-1}$






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}







17












$begingroup$


I am trying to show that $forall Ninmathbb{N}$,



$$sumlimits_{n=0}^{N}sumlimits_{k=0}^{N}frac{left(-1right)^{n+k}}{n+k+1}{Nchoose n}{Nchoose k}{N+nchoose n}{N+kchoose k}=frac{1}{2N+1}$$



It's backed by numerical verifications, but I can't come up with a proof.



So far, I tried using the generating function of $left(frac{1}{2N+1}right)_{Ninmathbb{N}}$, which is $frac{arctanleft(sqrt{x}right)}{sqrt{x}}$, by showing that the LHS has the same generating function, but this calculation doesn't seem to lead me anywhere...



Any suggestion ?



Edit: the comment of bof (below this question) actually leads to a very simple proof.



Indeed, from bof's comment we have that the LHS is equal to $$int_{0}^{1}left(sumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^kright)^2dx$$



And we recognize here the shifted Legendre Polynomials $widetilde{P_N}(x)=displaystylesumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^k$.



And we know that the shifted Legendre Polynomials form a family of orthogonal polynomials with respect to the inner product $<f|g>=displaystyleint_{0}^{1}f(x)g(x)dx$, and that their squared norm with respect to this product is $<widetilde{P_n}|widetilde{P_n}>=frac{1}{2n+1}$;



So this basically provides the desired result immediatly.










share|cite|improve this question











$endgroup$










  • 3




    $begingroup$
    $$sum_{n=0}^Nsum_{k=0}^Nfrac{(-1)^{n+k}}{n+k+1}binom Nnbinom Nkbinom{N+n}nbinom{N+k}k$$$$=int_0^1sum_{n=0}^Nsum_{k=0}^N(-1)^{n+k}binom Nnbinom Nkbinom{N+n}nbinom{N+k}kx^{n+k}dx$$$$=int_0^1left(sum_{n=0}^N(-1)^nbinom Nnbinom{N+n}nx^nright)left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)dx$$$$=int_9^1left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)^2dx$$ but I don't know why that integral evaluates to $frac1{2N+1}$.
    $endgroup$
    – bof
    15 hours ago










  • $begingroup$
    @bof : thank you very much, this actually sovled the problem (see my edit).
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    @HarmonicSun: Good observation. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago


















17












$begingroup$


I am trying to show that $forall Ninmathbb{N}$,



$$sumlimits_{n=0}^{N}sumlimits_{k=0}^{N}frac{left(-1right)^{n+k}}{n+k+1}{Nchoose n}{Nchoose k}{N+nchoose n}{N+kchoose k}=frac{1}{2N+1}$$



It's backed by numerical verifications, but I can't come up with a proof.



So far, I tried using the generating function of $left(frac{1}{2N+1}right)_{Ninmathbb{N}}$, which is $frac{arctanleft(sqrt{x}right)}{sqrt{x}}$, by showing that the LHS has the same generating function, but this calculation doesn't seem to lead me anywhere...



Any suggestion ?



Edit: the comment of bof (below this question) actually leads to a very simple proof.



Indeed, from bof's comment we have that the LHS is equal to $$int_{0}^{1}left(sumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^kright)^2dx$$



And we recognize here the shifted Legendre Polynomials $widetilde{P_N}(x)=displaystylesumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^k$.



And we know that the shifted Legendre Polynomials form a family of orthogonal polynomials with respect to the inner product $<f|g>=displaystyleint_{0}^{1}f(x)g(x)dx$, and that their squared norm with respect to this product is $<widetilde{P_n}|widetilde{P_n}>=frac{1}{2n+1}$;



So this basically provides the desired result immediatly.










share|cite|improve this question











$endgroup$










  • 3




    $begingroup$
    $$sum_{n=0}^Nsum_{k=0}^Nfrac{(-1)^{n+k}}{n+k+1}binom Nnbinom Nkbinom{N+n}nbinom{N+k}k$$$$=int_0^1sum_{n=0}^Nsum_{k=0}^N(-1)^{n+k}binom Nnbinom Nkbinom{N+n}nbinom{N+k}kx^{n+k}dx$$$$=int_0^1left(sum_{n=0}^N(-1)^nbinom Nnbinom{N+n}nx^nright)left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)dx$$$$=int_9^1left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)^2dx$$ but I don't know why that integral evaluates to $frac1{2N+1}$.
    $endgroup$
    – bof
    15 hours ago










  • $begingroup$
    @bof : thank you very much, this actually sovled the problem (see my edit).
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    @HarmonicSun: Good observation. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago














17












17








17


2



$begingroup$


I am trying to show that $forall Ninmathbb{N}$,



$$sumlimits_{n=0}^{N}sumlimits_{k=0}^{N}frac{left(-1right)^{n+k}}{n+k+1}{Nchoose n}{Nchoose k}{N+nchoose n}{N+kchoose k}=frac{1}{2N+1}$$



It's backed by numerical verifications, but I can't come up with a proof.



So far, I tried using the generating function of $left(frac{1}{2N+1}right)_{Ninmathbb{N}}$, which is $frac{arctanleft(sqrt{x}right)}{sqrt{x}}$, by showing that the LHS has the same generating function, but this calculation doesn't seem to lead me anywhere...



Any suggestion ?



Edit: the comment of bof (below this question) actually leads to a very simple proof.



Indeed, from bof's comment we have that the LHS is equal to $$int_{0}^{1}left(sumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^kright)^2dx$$



And we recognize here the shifted Legendre Polynomials $widetilde{P_N}(x)=displaystylesumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^k$.



And we know that the shifted Legendre Polynomials form a family of orthogonal polynomials with respect to the inner product $<f|g>=displaystyleint_{0}^{1}f(x)g(x)dx$, and that their squared norm with respect to this product is $<widetilde{P_n}|widetilde{P_n}>=frac{1}{2n+1}$;



So this basically provides the desired result immediatly.










share|cite|improve this question











$endgroup$




I am trying to show that $forall Ninmathbb{N}$,



$$sumlimits_{n=0}^{N}sumlimits_{k=0}^{N}frac{left(-1right)^{n+k}}{n+k+1}{Nchoose n}{Nchoose k}{N+nchoose n}{N+kchoose k}=frac{1}{2N+1}$$



It's backed by numerical verifications, but I can't come up with a proof.



So far, I tried using the generating function of $left(frac{1}{2N+1}right)_{Ninmathbb{N}}$, which is $frac{arctanleft(sqrt{x}right)}{sqrt{x}}$, by showing that the LHS has the same generating function, but this calculation doesn't seem to lead me anywhere...



Any suggestion ?



Edit: the comment of bof (below this question) actually leads to a very simple proof.



Indeed, from bof's comment we have that the LHS is equal to $$int_{0}^{1}left(sumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^kright)^2dx$$



And we recognize here the shifted Legendre Polynomials $widetilde{P_N}(x)=displaystylesumlimits_{k=0}^{N}(-1)^k{Nchoose k}{N+kchoose k}x^k$.



And we know that the shifted Legendre Polynomials form a family of orthogonal polynomials with respect to the inner product $<f|g>=displaystyleint_{0}^{1}f(x)g(x)dx$, and that their squared norm with respect to this product is $<widetilde{P_n}|widetilde{P_n}>=frac{1}{2n+1}$;



So this basically provides the desired result immediatly.







real-analysis combinatorics summation






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 10 hours ago







Harmonic Sun

















asked 16 hours ago









Harmonic SunHarmonic Sun

9431 silver badge11 bronze badges




9431 silver badge11 bronze badges











  • 3




    $begingroup$
    $$sum_{n=0}^Nsum_{k=0}^Nfrac{(-1)^{n+k}}{n+k+1}binom Nnbinom Nkbinom{N+n}nbinom{N+k}k$$$$=int_0^1sum_{n=0}^Nsum_{k=0}^N(-1)^{n+k}binom Nnbinom Nkbinom{N+n}nbinom{N+k}kx^{n+k}dx$$$$=int_0^1left(sum_{n=0}^N(-1)^nbinom Nnbinom{N+n}nx^nright)left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)dx$$$$=int_9^1left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)^2dx$$ but I don't know why that integral evaluates to $frac1{2N+1}$.
    $endgroup$
    – bof
    15 hours ago










  • $begingroup$
    @bof : thank you very much, this actually sovled the problem (see my edit).
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    @HarmonicSun: Good observation. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago














  • 3




    $begingroup$
    $$sum_{n=0}^Nsum_{k=0}^Nfrac{(-1)^{n+k}}{n+k+1}binom Nnbinom Nkbinom{N+n}nbinom{N+k}k$$$$=int_0^1sum_{n=0}^Nsum_{k=0}^N(-1)^{n+k}binom Nnbinom Nkbinom{N+n}nbinom{N+k}kx^{n+k}dx$$$$=int_0^1left(sum_{n=0}^N(-1)^nbinom Nnbinom{N+n}nx^nright)left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)dx$$$$=int_9^1left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)^2dx$$ but I don't know why that integral evaluates to $frac1{2N+1}$.
    $endgroup$
    – bof
    15 hours ago










  • $begingroup$
    @bof : thank you very much, this actually sovled the problem (see my edit).
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    @HarmonicSun: Good observation. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago








3




3




$begingroup$
$$sum_{n=0}^Nsum_{k=0}^Nfrac{(-1)^{n+k}}{n+k+1}binom Nnbinom Nkbinom{N+n}nbinom{N+k}k$$$$=int_0^1sum_{n=0}^Nsum_{k=0}^N(-1)^{n+k}binom Nnbinom Nkbinom{N+n}nbinom{N+k}kx^{n+k}dx$$$$=int_0^1left(sum_{n=0}^N(-1)^nbinom Nnbinom{N+n}nx^nright)left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)dx$$$$=int_9^1left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)^2dx$$ but I don't know why that integral evaluates to $frac1{2N+1}$.
$endgroup$
– bof
15 hours ago




$begingroup$
$$sum_{n=0}^Nsum_{k=0}^Nfrac{(-1)^{n+k}}{n+k+1}binom Nnbinom Nkbinom{N+n}nbinom{N+k}k$$$$=int_0^1sum_{n=0}^Nsum_{k=0}^N(-1)^{n+k}binom Nnbinom Nkbinom{N+n}nbinom{N+k}kx^{n+k}dx$$$$=int_0^1left(sum_{n=0}^N(-1)^nbinom Nnbinom{N+n}nx^nright)left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)dx$$$$=int_9^1left(sum_{k=0}^N(-1)^kbinom Nkbinom{N+k}kx^kright)^2dx$$ but I don't know why that integral evaluates to $frac1{2N+1}$.
$endgroup$
– bof
15 hours ago












$begingroup$
@bof : thank you very much, this actually sovled the problem (see my edit).
$endgroup$
– Harmonic Sun
10 hours ago




$begingroup$
@bof : thank you very much, this actually sovled the problem (see my edit).
$endgroup$
– Harmonic Sun
10 hours ago












$begingroup$
@HarmonicSun: Good observation. (+1)
$endgroup$
– Markus Scheuer
10 hours ago




$begingroup$
@HarmonicSun: Good observation. (+1)
$endgroup$
– Markus Scheuer
10 hours ago










1 Answer
1






active

oldest

votes


















5













$begingroup$

We seek to verify that



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1}
{Nchoose n} {Nchoose k}
{N+nchoose n} {N+kchoose k}
= frac{1}{2N+1}.$$



Now we have



$${Nchoose k} {N+nchoose n}
= frac{(N+n)!}{(N-k)! times k! times n!}
= {N+nchoose n+k} {n+kchoose k}.$$



We get for the LHS



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1} {N+nchoose n+k}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} sum_{k=0}^N
(-1)^{n+k} {N+n+1choose n+k+1}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} {Nchoose n}
sum_{k=0}^N
(-1)^{n+k} {N+n+1choose N-k}
{N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
sum_{k=0}^N
(-1)^{n+k} z^k
{N+kchoose N} {n+kchoose n}.$$



Now the coefficient extractor controls the range and we continue with



$$sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{(1-w)^{k+1}}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N} frac{1}{(1-w)^{k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
frac{1}{(1+z/(1-w))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w+z)^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w/(1+z))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} frac{1}{(1+z)^{n-k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} [z^N] (1+z)^k.$$



Now for the coefficient extractor to be non-zero we must have $kge N$
which happens just once, namely when $n=N$ and $k=N.$ We get



$$frac{(-1)^N}{2N+1}
{Nchoose N}
(-1)^N {Nchoose N}
{N-N+Nchoose N}.$$



This expression does indeed simplify to



$$bbox[5px,border:2px solid #00A000]{
frac{1}{2N+1}}$$



as claimed.






share|cite|improve this answer









$endgroup$















  • $begingroup$
    Nice answer. Verified. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago






  • 1




    $begingroup$
    Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :)
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit.
    $endgroup$
    – Marko Riedel
    9 hours ago














Your Answer








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


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3333597%2fa-nice-combinatorial-identity%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









5













$begingroup$

We seek to verify that



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1}
{Nchoose n} {Nchoose k}
{N+nchoose n} {N+kchoose k}
= frac{1}{2N+1}.$$



Now we have



$${Nchoose k} {N+nchoose n}
= frac{(N+n)!}{(N-k)! times k! times n!}
= {N+nchoose n+k} {n+kchoose k}.$$



We get for the LHS



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1} {N+nchoose n+k}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} sum_{k=0}^N
(-1)^{n+k} {N+n+1choose n+k+1}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} {Nchoose n}
sum_{k=0}^N
(-1)^{n+k} {N+n+1choose N-k}
{N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
sum_{k=0}^N
(-1)^{n+k} z^k
{N+kchoose N} {n+kchoose n}.$$



Now the coefficient extractor controls the range and we continue with



$$sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{(1-w)^{k+1}}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N} frac{1}{(1-w)^{k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
frac{1}{(1+z/(1-w))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w+z)^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w/(1+z))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} frac{1}{(1+z)^{n-k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} [z^N] (1+z)^k.$$



Now for the coefficient extractor to be non-zero we must have $kge N$
which happens just once, namely when $n=N$ and $k=N.$ We get



$$frac{(-1)^N}{2N+1}
{Nchoose N}
(-1)^N {Nchoose N}
{N-N+Nchoose N}.$$



This expression does indeed simplify to



$$bbox[5px,border:2px solid #00A000]{
frac{1}{2N+1}}$$



as claimed.






share|cite|improve this answer









$endgroup$















  • $begingroup$
    Nice answer. Verified. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago






  • 1




    $begingroup$
    Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :)
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit.
    $endgroup$
    – Marko Riedel
    9 hours ago
















5













$begingroup$

We seek to verify that



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1}
{Nchoose n} {Nchoose k}
{N+nchoose n} {N+kchoose k}
= frac{1}{2N+1}.$$



Now we have



$${Nchoose k} {N+nchoose n}
= frac{(N+n)!}{(N-k)! times k! times n!}
= {N+nchoose n+k} {n+kchoose k}.$$



We get for the LHS



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1} {N+nchoose n+k}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} sum_{k=0}^N
(-1)^{n+k} {N+n+1choose n+k+1}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} {Nchoose n}
sum_{k=0}^N
(-1)^{n+k} {N+n+1choose N-k}
{N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
sum_{k=0}^N
(-1)^{n+k} z^k
{N+kchoose N} {n+kchoose n}.$$



Now the coefficient extractor controls the range and we continue with



$$sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{(1-w)^{k+1}}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N} frac{1}{(1-w)^{k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
frac{1}{(1+z/(1-w))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w+z)^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w/(1+z))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} frac{1}{(1+z)^{n-k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} [z^N] (1+z)^k.$$



Now for the coefficient extractor to be non-zero we must have $kge N$
which happens just once, namely when $n=N$ and $k=N.$ We get



$$frac{(-1)^N}{2N+1}
{Nchoose N}
(-1)^N {Nchoose N}
{N-N+Nchoose N}.$$



This expression does indeed simplify to



$$bbox[5px,border:2px solid #00A000]{
frac{1}{2N+1}}$$



as claimed.






share|cite|improve this answer









$endgroup$















  • $begingroup$
    Nice answer. Verified. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago






  • 1




    $begingroup$
    Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :)
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit.
    $endgroup$
    – Marko Riedel
    9 hours ago














5














5










5







$begingroup$

We seek to verify that



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1}
{Nchoose n} {Nchoose k}
{N+nchoose n} {N+kchoose k}
= frac{1}{2N+1}.$$



Now we have



$${Nchoose k} {N+nchoose n}
= frac{(N+n)!}{(N-k)! times k! times n!}
= {N+nchoose n+k} {n+kchoose k}.$$



We get for the LHS



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1} {N+nchoose n+k}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} sum_{k=0}^N
(-1)^{n+k} {N+n+1choose n+k+1}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} {Nchoose n}
sum_{k=0}^N
(-1)^{n+k} {N+n+1choose N-k}
{N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
sum_{k=0}^N
(-1)^{n+k} z^k
{N+kchoose N} {n+kchoose n}.$$



Now the coefficient extractor controls the range and we continue with



$$sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{(1-w)^{k+1}}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N} frac{1}{(1-w)^{k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
frac{1}{(1+z/(1-w))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w+z)^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w/(1+z))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} frac{1}{(1+z)^{n-k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} [z^N] (1+z)^k.$$



Now for the coefficient extractor to be non-zero we must have $kge N$
which happens just once, namely when $n=N$ and $k=N.$ We get



$$frac{(-1)^N}{2N+1}
{Nchoose N}
(-1)^N {Nchoose N}
{N-N+Nchoose N}.$$



This expression does indeed simplify to



$$bbox[5px,border:2px solid #00A000]{
frac{1}{2N+1}}$$



as claimed.






share|cite|improve this answer









$endgroup$



We seek to verify that



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1}
{Nchoose n} {Nchoose k}
{N+nchoose n} {N+kchoose k}
= frac{1}{2N+1}.$$



Now we have



$${Nchoose k} {N+nchoose n}
= frac{(N+n)!}{(N-k)! times k! times n!}
= {N+nchoose n+k} {n+kchoose k}.$$



We get for the LHS



$$sum_{n=0}^N sum_{k=0}^N
frac{(-1)^{n+k}}{n+k+1} {N+nchoose n+k}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} sum_{k=0}^N
(-1)^{n+k} {N+n+1choose n+k+1}
{Nchoose n} {N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1} {Nchoose n}
sum_{k=0}^N
(-1)^{n+k} {N+n+1choose N-k}
{N+kchoose k} {n+kchoose k}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
sum_{k=0}^N
(-1)^{n+k} z^k
{N+kchoose N} {n+kchoose n}.$$



Now the coefficient extractor controls the range and we continue with



$$sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{(1-w)^{k+1}}
\ = sum_{n=0}^N frac{1}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
\ times sum_{kge 0}
(-1)^{n+k} z^k
{N+kchoose N} frac{1}{(1-w)^{k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}} frac{1}{1-w}
frac{1}{(1+z/(1-w))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{N+n+1}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w+z)^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times mathrm{Res}_{w=0} frac{1}{w^{n+1}}
frac{(1-w)^N}{(1-w/(1+z))^{N+1}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
[z^N] (1+z)^{n}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} frac{1}{(1+z)^{n-k}}
\ = sum_{n=0}^N frac{(-1)^n}{N+n+1}
{Nchoose n}
\ times sum_{k=0}^n (-1)^k {Nchoose k}
{n-k+Nchoose N} [z^N] (1+z)^k.$$



Now for the coefficient extractor to be non-zero we must have $kge N$
which happens just once, namely when $n=N$ and $k=N.$ We get



$$frac{(-1)^N}{2N+1}
{Nchoose N}
(-1)^N {Nchoose N}
{N-N+Nchoose N}.$$



This expression does indeed simplify to



$$bbox[5px,border:2px solid #00A000]{
frac{1}{2N+1}}$$



as claimed.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 10 hours ago









Marko RiedelMarko Riedel

43k3 gold badges42 silver badges115 bronze badges




43k3 gold badges42 silver badges115 bronze badges















  • $begingroup$
    Nice answer. Verified. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago






  • 1




    $begingroup$
    Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :)
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit.
    $endgroup$
    – Marko Riedel
    9 hours ago


















  • $begingroup$
    Nice answer. Verified. (+1)
    $endgroup$
    – Markus Scheuer
    10 hours ago






  • 1




    $begingroup$
    Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :)
    $endgroup$
    – Harmonic Sun
    10 hours ago










  • $begingroup$
    All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit.
    $endgroup$
    – Marko Riedel
    9 hours ago
















$begingroup$
Nice answer. Verified. (+1)
$endgroup$
– Markus Scheuer
10 hours ago




$begingroup$
Nice answer. Verified. (+1)
$endgroup$
– Markus Scheuer
10 hours ago




1




1




$begingroup$
Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :)
$endgroup$
– Harmonic Sun
10 hours ago




$begingroup$
Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :)
$endgroup$
– Harmonic Sun
10 hours ago












$begingroup$
All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit.
$endgroup$
– Marko Riedel
9 hours ago




$begingroup$
All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit.
$endgroup$
– Marko Riedel
9 hours ago


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3333597%2fa-nice-combinatorial-identity%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Taj Mahal Inhaltsverzeichnis Aufbau | Geschichte | 350-Jahr-Feier | Heutige Bedeutung | Siehe auch |...

Baia Sprie Cuprins Etimologie | Istorie | Demografie | Politică și administrație | Arii naturale...

Nicolae Petrescu-Găină Cuprins Biografie | Opera | In memoriam | Varia | Controverse, incertitudini...