Mixing
Simplification of a sum involving binomial coefficient
$begingroup$
Let the following complicated sum:
$$sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}.$$
Is there a way to simplify it? Or should we upper and lower bound it?
Thank you
combinatorics summation combinations
asked Jan 31 at 16:21
Adam54Adam54
916
$endgroup$
add a comment |
$begingroup$
Let the following complicated sum:
$$sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}.$$
Is there a way to simplify it? Or should we upper and lower bound it?
Thank you
combinatorics summation combinations
asked Jan 31 at 16:21
Adam54Adam54
916
$endgroup$
$begingroup$
Are you sure the binomial coefficient should be written like that? That would become a half integer for even n.
$endgroup$
– SimpleProgrammer
Jan 31 at 16:28
$begingroup$
@SimpleProgrammer Thank you, your are right. I update the post.
$endgroup$
– Adam54
Jan 31 at 17:36
add a comment |
$begingroup$
Let the following complicated sum:
$$sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}.$$
Is there a way to simplify it? Or should we upper and lower bound it?
Thank you
combinatorics summation combinations
asked Jan 31 at 16:21
Adam54Adam54
916
$endgroup$
Let the following complicated sum:
$$sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}.$$
Is there a way to simplify it? Or should we upper and lower bound it?
Thank you
combinatorics summation combinations
combinatorics summation combinations
asked Jan 31 at 16:21
Adam54Adam54
916
asked Jan 31 at 16:21
Adam54Adam54
916
edited Jan 31 at 17:37
Adam54
asked Jan 31 at 16:21
Adam54Adam54
916
asked Jan 31 at 16:21
Adam54Adam54
916
asked Jan 31 at 16:21
Adam54Adam54
916
916
$begingroup$
Are you sure the binomial coefficient should be written like that? That would become a half integer for even n.
$endgroup$
– SimpleProgrammer
Jan 31 at 16:28
$begingroup$
@SimpleProgrammer Thank you, your are right. I update the post.
$endgroup$
– Adam54
Jan 31 at 17:36
add a comment |
$begingroup$
Are you sure the binomial coefficient should be written like that? That would become a half integer for even n.
$endgroup$
– SimpleProgrammer
Jan 31 at 16:28
$begingroup$
@SimpleProgrammer Thank you, your are right. I update the post.
$endgroup$
– Adam54
Jan 31 at 17:36
$begingroup$
Are you sure the binomial coefficient should be written like that? That would become a half integer for even n.
$endgroup$
– SimpleProgrammer
Jan 31 at 16:28
$begingroup$
Are you sure the binomial coefficient should be written like that? That would become a half integer for even n.
$endgroup$
– SimpleProgrammer
Jan 31 at 16:28
$begingroup$
@SimpleProgrammer Thank you, your are right. I update the post.
$endgroup$
– Adam54
Jan 31 at 17:36
$begingroup$
@SimpleProgrammer Thank you, your are right. I update the post.
$endgroup$
– Adam54
Jan 31 at 17:36
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Using Stirling's approximation, $$binom{2n}napproxfrac{sqrt{4pi n}left(dfrac{2n}eright)^{2n}}{2pi nleft(dfrac{n}eright)^{2n}}=frac{2^{2n}}{sqrt{pi n}}$$
so your sum should be $Theta(sqrt k)$.
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
$endgroup$
$begingroup$
Thank you for your answer. In fact, I was expecting a non-approximated solution.
$endgroup$
– Adam54
Jan 31 at 20:31
add a comment |
$begingroup$
Without approximation
$$S_k=sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}=frac{(1+k)}{2^{2( k+1)}} binom{2 (k+1)}{k+1}-frac{1}{2}=frac{Gamma left(k+frac{3}{2}right)}{k! ,sqrt{pi } }-frac{1}{2}$$ which would generate the sequence
$$left{frac{1}{4},frac{7}{16},frac{19}{32},frac{187}{256},frac{437}{512},frac
{1979}{2048},frac{4387}{4096},frac{76627}{65536},frac{165409}{131072},frac{7
07825}{524288},frac{1503829}{1048576},frac{12706671}{8388608}right}$$
For large values of $k$, an expansion would give
$$S_k=sqrt{frac k pi}-frac{1}{2}+frac{3 }{8 sqrt{pi k
}}-frac{7 }{128 sqrt{pi k^3
}}+Oleft(frac{1}{k^{5/2}}right)$$
For $k=10$, the exact value would be $S_{10}=frac{707825}{524288}approx 1.350069$ while the above expansion would give $frac{13273}{1280 sqrt{10 pi }}-frac{1}{2}approx 1.350053$.
Edit
Since you asked for them, the next terms of the expansion to $Oleft(frac{1}{k^{9/2}}right)$ would be
$$+frac{9 }{1024 sqrt{pi k^5}}+frac{59 }{32768 sqrt{pi k^7}}+Oleft(frac{1}{k^{9/2}}right)$$
If you want a quite good approximation, transforming the series into a simple Padé approximant, you could use
$$S_ksimeq -frac 12+frac 1 {16,sqrt {pi k} } frac{896 k^2+480 k+5 } {56 k+9 }$$ For $k=10$, this would give $approx 1.3500685$ for an exact value $approx 1.3500690$
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
$begingroup$
Thank you very much Claude! How big is the factor in the $O$?
$endgroup$
– Adam54
Feb 1 at 8:56
$begingroup$
@Adam54. Just a few minutes, please. I shall add a few things to my answer.
$endgroup$
– Claude Leibovici
Feb 1 at 9:09
$begingroup$
@Adam54. If you want more terms for the series or a better approximation using Padé approximants, let me know.
$endgroup$
– Claude Leibovici
Feb 1 at 9:41
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
});
}
});
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%2f3095084%2fsimplification-of-a-sum-involving-binomial-coefficient%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Using Stirling's approximation, $$binom{2n}napproxfrac{sqrt{4pi n}left(dfrac{2n}eright)^{2n}}{2pi nleft(dfrac{n}eright)^{2n}}=frac{2^{2n}}{sqrt{pi n}}$$
so your sum should be $Theta(sqrt k)$.
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
$endgroup$
$begingroup$
Thank you for your answer. In fact, I was expecting a non-approximated solution.
$endgroup$
– Adam54
Jan 31 at 20:31
add a comment |
$begingroup$
Using Stirling's approximation, $$binom{2n}napproxfrac{sqrt{4pi n}left(dfrac{2n}eright)^{2n}}{2pi nleft(dfrac{n}eright)^{2n}}=frac{2^{2n}}{sqrt{pi n}}$$
so your sum should be $Theta(sqrt k)$.
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
$endgroup$
$begingroup$
Thank you for your answer. In fact, I was expecting a non-approximated solution.
$endgroup$
– Adam54
Jan 31 at 20:31
add a comment |
$begingroup$
Using Stirling's approximation, $$binom{2n}napproxfrac{sqrt{4pi n}left(dfrac{2n}eright)^{2n}}{2pi nleft(dfrac{n}eright)^{2n}}=frac{2^{2n}}{sqrt{pi n}}$$
so your sum should be $Theta(sqrt k)$.
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
$endgroup$
Using Stirling's approximation, $$binom{2n}napproxfrac{sqrt{4pi n}left(dfrac{2n}eright)^{2n}}{2pi nleft(dfrac{n}eright)^{2n}}=frac{2^{2n}}{sqrt{pi n}}$$
so your sum should be $Theta(sqrt k)$.
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
answered Jan 31 at 17:47
Yves DaoustYves Daoust
132k676230
132k676230
$begingroup$
Thank you for your answer. In fact, I was expecting a non-approximated solution.
$endgroup$
– Adam54
Jan 31 at 20:31
add a comment |
$begingroup$
Thank you for your answer. In fact, I was expecting a non-approximated solution.
$endgroup$
– Adam54
Jan 31 at 20:31
$begingroup$
Thank you for your answer. In fact, I was expecting a non-approximated solution.
$endgroup$
– Adam54
Jan 31 at 20:31
$begingroup$
Thank you for your answer. In fact, I was expecting a non-approximated solution.
$endgroup$
– Adam54
Jan 31 at 20:31
add a comment |
$begingroup$
Without approximation
$$S_k=sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}=frac{(1+k)}{2^{2( k+1)}} binom{2 (k+1)}{k+1}-frac{1}{2}=frac{Gamma left(k+frac{3}{2}right)}{k! ,sqrt{pi } }-frac{1}{2}$$ which would generate the sequence
$$left{frac{1}{4},frac{7}{16},frac{19}{32},frac{187}{256},frac{437}{512},frac
{1979}{2048},frac{4387}{4096},frac{76627}{65536},frac{165409}{131072},frac{7
07825}{524288},frac{1503829}{1048576},frac{12706671}{8388608}right}$$
For large values of $k$, an expansion would give
$$S_k=sqrt{frac k pi}-frac{1}{2}+frac{3 }{8 sqrt{pi k
}}-frac{7 }{128 sqrt{pi k^3
}}+Oleft(frac{1}{k^{5/2}}right)$$
For $k=10$, the exact value would be $S_{10}=frac{707825}{524288}approx 1.350069$ while the above expansion would give $frac{13273}{1280 sqrt{10 pi }}-frac{1}{2}approx 1.350053$.
Edit
Since you asked for them, the next terms of the expansion to $Oleft(frac{1}{k^{9/2}}right)$ would be
$$+frac{9 }{1024 sqrt{pi k^5}}+frac{59 }{32768 sqrt{pi k^7}}+Oleft(frac{1}{k^{9/2}}right)$$
If you want a quite good approximation, transforming the series into a simple Padé approximant, you could use
$$S_ksimeq -frac 12+frac 1 {16,sqrt {pi k} } frac{896 k^2+480 k+5 } {56 k+9 }$$ For $k=10$, this would give $approx 1.3500685$ for an exact value $approx 1.3500690$
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
$begingroup$
Thank you very much Claude! How big is the factor in the $O$?
$endgroup$
– Adam54
Feb 1 at 8:56
$begingroup$
@Adam54. Just a few minutes, please. I shall add a few things to my answer.
$endgroup$
– Claude Leibovici
Feb 1 at 9:09
$begingroup$
@Adam54. If you want more terms for the series or a better approximation using Padé approximants, let me know.
$endgroup$
– Claude Leibovici
Feb 1 at 9:41
add a comment |
$begingroup$
Without approximation
$$S_k=sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}=frac{(1+k)}{2^{2( k+1)}} binom{2 (k+1)}{k+1}-frac{1}{2}=frac{Gamma left(k+frac{3}{2}right)}{k! ,sqrt{pi } }-frac{1}{2}$$ which would generate the sequence
$$left{frac{1}{4},frac{7}{16},frac{19}{32},frac{187}{256},frac{437}{512},frac
{1979}{2048},frac{4387}{4096},frac{76627}{65536},frac{165409}{131072},frac{7
07825}{524288},frac{1503829}{1048576},frac{12706671}{8388608}right}$$
For large values of $k$, an expansion would give
$$S_k=sqrt{frac k pi}-frac{1}{2}+frac{3 }{8 sqrt{pi k
}}-frac{7 }{128 sqrt{pi k^3
}}+Oleft(frac{1}{k^{5/2}}right)$$
For $k=10$, the exact value would be $S_{10}=frac{707825}{524288}approx 1.350069$ while the above expansion would give $frac{13273}{1280 sqrt{10 pi }}-frac{1}{2}approx 1.350053$.
Edit
Since you asked for them, the next terms of the expansion to $Oleft(frac{1}{k^{9/2}}right)$ would be
$$+frac{9 }{1024 sqrt{pi k^5}}+frac{59 }{32768 sqrt{pi k^7}}+Oleft(frac{1}{k^{9/2}}right)$$
If you want a quite good approximation, transforming the series into a simple Padé approximant, you could use
$$S_ksimeq -frac 12+frac 1 {16,sqrt {pi k} } frac{896 k^2+480 k+5 } {56 k+9 }$$ For $k=10$, this would give $approx 1.3500685$ for an exact value $approx 1.3500690$
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
$begingroup$
Thank you very much Claude! How big is the factor in the $O$?
$endgroup$
– Adam54
Feb 1 at 8:56
$begingroup$
@Adam54. Just a few minutes, please. I shall add a few things to my answer.
$endgroup$
– Claude Leibovici
Feb 1 at 9:09
$begingroup$
@Adam54. If you want more terms for the series or a better approximation using Padé approximants, let me know.
$endgroup$
– Claude Leibovici
Feb 1 at 9:41
add a comment |
$begingroup$
Without approximation
$$S_k=sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}=frac{(1+k)}{2^{2( k+1)}} binom{2 (k+1)}{k+1}-frac{1}{2}=frac{Gamma left(k+frac{3}{2}right)}{k! ,sqrt{pi } }-frac{1}{2}$$ which would generate the sequence
$$left{frac{1}{4},frac{7}{16},frac{19}{32},frac{187}{256},frac{437}{512},frac
{1979}{2048},frac{4387}{4096},frac{76627}{65536},frac{165409}{131072},frac{7
07825}{524288},frac{1503829}{1048576},frac{12706671}{8388608}right}$$
For large values of $k$, an expansion would give
$$S_k=sqrt{frac k pi}-frac{1}{2}+frac{3 }{8 sqrt{pi k
}}-frac{7 }{128 sqrt{pi k^3
}}+Oleft(frac{1}{k^{5/2}}right)$$
For $k=10$, the exact value would be $S_{10}=frac{707825}{524288}approx 1.350069$ while the above expansion would give $frac{13273}{1280 sqrt{10 pi }}-frac{1}{2}approx 1.350053$.
Edit
Since you asked for them, the next terms of the expansion to $Oleft(frac{1}{k^{9/2}}right)$ would be
$$+frac{9 }{1024 sqrt{pi k^5}}+frac{59 }{32768 sqrt{pi k^7}}+Oleft(frac{1}{k^{9/2}}right)$$
If you want a quite good approximation, transforming the series into a simple Padé approximant, you could use
$$S_ksimeq -frac 12+frac 1 {16,sqrt {pi k} } frac{896 k^2+480 k+5 } {56 k+9 }$$ For $k=10$, this would give $approx 1.3500685$ for an exact value $approx 1.3500690$
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
Without approximation
$$S_k=sum_{n=1}^k frac{1}{2^{2n+1}}binom{2n}{n}=frac{(1+k)}{2^{2( k+1)}} binom{2 (k+1)}{k+1}-frac{1}{2}=frac{Gamma left(k+frac{3}{2}right)}{k! ,sqrt{pi } }-frac{1}{2}$$ which would generate the sequence
$$left{frac{1}{4},frac{7}{16},frac{19}{32},frac{187}{256},frac{437}{512},frac
{1979}{2048},frac{4387}{4096},frac{76627}{65536},frac{165409}{131072},frac{7
07825}{524288},frac{1503829}{1048576},frac{12706671}{8388608}right}$$
For large values of $k$, an expansion would give
$$S_k=sqrt{frac k pi}-frac{1}{2}+frac{3 }{8 sqrt{pi k
}}-frac{7 }{128 sqrt{pi k^3
}}+Oleft(frac{1}{k^{5/2}}right)$$
For $k=10$, the exact value would be $S_{10}=frac{707825}{524288}approx 1.350069$ while the above expansion would give $frac{13273}{1280 sqrt{10 pi }}-frac{1}{2}approx 1.350053$.
Edit
Since you asked for them, the next terms of the expansion to $Oleft(frac{1}{k^{9/2}}right)$ would be
$$+frac{9 }{1024 sqrt{pi k^5}}+frac{59 }{32768 sqrt{pi k^7}}+Oleft(frac{1}{k^{9/2}}right)$$
If you want a quite good approximation, transforming the series into a simple Padé approximant, you could use
$$S_ksimeq -frac 12+frac 1 {16,sqrt {pi k} } frac{896 k^2+480 k+5 } {56 k+9 }$$ For $k=10$, this would give $approx 1.3500685$ for an exact value $approx 1.3500690$
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
edited Feb 1 at 9:39
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
answered Feb 1 at 5:51
Claude LeiboviciClaude Leibovici
125k1158135
125k1158135
$begingroup$
Thank you very much Claude! How big is the factor in the $O$?
$endgroup$
– Adam54
Feb 1 at 8:56
$begingroup$
@Adam54. Just a few minutes, please. I shall add a few things to my answer.
$endgroup$
– Claude Leibovici
Feb 1 at 9:09
$begingroup$
@Adam54. If you want more terms for the series or a better approximation using Padé approximants, let me know.
$endgroup$
– Claude Leibovici
Feb 1 at 9:41
add a comment |
$begingroup$
Thank you very much Claude! How big is the factor in the $O$?
$endgroup$
– Adam54
Feb 1 at 8:56
$begingroup$
@Adam54. Just a few minutes, please. I shall add a few things to my answer.
$endgroup$
– Claude Leibovici
Feb 1 at 9:09
$begingroup$
@Adam54. If you want more terms for the series or a better approximation using Padé approximants, let me know.
$endgroup$
– Claude Leibovici
Feb 1 at 9:41
$begingroup$
Thank you very much Claude! How big is the factor in the $O$?
$endgroup$
– Adam54
Feb 1 at 8:56
$begingroup$
Thank you very much Claude! How big is the factor in the $O$?
$endgroup$
– Adam54
Feb 1 at 8:56
$begingroup$
@Adam54. Just a few minutes, please. I shall add a few things to my answer.
$endgroup$
– Claude Leibovici
Feb 1 at 9:09
$begingroup$
@Adam54. Just a few minutes, please. I shall add a few things to my answer.
$endgroup$
– Claude Leibovici
Feb 1 at 9:09
$begingroup$
@Adam54. If you want more terms for the series or a better approximation using Padé approximants, let me know.
$endgroup$
– Claude Leibovici
Feb 1 at 9:41
$begingroup$
@Adam54. If you want more terms for the series or a better approximation using Padé approximants, let me know.
$endgroup$
– Claude Leibovici
Feb 1 at 9:41
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%2f3095084%2fsimplification-of-a-sum-involving-binomial-coefficient%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
$begingroup$
Are you sure the binomial coefficient should be written like that? That would become a half integer for even n.
$endgroup$
– SimpleProgrammer
Jan 31 at 16:28
$begingroup$
@SimpleProgrammer Thank you, your are right. I update the post.
$endgroup$
– Adam54
Jan 31 at 17:36