Looking for a proof for this counting problem
up vote
3
down vote
favorite
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
edited Dec 2 at 21:46
LutzL
54.4k41953
asked Dec 2 at 17:41
rsadhvika
1,5181228
|
show 4 more comments
up vote
3
down vote
favorite
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
edited Dec 2 at 21:46
LutzL
54.4k41953
asked Dec 2 at 17:41
rsadhvika
1,5181228
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 at 4:47
|
show 4 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
edited Dec 2 at 21:46
LutzL
54.4k41953
asked Dec 2 at 17:41
rsadhvika
1,5181228
Consider all the coefficients in the expansion of
$$(x^a+x^b)^n$$
where $a,b,n$ are non negative integers.
Claim: The $color{Red}{textit{exponent}}$ with the $color{blue}{textit {maximum coefficient value}}$ in the expansion is $color{red}{lfloorfrac{n(a+b)}2rfloor}$
Example :
$(x^1+x^3)^4 = sumlimits_{k=0}^4binom{4}{k}x^{n-k}x^{3k} = x^{4} +4x^{6}+color{blue}{6}x^{color{red}{8}}+4x^{10}+x^{12}$
$color{red}{dfrac{4(1+3)}{2} = 8}$.
I feel this is a special case of central limit theorem in probability, but that theorem seems way more complicated to understand than my special case. So I'm trying to make sense of this result w/o using CLT. Any help ?
combinatorics
combinatorics
edited Dec 2 at 21:46
LutzL
54.4k41953
asked Dec 2 at 17:41
rsadhvika
1,5181228
edited Dec 2 at 21:46
LutzL
54.4k41953
asked Dec 2 at 17:41
rsadhvika
1,5181228
edited Dec 2 at 21:46
LutzL
54.4k41953
edited Dec 2 at 21:46
LutzL
54.4k41953
edited Dec 2 at 21:46
LutzL
54.4k41953
54.4k41953
asked Dec 2 at 17:41
rsadhvika
1,5181228
asked Dec 2 at 17:41
rsadhvika
1,5181228
asked Dec 2 at 17:41
rsadhvika
1,5181228
1,5181228
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 at 4:47
|
show 4 more comments
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 at 4:47
1
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 at 17:46
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 at 17:49
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 at 17:49
1
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 at 17:49
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 at 17:49
1
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 at 0:31
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 at 0:31
1
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 at 4:47
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 at 4:47
|
show 4 more comments
3 Answers
3
active
oldest
votes
up vote
6
down vote
accepted
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
answered Dec 2 at 17:47
Boshu
694315
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 at 18:05
add a comment |
up vote
5
down vote
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
answered Dec 2 at 17:51
John_Wick
1,144111
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 at 21:46
add a comment |
up vote
3
down vote
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
answered Dec 2 at 17:51
Yves Daoust
123k668218
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
answered Dec 2 at 17:47
Boshu
694315
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 at 18:05
add a comment |
up vote
6
down vote
accepted
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
answered Dec 2 at 17:47
Boshu
694315
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 at 18:05
add a comment |
up vote
6
down vote
accepted
up vote
6
down vote
accepted
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
answered Dec 2 at 17:47
Boshu
694315
If you know the binomial expansion (which you seem to), then this follows almost immediately. The key point to remember is that the maximum value of the coefficient is obtained at $nchoose k$, where $k$ is the largest integer less than or equal to $frac{n}{2}$. To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is greater than $1$. Plug in your value of $k$ and you get your result.
PS: Note that your exponents must actually appear in the expansion for this to happen.
answered Dec 2 at 17:47
Boshu
694315
edited Dec 2 at 18:06
answered Dec 2 at 17:47
Boshu
694315
answered Dec 2 at 17:47
Boshu
694315
answered Dec 2 at 17:47
Boshu
694315
694315
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 at 18:05
add a comment |
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 at 18:05
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 at 18:01
Ahh I kindof see now how this can be related to the max coefficient in binomial expansion. Ty :) Pretty sure you meant this : $$$$ To prove this, consider the ratios $frac{n choose k+1}{nchoose k}$ and see for what range this is $color{red}{greater ~than~ 1}$.
– rsadhvika
Dec 2 at 18:01
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 at 18:05
Ah yes you’re right, I meant that the binomial coefficient itself is increasing, not the ratio. I’ll correct that.
– Boshu
Dec 2 at 18:05
add a comment |
up vote
5
down vote
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
answered Dec 2 at 17:51
John_Wick
1,144111
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 at 21:46
add a comment |
up vote
5
down vote
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
answered Dec 2 at 17:51
John_Wick
1,144111
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 at 21:46
add a comment |
up vote
5
down vote
up vote
5
down vote
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
answered Dec 2 at 17:51
John_Wick
1,144111
$(x^a+x^b)^n=x^{na}(1+x^c)^n=sum_{k=0}^n{n choose k}x^{na+k(b-a)}$. Now, ${n choose k}$ is maximum for $k=[n/2].$ So, answer is $na+[n/2](b-a)$ which matches with your answer if $n$ is even.
answered Dec 2 at 17:51
John_Wick
1,144111
answered Dec 2 at 17:51
John_Wick
1,144111
answered Dec 2 at 17:51
John_Wick
1,144111
answered Dec 2 at 17:51
John_Wick
1,144111
1,144111
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 at 21:46
add a comment |
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 at 21:46
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 at 21:46
$c = b-a$; I like your approach more. It is neat and to the point, but I started working on the other answer first so had to mark it best as it helped me first. Thank you so much John_Wick you're awesome :)
– rsadhvika
Dec 2 at 21:46
add a comment |
up vote
3
down vote
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
answered Dec 2 at 17:51
Yves Daoust
123k668218
add a comment |
up vote
3
down vote
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
answered Dec 2 at 17:51
Yves Daoust
123k668218
add a comment |
up vote
3
down vote
up vote
3
down vote
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
answered Dec 2 at 17:51
Yves Daoust
123k668218
The exponents of the development run from $na$ to $nb$, in increments $b-a$. By symmetry, the requested exponent can only be
$$frac{n(a+b)}{2}$$ when the numerator is even, and
$$frac{n(a+b)pm(b-a)}{2}$$
otherwise (there will be two consecutive terms with equal coefficient).
answered Dec 2 at 17:51
Yves Daoust
123k668218
edited Dec 2 at 17:58
answered Dec 2 at 17:51
Yves Daoust
123k668218
answered Dec 2 at 17:51
Yves Daoust
123k668218
answered Dec 2 at 17:51
Yves Daoust
123k668218
123k668218
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3022949%2flooking-for-a-proof-for-this-counting-problem%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
1
Well you need to add something here, because this is false with $a=1$, $b=2$, and $n=1$.
– BlarglFlarg
Dec 2 at 17:46
Oh sorry when n(a+b)/2 is not an integer, both the ceil and floor will have the same coefficients.. I'll add this in the question. Ty @BlarglFlarg
– rsadhvika
Dec 2 at 17:49
1
It is just related to the binomial coefficients characteristics, nothing to do with a and b. Look at how they are calculated with Pascal' triangle
– Damien
Dec 2 at 17:49
1
I know that the beauty of mathematics partially relies on the fact that it can connect seemingly unrelated topics but... how do you see a connection to CLT in this problem?
– Taladris
Dec 3 at 0:31
1
@Taladris From what I understand it is (a bit) connected because $left(frac{x^a+x^b}{2}right)^n$ is the generating function of some sort of binomial distribution. (?)
– Idéophage
Dec 3 at 4:47