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;
}
$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.
real-analysis combinatorics summation
$endgroup$
add a comment |
$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.
real-analysis combinatorics summation
$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
add a comment |
$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.
real-analysis combinatorics summation
$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
real-analysis combinatorics summation
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
add a comment |
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
add a comment |
1 Answer
1
active
oldest
votes
$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.
$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
add a comment |
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
});
}
});
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
Required, but never shown
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
$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.
$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
add a comment |
$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.
$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
add a comment |
$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.
$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.
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
add a comment |
$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
add a comment |
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.
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
Required, but never shown
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
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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