Mixing
Concluding a proof with polynomials.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I wish to prove the following: Let $g$ be a polynomial with integer coefficients and let $$h(x)=fracg(x)(p-1)!$$ for some $pinBbbN$.
Then $forall igeq p:h^(i)$ is a polynomial with integer coefficients such that each is divisible by $p$. My go:
For $p>degg$ proof is trivial because $h^(p)=0$ and for any $igeq p$ too. Let $pleq degg$. Formally, I want to prove by induction, prove the base step and then induction holds, because taking more derivatives doesn't change the divisibility.
So, i started writing out the derivatives...
$$h(x)=fracg_0(p-1)!+fracg_1x(p-1)!+fracg_2x^2(p-1)!+fracg_3x^3(p-1)!+fracg_4x^4(p-1)!+cdots+fracg_nx^n(p-1)!$$
$$h'(x)=fracg_1(p-1)!+frac2g_2x(p-1)!+frac3g_3x^2(p-1)!+frac4g_4x^3(p-1)!+frac5g_5x^4(p-1)!+cdots+fracng_nx^n-1(p-1)!$$
$$h''(x)=frac2cdot 1g_2(p-1)!+frac3cdot 2g_3x(p-1)!+frac4cdot3g_4x^2(p-1)!+frac5cdot4g_5x^3(p-1)!+frac6cdot 5g_6x^4(p-1)!+cdots+fracn(n-1)g_nx^n-2(p-1)!$$
For some $k$-th derivative the term with $g_k-1$ vanishes and the absolute term has $k!$ in the numerator:
$$h^(p)(x)=fracp!g_p(p-1)!+fracfrac(p+1)!1!g_p+1x(p-1)!+fracfrac(p+2)!2!g_p+2x^2(p-1)!+fracfrac(p+3)!3!g_p+3x^3(p-1)!+cdots$$
Now in the first term $p!$ and $(p-1)!$ cancels out and we are left with $pg_p$ which is divisible by $p$.
Is this reasoning for the next terms correct?
For some $j$-th term in $h^(p)(x)$ we cancel out the $(p-1)!$ and in the numerator we are left with $frac(p+j)(p+j-1)(p+j-2)cdots (p+2)(p+1)pj!g_p+jx^j$. Now $p+j,p+j-1,p+j-2...p+2,p+1$ is sequence of $j$ consecutive integers, thus for any $1leq ileq j$ (thus all factors of $j!$) we find some number $l$ in the sequence such that $i mid l$.
proof-verification polynomials
asked Jul 31 at 15:20
Michal Dvořák
48912
add a comment |Â
up vote
0
down vote
favorite
I wish to prove the following: Let $g$ be a polynomial with integer coefficients and let $$h(x)=fracg(x)(p-1)!$$ for some $pinBbbN$.
Then $forall igeq p:h^(i)$ is a polynomial with integer coefficients such that each is divisible by $p$. My go:
For $p>degg$ proof is trivial because $h^(p)=0$ and for any $igeq p$ too. Let $pleq degg$. Formally, I want to prove by induction, prove the base step and then induction holds, because taking more derivatives doesn't change the divisibility.
So, i started writing out the derivatives...
$$h(x)=fracg_0(p-1)!+fracg_1x(p-1)!+fracg_2x^2(p-1)!+fracg_3x^3(p-1)!+fracg_4x^4(p-1)!+cdots+fracg_nx^n(p-1)!$$
$$h'(x)=fracg_1(p-1)!+frac2g_2x(p-1)!+frac3g_3x^2(p-1)!+frac4g_4x^3(p-1)!+frac5g_5x^4(p-1)!+cdots+fracng_nx^n-1(p-1)!$$
$$h''(x)=frac2cdot 1g_2(p-1)!+frac3cdot 2g_3x(p-1)!+frac4cdot3g_4x^2(p-1)!+frac5cdot4g_5x^3(p-1)!+frac6cdot 5g_6x^4(p-1)!+cdots+fracn(n-1)g_nx^n-2(p-1)!$$
For some $k$-th derivative the term with $g_k-1$ vanishes and the absolute term has $k!$ in the numerator:
$$h^(p)(x)=fracp!g_p(p-1)!+fracfrac(p+1)!1!g_p+1x(p-1)!+fracfrac(p+2)!2!g_p+2x^2(p-1)!+fracfrac(p+3)!3!g_p+3x^3(p-1)!+cdots$$
Now in the first term $p!$ and $(p-1)!$ cancels out and we are left with $pg_p$ which is divisible by $p$.
Is this reasoning for the next terms correct?
For some $j$-th term in $h^(p)(x)$ we cancel out the $(p-1)!$ and in the numerator we are left with $frac(p+j)(p+j-1)(p+j-2)cdots (p+2)(p+1)pj!g_p+jx^j$. Now $p+j,p+j-1,p+j-2...p+2,p+1$ is sequence of $j$ consecutive integers, thus for any $1leq ileq j$ (thus all factors of $j!$) we find some number $l$ in the sequence such that $i mid l$.
proof-verification polynomials
asked Jul 31 at 15:20
Michal Dvořák
48912
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I wish to prove the following: Let $g$ be a polynomial with integer coefficients and let $$h(x)=fracg(x)(p-1)!$$ for some $pinBbbN$.
Then $forall igeq p:h^(i)$ is a polynomial with integer coefficients such that each is divisible by $p$. My go:
For $p>degg$ proof is trivial because $h^(p)=0$ and for any $igeq p$ too. Let $pleq degg$. Formally, I want to prove by induction, prove the base step and then induction holds, because taking more derivatives doesn't change the divisibility.
So, i started writing out the derivatives...
$$h(x)=fracg_0(p-1)!+fracg_1x(p-1)!+fracg_2x^2(p-1)!+fracg_3x^3(p-1)!+fracg_4x^4(p-1)!+cdots+fracg_nx^n(p-1)!$$
$$h'(x)=fracg_1(p-1)!+frac2g_2x(p-1)!+frac3g_3x^2(p-1)!+frac4g_4x^3(p-1)!+frac5g_5x^4(p-1)!+cdots+fracng_nx^n-1(p-1)!$$
$$h''(x)=frac2cdot 1g_2(p-1)!+frac3cdot 2g_3x(p-1)!+frac4cdot3g_4x^2(p-1)!+frac5cdot4g_5x^3(p-1)!+frac6cdot 5g_6x^4(p-1)!+cdots+fracn(n-1)g_nx^n-2(p-1)!$$
For some $k$-th derivative the term with $g_k-1$ vanishes and the absolute term has $k!$ in the numerator:
$$h^(p)(x)=fracp!g_p(p-1)!+fracfrac(p+1)!1!g_p+1x(p-1)!+fracfrac(p+2)!2!g_p+2x^2(p-1)!+fracfrac(p+3)!3!g_p+3x^3(p-1)!+cdots$$
Now in the first term $p!$ and $(p-1)!$ cancels out and we are left with $pg_p$ which is divisible by $p$.
Is this reasoning for the next terms correct?
For some $j$-th term in $h^(p)(x)$ we cancel out the $(p-1)!$ and in the numerator we are left with $frac(p+j)(p+j-1)(p+j-2)cdots (p+2)(p+1)pj!g_p+jx^j$. Now $p+j,p+j-1,p+j-2...p+2,p+1$ is sequence of $j$ consecutive integers, thus for any $1leq ileq j$ (thus all factors of $j!$) we find some number $l$ in the sequence such that $i mid l$.
proof-verification polynomials
asked Jul 31 at 15:20
Michal Dvořák
48912
I wish to prove the following: Let $g$ be a polynomial with integer coefficients and let $$h(x)=fracg(x)(p-1)!$$ for some $pinBbbN$.
Then $forall igeq p:h^(i)$ is a polynomial with integer coefficients such that each is divisible by $p$. My go:
For $p>degg$ proof is trivial because $h^(p)=0$ and for any $igeq p$ too. Let $pleq degg$. Formally, I want to prove by induction, prove the base step and then induction holds, because taking more derivatives doesn't change the divisibility.
So, i started writing out the derivatives...
$$h(x)=fracg_0(p-1)!+fracg_1x(p-1)!+fracg_2x^2(p-1)!+fracg_3x^3(p-1)!+fracg_4x^4(p-1)!+cdots+fracg_nx^n(p-1)!$$
$$h'(x)=fracg_1(p-1)!+frac2g_2x(p-1)!+frac3g_3x^2(p-1)!+frac4g_4x^3(p-1)!+frac5g_5x^4(p-1)!+cdots+fracng_nx^n-1(p-1)!$$
$$h''(x)=frac2cdot 1g_2(p-1)!+frac3cdot 2g_3x(p-1)!+frac4cdot3g_4x^2(p-1)!+frac5cdot4g_5x^3(p-1)!+frac6cdot 5g_6x^4(p-1)!+cdots+fracn(n-1)g_nx^n-2(p-1)!$$
For some $k$-th derivative the term with $g_k-1$ vanishes and the absolute term has $k!$ in the numerator:
$$h^(p)(x)=fracp!g_p(p-1)!+fracfrac(p+1)!1!g_p+1x(p-1)!+fracfrac(p+2)!2!g_p+2x^2(p-1)!+fracfrac(p+3)!3!g_p+3x^3(p-1)!+cdots$$
Now in the first term $p!$ and $(p-1)!$ cancels out and we are left with $pg_p$ which is divisible by $p$.
Is this reasoning for the next terms correct?
For some $j$-th term in $h^(p)(x)$ we cancel out the $(p-1)!$ and in the numerator we are left with $frac(p+j)(p+j-1)(p+j-2)cdots (p+2)(p+1)pj!g_p+jx^j$. Now $p+j,p+j-1,p+j-2...p+2,p+1$ is sequence of $j$ consecutive integers, thus for any $1leq ileq j$ (thus all factors of $j!$) we find some number $l$ in the sequence such that $i mid l$.
proof-verification polynomials
asked Jul 31 at 15:20
Michal Dvořák
48912
asked Jul 31 at 15:20
Michal Dvořák
48912
asked Jul 31 at 15:20
Michal Dvořák
48912
asked Jul 31 at 15:20
Michal Dvořák
48912
48912
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
I guess you want to show that the product of $p$ consecutive positive integers is divisible by $p!.$ Consider that $$
fracN(N-1)dots(N-p+1)p!=Nchoose p$$
answered Jul 31 at 15:33
saulspatz
10.3k21324
Ah, I didn't realise that, so $fracp+j(p+j-1)(p+j-2)cdots(p+2)(p+1)pj!=pcdotp+jchoosejinBbbN$ and divisible by $p$ right?
– Michal Dvořák
Jul 31 at 15:39
You mean $p+jchoose j$ I think
– saulspatz
Jul 31 at 15:41
Yes, edited it. Thanks!
– Michal Dvořák
Jul 31 at 15:42
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
I guess you want to show that the product of $p$ consecutive positive integers is divisible by $p!.$ Consider that $$
fracN(N-1)dots(N-p+1)p!=Nchoose p$$
answered Jul 31 at 15:33
saulspatz
10.3k21324
Ah, I didn't realise that, so $fracp+j(p+j-1)(p+j-2)cdots(p+2)(p+1)pj!=pcdotp+jchoosejinBbbN$ and divisible by $p$ right?
– Michal Dvořák
Jul 31 at 15:39
You mean $p+jchoose j$ I think
– saulspatz
Jul 31 at 15:41
Yes, edited it. Thanks!
– Michal Dvořák
Jul 31 at 15:42
add a comment |Â
up vote
1
down vote
accepted
I guess you want to show that the product of $p$ consecutive positive integers is divisible by $p!.$ Consider that $$
fracN(N-1)dots(N-p+1)p!=Nchoose p$$
answered Jul 31 at 15:33
saulspatz
10.3k21324
Ah, I didn't realise that, so $fracp+j(p+j-1)(p+j-2)cdots(p+2)(p+1)pj!=pcdotp+jchoosejinBbbN$ and divisible by $p$ right?
– Michal Dvořák
Jul 31 at 15:39
You mean $p+jchoose j$ I think
– saulspatz
Jul 31 at 15:41
Yes, edited it. Thanks!
– Michal Dvořák
Jul 31 at 15:42
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
I guess you want to show that the product of $p$ consecutive positive integers is divisible by $p!.$ Consider that $$
fracN(N-1)dots(N-p+1)p!=Nchoose p$$
answered Jul 31 at 15:33
saulspatz
10.3k21324
I guess you want to show that the product of $p$ consecutive positive integers is divisible by $p!.$ Consider that $$
fracN(N-1)dots(N-p+1)p!=Nchoose p$$
answered Jul 31 at 15:33
saulspatz
10.3k21324
answered Jul 31 at 15:33
saulspatz
10.3k21324
answered Jul 31 at 15:33
saulspatz
10.3k21324
answered Jul 31 at 15:33
saulspatz
10.3k21324
10.3k21324
Ah, I didn't realise that, so $fracp+j(p+j-1)(p+j-2)cdots(p+2)(p+1)pj!=pcdotp+jchoosejinBbbN$ and divisible by $p$ right?
– Michal Dvořák
Jul 31 at 15:39
You mean $p+jchoose j$ I think
– saulspatz
Jul 31 at 15:41
Yes, edited it. Thanks!
– Michal Dvořák
Jul 31 at 15:42
add a comment |Â
Ah, I didn't realise that, so $fracp+j(p+j-1)(p+j-2)cdots(p+2)(p+1)pj!=pcdotp+jchoosejinBbbN$ and divisible by $p$ right?
– Michal Dvořák
Jul 31 at 15:39
You mean $p+jchoose j$ I think
– saulspatz
Jul 31 at 15:41
Yes, edited it. Thanks!
– Michal Dvořák
Jul 31 at 15:42
Ah, I didn't realise that, so $fracp+j(p+j-1)(p+j-2)cdots(p+2)(p+1)pj!=pcdotp+jchoosejinBbbN$ and divisible by $p$ right?
– Michal Dvořák
Jul 31 at 15:39
Ah, I didn't realise that, so $fracp+j(p+j-1)(p+j-2)cdots(p+2)(p+1)pj!=pcdotp+jchoosejinBbbN$ and divisible by $p$ right?
– Michal Dvořák
Jul 31 at 15:39
You mean $p+jchoose j$ I think
– saulspatz
Jul 31 at 15:41
You mean $p+jchoose j$ I think
– saulspatz
Jul 31 at 15:41
Yes, edited it. Thanks!
– Michal Dvořák
Jul 31 at 15:42
Yes, edited it. Thanks!
– Michal Dvořák
Jul 31 at 15:42
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868170%2fconcluding-a-proof-with-polynomials%23new-answer', 'question_page');
);
Post as a guest
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
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
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