Mixing
How to identify the coefficient of $x^k$ in $1/(1-x)^N$ where $N$ can be a large integer
$begingroup$
I have an infinite serie in the form A(x) = 1/(1-x) which expanded is A(x) = 1 + x + x^2 + x^3...
I need to find the coefficient of the term x^K in A(x)^N where N can be a large number(2^32). I saw a solution overthere using induction, but I didn't understand it. Please suggest a different solution or help me to understand the solution that uses induction.
power-series generating-functions
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
$endgroup$
|
show 2 more comments
$begingroup$
I have an infinite serie in the form A(x) = 1/(1-x) which expanded is A(x) = 1 + x + x^2 + x^3...
I need to find the coefficient of the term x^K in A(x)^N where N can be a large number(2^32). I saw a solution overthere using induction, but I didn't understand it. Please suggest a different solution or help me to understand the solution that uses induction.
power-series generating-functions
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
$endgroup$
$begingroup$
Hint: Note that $frac {d^n}{dx^n}A(x)=frac 1{left(1-xright)^n}$.
$endgroup$
– lulu
Nov 3 '16 at 16:33
$begingroup$
@lulu, don't you mean $frac{1}{n!(1-x)^{n+1}}$?
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:37
$begingroup$
Let's try to get your induction started. What's the constant term in $A(x)^2$ going to be? $1$. What about the $x$ term? $1cdot x + x cdot 1 = 2x$. What about $x^2$? $1cdot x^2 + xcdot x + x^2cdot 1 = 3x^2$. See a pattern? Now try to figure out $A(x)^3$, and look for another pattern. Once you think you've found the general pattern, try to prove it.
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:40
1
$begingroup$
If you take $A(x)=1+x+x^2dots$ to the $N^text{th}$ power, you are multiplying $N$ copies of it together. By the rules of polynomial multiplication, this will be the sum of every possible product of one term from each copy. $x^k$ terms are products of terms whose exponents total $k$, so the coefficient is the same as the number of ways to write $N$ numbers from $0$ to $k$ totaling $k$, where the order matters. Don't know if that makes it easier or harder for you, but it's a different way of looking at it, anyway.
$endgroup$
– Gabriel Burns
Nov 3 '16 at 16:44
1
$begingroup$
@KyleFerendo Indeed I do. Thanks for the correction.
$endgroup$
– lulu
Nov 3 '16 at 16:47
|
show 2 more comments
$begingroup$
I have an infinite serie in the form A(x) = 1/(1-x) which expanded is A(x) = 1 + x + x^2 + x^3...
I need to find the coefficient of the term x^K in A(x)^N where N can be a large number(2^32). I saw a solution overthere using induction, but I didn't understand it. Please suggest a different solution or help me to understand the solution that uses induction.
power-series generating-functions
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
$endgroup$
I have an infinite serie in the form A(x) = 1/(1-x) which expanded is A(x) = 1 + x + x^2 + x^3...
I need to find the coefficient of the term x^K in A(x)^N where N can be a large number(2^32). I saw a solution overthere using induction, but I didn't understand it. Please suggest a different solution or help me to understand the solution that uses induction.
power-series generating-functions
power-series generating-functions
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
edited Nov 4 '16 at 21:09
Martín-Blas Pérez Pinilla
34.3k42871
34.3k42871
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
asked Nov 3 '16 at 16:29
Antonio González BorregoAntonio González Borrego
346
346
$begingroup$
Hint: Note that $frac {d^n}{dx^n}A(x)=frac 1{left(1-xright)^n}$.
$endgroup$
– lulu
Nov 3 '16 at 16:33
$begingroup$
@lulu, don't you mean $frac{1}{n!(1-x)^{n+1}}$?
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:37
$begingroup$
Let's try to get your induction started. What's the constant term in $A(x)^2$ going to be? $1$. What about the $x$ term? $1cdot x + x cdot 1 = 2x$. What about $x^2$? $1cdot x^2 + xcdot x + x^2cdot 1 = 3x^2$. See a pattern? Now try to figure out $A(x)^3$, and look for another pattern. Once you think you've found the general pattern, try to prove it.
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:40
1
$begingroup$
If you take $A(x)=1+x+x^2dots$ to the $N^text{th}$ power, you are multiplying $N$ copies of it together. By the rules of polynomial multiplication, this will be the sum of every possible product of one term from each copy. $x^k$ terms are products of terms whose exponents total $k$, so the coefficient is the same as the number of ways to write $N$ numbers from $0$ to $k$ totaling $k$, where the order matters. Don't know if that makes it easier or harder for you, but it's a different way of looking at it, anyway.
$endgroup$
– Gabriel Burns
Nov 3 '16 at 16:44
1
$begingroup$
@KyleFerendo Indeed I do. Thanks for the correction.
$endgroup$
– lulu
Nov 3 '16 at 16:47
|
show 2 more comments
$begingroup$
Hint: Note that $frac {d^n}{dx^n}A(x)=frac 1{left(1-xright)^n}$.
$endgroup$
– lulu
Nov 3 '16 at 16:33
$begingroup$
@lulu, don't you mean $frac{1}{n!(1-x)^{n+1}}$?
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:37
$begingroup$
Let's try to get your induction started. What's the constant term in $A(x)^2$ going to be? $1$. What about the $x$ term? $1cdot x + x cdot 1 = 2x$. What about $x^2$? $1cdot x^2 + xcdot x + x^2cdot 1 = 3x^2$. See a pattern? Now try to figure out $A(x)^3$, and look for another pattern. Once you think you've found the general pattern, try to prove it.
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:40
1
$begingroup$
If you take $A(x)=1+x+x^2dots$ to the $N^text{th}$ power, you are multiplying $N$ copies of it together. By the rules of polynomial multiplication, this will be the sum of every possible product of one term from each copy. $x^k$ terms are products of terms whose exponents total $k$, so the coefficient is the same as the number of ways to write $N$ numbers from $0$ to $k$ totaling $k$, where the order matters. Don't know if that makes it easier or harder for you, but it's a different way of looking at it, anyway.
$endgroup$
– Gabriel Burns
Nov 3 '16 at 16:44
1
$begingroup$
@KyleFerendo Indeed I do. Thanks for the correction.
$endgroup$
– lulu
Nov 3 '16 at 16:47
$begingroup$
Hint: Note that $frac {d^n}{dx^n}A(x)=frac 1{left(1-xright)^n}$.
$endgroup$
– lulu
Nov 3 '16 at 16:33
$begingroup$
Hint: Note that $frac {d^n}{dx^n}A(x)=frac 1{left(1-xright)^n}$.
$endgroup$
– lulu
Nov 3 '16 at 16:33
$begingroup$
@lulu, don't you mean $frac{1}{n!(1-x)^{n+1}}$?
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:37
$begingroup$
@lulu, don't you mean $frac{1}{n!(1-x)^{n+1}}$?
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:37
$begingroup$
Let's try to get your induction started. What's the constant term in $A(x)^2$ going to be? $1$. What about the $x$ term? $1cdot x + x cdot 1 = 2x$. What about $x^2$? $1cdot x^2 + xcdot x + x^2cdot 1 = 3x^2$. See a pattern? Now try to figure out $A(x)^3$, and look for another pattern. Once you think you've found the general pattern, try to prove it.
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:40
$begingroup$
Let's try to get your induction started. What's the constant term in $A(x)^2$ going to be? $1$. What about the $x$ term? $1cdot x + x cdot 1 = 2x$. What about $x^2$? $1cdot x^2 + xcdot x + x^2cdot 1 = 3x^2$. See a pattern? Now try to figure out $A(x)^3$, and look for another pattern. Once you think you've found the general pattern, try to prove it.
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:40
1
1
$begingroup$
If you take $A(x)=1+x+x^2dots$ to the $N^text{th}$ power, you are multiplying $N$ copies of it together. By the rules of polynomial multiplication, this will be the sum of every possible product of one term from each copy. $x^k$ terms are products of terms whose exponents total $k$, so the coefficient is the same as the number of ways to write $N$ numbers from $0$ to $k$ totaling $k$, where the order matters. Don't know if that makes it easier or harder for you, but it's a different way of looking at it, anyway.
$endgroup$
– Gabriel Burns
Nov 3 '16 at 16:44
$begingroup$
If you take $A(x)=1+x+x^2dots$ to the $N^text{th}$ power, you are multiplying $N$ copies of it together. By the rules of polynomial multiplication, this will be the sum of every possible product of one term from each copy. $x^k$ terms are products of terms whose exponents total $k$, so the coefficient is the same as the number of ways to write $N$ numbers from $0$ to $k$ totaling $k$, where the order matters. Don't know if that makes it easier or harder for you, but it's a different way of looking at it, anyway.
$endgroup$
– Gabriel Burns
Nov 3 '16 at 16:44
1
1
$begingroup$
@KyleFerendo Indeed I do. Thanks for the correction.
$endgroup$
– lulu
Nov 3 '16 at 16:47
$begingroup$
@KyleFerendo Indeed I do. Thanks for the correction.
$endgroup$
– lulu
Nov 3 '16 at 16:47
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
We can extract the coefficient of $x^k$ of $frac{1}{(1-x)^N}$ by using the binomial series expansion with $alpha = -N$.
begin{align*}
(1+x)^alpha=sum_{j=0}^inftybinom{alpha}{j}x^jqquadqquad |x|<1, alphainmathbb{C}tag{1}
end{align*}
It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.
We obtain
begin{align*}
[x^k]frac{1}{(1-x)^N}&=[x^k](1-x)^{-N}\
&=[x^k]sum_{j=0}^inftybinom{-N}{j}(-x)^jtag{1}\
&=[x^k]sum_{j=0}^inftybinom{N+j-1}{j}x^jtag{2}\
&=binom{N+k-1}{k}tag{3}
end{align*}
Comment:
In (1) we apply the binomial series expansion (1) with $alpha=-N$.
In (2) we use the binomial identity
begin{align*}
binom{-p}{q}=binom{p+q-1}{q}(-1)^q
end{align*}In (3) we select the coefficient of $x^k$.
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
add a comment |
$begingroup$
For $i=0,1,2....$ put $; C_{1,i}=1$.
Assume the following recurrence hypothesis
$$(A(x))^n=sum_{iin N}C_{n,i}x^i.$$
$$(A(x))^{n+1}
=(A(x))^nsum_{jin N}x^j$$
$$=sum_{i,j in N}C_{n,i}C_{1,j}x^{i+j}$$
$$=sum_{iin N}(sum_{j=0}^i C_{n,j})x^i$$
thus, we get the following recursive formula
$$C_{n+1,N}=sum_{j=0}^NC_{n,j}$$
with $C_{1,j}=1$ for $j=0,1,2...$.
For example, take $n=4,N=4$
$C_{2,0}=1,C_{2,1}=2,C_{2,2}=3,C_{2,3}=4,C_{2,4}=5$
$C_{3,0}=1,C_{3,1}=3,C_{3,2}=6,C_{3,3}=10,C_{3,4}=15$
$$C_{4,4}=1+3+6+10+15=35.$$
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
$endgroup$
$begingroup$
man, I don't understand the way you separate C(n+1,i)Xi at third step
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 17:31
$begingroup$
an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator.
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 19:02
$begingroup$
@AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$.
$endgroup$
– hamam_Abdallah
Nov 4 '16 at 20:21
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%2f1997844%2fhow-to-identify-the-coefficient-of-xk-in-1-1-xn-where-n-can-be-a-large%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$
We can extract the coefficient of $x^k$ of $frac{1}{(1-x)^N}$ by using the binomial series expansion with $alpha = -N$.
begin{align*}
(1+x)^alpha=sum_{j=0}^inftybinom{alpha}{j}x^jqquadqquad |x|<1, alphainmathbb{C}tag{1}
end{align*}
It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.
We obtain
begin{align*}
[x^k]frac{1}{(1-x)^N}&=[x^k](1-x)^{-N}\
&=[x^k]sum_{j=0}^inftybinom{-N}{j}(-x)^jtag{1}\
&=[x^k]sum_{j=0}^inftybinom{N+j-1}{j}x^jtag{2}\
&=binom{N+k-1}{k}tag{3}
end{align*}
Comment:
In (1) we apply the binomial series expansion (1) with $alpha=-N$.
In (2) we use the binomial identity
begin{align*}
binom{-p}{q}=binom{p+q-1}{q}(-1)^q
end{align*}In (3) we select the coefficient of $x^k$.
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
add a comment |
$begingroup$
We can extract the coefficient of $x^k$ of $frac{1}{(1-x)^N}$ by using the binomial series expansion with $alpha = -N$.
begin{align*}
(1+x)^alpha=sum_{j=0}^inftybinom{alpha}{j}x^jqquadqquad |x|<1, alphainmathbb{C}tag{1}
end{align*}
It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.
We obtain
begin{align*}
[x^k]frac{1}{(1-x)^N}&=[x^k](1-x)^{-N}\
&=[x^k]sum_{j=0}^inftybinom{-N}{j}(-x)^jtag{1}\
&=[x^k]sum_{j=0}^inftybinom{N+j-1}{j}x^jtag{2}\
&=binom{N+k-1}{k}tag{3}
end{align*}
Comment:
In (1) we apply the binomial series expansion (1) with $alpha=-N$.
In (2) we use the binomial identity
begin{align*}
binom{-p}{q}=binom{p+q-1}{q}(-1)^q
end{align*}In (3) we select the coefficient of $x^k$.
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
add a comment |
$begingroup$
We can extract the coefficient of $x^k$ of $frac{1}{(1-x)^N}$ by using the binomial series expansion with $alpha = -N$.
begin{align*}
(1+x)^alpha=sum_{j=0}^inftybinom{alpha}{j}x^jqquadqquad |x|<1, alphainmathbb{C}tag{1}
end{align*}
It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.
We obtain
begin{align*}
[x^k]frac{1}{(1-x)^N}&=[x^k](1-x)^{-N}\
&=[x^k]sum_{j=0}^inftybinom{-N}{j}(-x)^jtag{1}\
&=[x^k]sum_{j=0}^inftybinom{N+j-1}{j}x^jtag{2}\
&=binom{N+k-1}{k}tag{3}
end{align*}
Comment:
In (1) we apply the binomial series expansion (1) with $alpha=-N$.
In (2) we use the binomial identity
begin{align*}
binom{-p}{q}=binom{p+q-1}{q}(-1)^q
end{align*}In (3) we select the coefficient of $x^k$.
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
$endgroup$
We can extract the coefficient of $x^k$ of $frac{1}{(1-x)^N}$ by using the binomial series expansion with $alpha = -N$.
begin{align*}
(1+x)^alpha=sum_{j=0}^inftybinom{alpha}{j}x^jqquadqquad |x|<1, alphainmathbb{C}tag{1}
end{align*}
It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.
We obtain
begin{align*}
[x^k]frac{1}{(1-x)^N}&=[x^k](1-x)^{-N}\
&=[x^k]sum_{j=0}^inftybinom{-N}{j}(-x)^jtag{1}\
&=[x^k]sum_{j=0}^inftybinom{N+j-1}{j}x^jtag{2}\
&=binom{N+k-1}{k}tag{3}
end{align*}
Comment:
In (1) we apply the binomial series expansion (1) with $alpha=-N$.
In (2) we use the binomial identity
begin{align*}
binom{-p}{q}=binom{p+q-1}{q}(-1)^q
end{align*}In (3) we select the coefficient of $x^k$.
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
answered Nov 4 '16 at 14:23
Markus ScheuerMarkus Scheuer
61.3k456146
61.3k456146
add a comment |
add a comment |
$begingroup$
For $i=0,1,2....$ put $; C_{1,i}=1$.
Assume the following recurrence hypothesis
$$(A(x))^n=sum_{iin N}C_{n,i}x^i.$$
$$(A(x))^{n+1}
=(A(x))^nsum_{jin N}x^j$$
$$=sum_{i,j in N}C_{n,i}C_{1,j}x^{i+j}$$
$$=sum_{iin N}(sum_{j=0}^i C_{n,j})x^i$$
thus, we get the following recursive formula
$$C_{n+1,N}=sum_{j=0}^NC_{n,j}$$
with $C_{1,j}=1$ for $j=0,1,2...$.
For example, take $n=4,N=4$
$C_{2,0}=1,C_{2,1}=2,C_{2,2}=3,C_{2,3}=4,C_{2,4}=5$
$C_{3,0}=1,C_{3,1}=3,C_{3,2}=6,C_{3,3}=10,C_{3,4}=15$
$$C_{4,4}=1+3+6+10+15=35.$$
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
$endgroup$
$begingroup$
man, I don't understand the way you separate C(n+1,i)Xi at third step
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 17:31
$begingroup$
an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator.
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 19:02
$begingroup$
@AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$.
$endgroup$
– hamam_Abdallah
Nov 4 '16 at 20:21
add a comment |
$begingroup$
For $i=0,1,2....$ put $; C_{1,i}=1$.
Assume the following recurrence hypothesis
$$(A(x))^n=sum_{iin N}C_{n,i}x^i.$$
$$(A(x))^{n+1}
=(A(x))^nsum_{jin N}x^j$$
$$=sum_{i,j in N}C_{n,i}C_{1,j}x^{i+j}$$
$$=sum_{iin N}(sum_{j=0}^i C_{n,j})x^i$$
thus, we get the following recursive formula
$$C_{n+1,N}=sum_{j=0}^NC_{n,j}$$
with $C_{1,j}=1$ for $j=0,1,2...$.
For example, take $n=4,N=4$
$C_{2,0}=1,C_{2,1}=2,C_{2,2}=3,C_{2,3}=4,C_{2,4}=5$
$C_{3,0}=1,C_{3,1}=3,C_{3,2}=6,C_{3,3}=10,C_{3,4}=15$
$$C_{4,4}=1+3+6+10+15=35.$$
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
$endgroup$
$begingroup$
man, I don't understand the way you separate C(n+1,i)Xi at third step
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 17:31
$begingroup$
an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator.
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 19:02
$begingroup$
@AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$.
$endgroup$
– hamam_Abdallah
Nov 4 '16 at 20:21
add a comment |
$begingroup$
For $i=0,1,2....$ put $; C_{1,i}=1$.
Assume the following recurrence hypothesis
$$(A(x))^n=sum_{iin N}C_{n,i}x^i.$$
$$(A(x))^{n+1}
=(A(x))^nsum_{jin N}x^j$$
$$=sum_{i,j in N}C_{n,i}C_{1,j}x^{i+j}$$
$$=sum_{iin N}(sum_{j=0}^i C_{n,j})x^i$$
thus, we get the following recursive formula
$$C_{n+1,N}=sum_{j=0}^NC_{n,j}$$
with $C_{1,j}=1$ for $j=0,1,2...$.
For example, take $n=4,N=4$
$C_{2,0}=1,C_{2,1}=2,C_{2,2}=3,C_{2,3}=4,C_{2,4}=5$
$C_{3,0}=1,C_{3,1}=3,C_{3,2}=6,C_{3,3}=10,C_{3,4}=15$
$$C_{4,4}=1+3+6+10+15=35.$$
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
$endgroup$
For $i=0,1,2....$ put $; C_{1,i}=1$.
Assume the following recurrence hypothesis
$$(A(x))^n=sum_{iin N}C_{n,i}x^i.$$
$$(A(x))^{n+1}
=(A(x))^nsum_{jin N}x^j$$
$$=sum_{i,j in N}C_{n,i}C_{1,j}x^{i+j}$$
$$=sum_{iin N}(sum_{j=0}^i C_{n,j})x^i$$
thus, we get the following recursive formula
$$C_{n+1,N}=sum_{j=0}^NC_{n,j}$$
with $C_{1,j}=1$ for $j=0,1,2...$.
For example, take $n=4,N=4$
$C_{2,0}=1,C_{2,1}=2,C_{2,2}=3,C_{2,3}=4,C_{2,4}=5$
$C_{3,0}=1,C_{3,1}=3,C_{3,2}=6,C_{3,3}=10,C_{3,4}=15$
$$C_{4,4}=1+3+6+10+15=35.$$
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
edited Nov 4 '16 at 20:20
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
answered Nov 3 '16 at 16:54
hamam_Abdallahhamam_Abdallah
38k21634
38k21634
$begingroup$
man, I don't understand the way you separate C(n+1,i)Xi at third step
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 17:31
$begingroup$
an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator.
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 19:02
$begingroup$
@AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$.
$endgroup$
– hamam_Abdallah
Nov 4 '16 at 20:21
add a comment |
$begingroup$
man, I don't understand the way you separate C(n+1,i)Xi at third step
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 17:31
$begingroup$
an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator.
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 19:02
$begingroup$
@AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$.
$endgroup$
– hamam_Abdallah
Nov 4 '16 at 20:21
$begingroup$
man, I don't understand the way you separate C(n+1,i)Xi at third step
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 17:31
$begingroup$
man, I don't understand the way you separate C(n+1,i)Xi at third step
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 17:31
$begingroup$
an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator.
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 19:02
$begingroup$
an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator.
$endgroup$
– Antonio González Borrego
Nov 3 '16 at 19:02
$begingroup$
@AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$.
$endgroup$
– hamam_Abdallah
Nov 4 '16 at 20:21
$begingroup$
@AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$.
$endgroup$
– hamam_Abdallah
Nov 4 '16 at 20:21
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%2f1997844%2fhow-to-identify-the-coefficient-of-xk-in-1-1-xn-where-n-can-be-a-large%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$
Hint: Note that $frac {d^n}{dx^n}A(x)=frac 1{left(1-xright)^n}$.
$endgroup$
– lulu
Nov 3 '16 at 16:33
$begingroup$
@lulu, don't you mean $frac{1}{n!(1-x)^{n+1}}$?
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:37
$begingroup$
Let's try to get your induction started. What's the constant term in $A(x)^2$ going to be? $1$. What about the $x$ term? $1cdot x + x cdot 1 = 2x$. What about $x^2$? $1cdot x^2 + xcdot x + x^2cdot 1 = 3x^2$. See a pattern? Now try to figure out $A(x)^3$, and look for another pattern. Once you think you've found the general pattern, try to prove it.
$endgroup$
– Kyle Ferendo
Nov 3 '16 at 16:40
1
$begingroup$
If you take $A(x)=1+x+x^2dots$ to the $N^text{th}$ power, you are multiplying $N$ copies of it together. By the rules of polynomial multiplication, this will be the sum of every possible product of one term from each copy. $x^k$ terms are products of terms whose exponents total $k$, so the coefficient is the same as the number of ways to write $N$ numbers from $0$ to $k$ totaling $k$, where the order matters. Don't know if that makes it easier or harder for you, but it's a different way of looking at it, anyway.
$endgroup$
– Gabriel Burns
Nov 3 '16 at 16:44
1
$begingroup$
@KyleFerendo Indeed I do. Thanks for the correction.
$endgroup$
– lulu
Nov 3 '16 at 16:47