The application of Synthetic division in Polynomial theory
by fungarwai, Feb 9, 2023, 4:40 AM
Power sum of polynomial roots
Synthetic division can be applied to find the power sums of roots of a polynomial
by dividing with
has two real roots
The coefficients of the quotient show that
This result is caused by the formula
Reference: The application of Synthetic division in Polynomial theory (Chinese) Section 1.1.5
Proof
Example
Python program to generate Synthetic division in LaTeX code
pywindow code
Synthetic division can be applied to find the power sums of roots of a polynomial
by dividing with
has two real roots
The coefficients of the quotient show that
This result is caused by the formula
Reference: The application of Synthetic division in Polynomial theory (Chinese) Section 1.1.5
Proof
Let ,
Suppose , the Laurent series of can be expressed as
Each term in the Laurent series is unique.
As the coefficients of the quotient are determined one by one with Synthetic division, the power sums of polynomial roots are computed.
Suppose , the Laurent series of can be expressed as
Each term in the Laurent series is unique.
As the coefficients of the quotient are determined one by one with Synthetic division, the power sums of polynomial roots are computed.
Example
a,b,c are roots of the equation x³-9x+9 = 0.
Find the value of -
1/a³ + 1/b³ + 1/c³
1/a⁵ + 1/b⁵ + 1/c⁵.
Reference: Sum of powers of roots
Let
Compute with Synthetic division
i.e.
Find the value of -
1/a³ + 1/b³ + 1/c³
1/a⁵ + 1/b⁵ + 1/c⁵.
Reference: Sum of powers of roots
Let
Compute with Synthetic division
i.e.
Python program to generate Synthetic division in LaTeX code
dividend=[27,-18,0];#input by user, 27x^2-18x for example divisor=[9,-9,0,1];#input by user, 9x^3-9x^2+1 for example def roundint(x): if x == int(x): return str(int(x)) else: for k in range(1,100): T=0 if x*k == int(x*k): T=1;break; if T==1: return "\dfrac{"+str(int(x*k))+"}{"+str(k)+"}" else: return str(round(x,3)) qlen=11;e=0; dlen=len(divisor)-1; ddlen=len(dividend); dd="~ " for k in range(0,ddlen): dividend[k]=dividend[k]/divisor[0] dd=dd+"& "+roundint(dividend[k])+" " for k in range(0,qlen-ddlen+1): dividend.append(0) dd=dd+"\\\\\n" for k in range(1,dlen+1): divisor[k]=-divisor[k]/divisor[0] q=[] q.append(dividend[0]) qq="~ & "+roundint(q[0])+" " s="$\\begin{array}{c|" s2=[] for k in range(1,dlen+1): s2.append(roundint(divisor[k])+" ") for k in range(0,dlen): for i in range(0,k+1): s2[k]=s2[k]+"& ~ " for i in range(0,qlen-dlen): t=dividend[i+1] for k in range(0,dlen): tt=q[i]*divisor[k+1] s2[k]=s2[k]+"& "+roundint(tt)+" " if i-k >= 0: t=t+q[i-k]*divisor[k+1] q.append(t) if t==0: e=e+1 else: e=0 if e>=dlen and i>=ddlen-1: break qq=qq+"& "+roundint(t)+" " for i in range(qlen-dlen,qlen-1): if e>=dlen and i>=ddlen-1: break t=dividend[i+1] for k in range(0,dlen): if i-k < qlen-dlen: t=t+q[i-k]*divisor[k+1] q.append(t) qq=qq+"& "+roundint(t)+" " for k in range(0,qlen+1): s=s+"c" s=s+"}\n"+dd for k in range(0,dlen): s=s+s2[k]+"\\\\\n" s=s+"\\hline\n"+qq+"\\end{array}$" print(s)
pywindow code
[pywindow]
dividend=[27,-18,0];#input by user, 27x^2-18x for example
divisor=[9,-9,0,1];#input by user, 9x^3-9x^2+1 for example
def roundint(x):
if x == int(x):
return str(int(x))
else:
for k in range(1,100):
T=0
if x*k == int(x*k):
T=1;break;
if T==1:
return "\dfrac{"+str(int(x*k))+"}{"+str(k)+"}"
else:
return str(round(x,3))
qlen=11;e=0;
dlen=len(divisor)-1;
ddlen=len(dividend);
dd="~ "
for k in range(0,ddlen):
dividend[k]=dividend[k]/divisor[0]
dd=dd+"& "+roundint(dividend[k])+" "
for k in range(0,qlen-ddlen+1):
dividend.append(0)
dd=dd+"\\\\\n"
for k in range(1,dlen+1):
divisor[k]=-divisor[k]/divisor[0]
q=[]
q.append(dividend[0])
qq="~ & "+roundint(q[0])+" "
s="$\\begin{array}{c|"
s2=[]
for k in range(1,dlen+1):
s2.append(roundint(divisor[k])+" ")
for k in range(0,dlen):
for i in range(0,k+1):
s2[k]=s2[k]+"& ~ "
for i in range(0,qlen-dlen):
t=dividend[i+1]
for k in range(0,dlen):
tt=q[i]*divisor[k+1]
s2[k]=s2[k]+"& "+roundint(tt)+" "
if i-k >= 0:
t=t+q[i-k]*divisor[k+1]
q.append(t)
if t==0:
e=e+1
else:
e=0
if e>=dlen and i>=ddlen-1:
break
qq=qq+"& "+roundint(t)+" "
for i in range(qlen-dlen,qlen-1):
if e>=dlen and i>=ddlen-1:
break
t=dividend[i+1]
for k in range(0,dlen):
if i-k < qlen-dlen:
t=t+q[i-k]*divisor[k+1]
q.append(t)
qq=qq+"& "+roundint(t)+" "
for k in range(0,qlen+1):
s=s+"c"
s=s+"}\n"+dd
for k in range(0,dlen):
s=s+s2[k]+"\\\\\n"
s=s+"\\hline\n"+qq+"\\end{array}$"
print(s)
[/pywindow]
This post has been edited 1 time. Last edited by fungarwai, Feb 9, 2023, 4:57 AM
GCD of 2^n-1 and 2^m+1
by fungarwai, Feb 23, 2022, 1:46 PM
Proof
Proof
If ,
Proof
Proof
Example
Showing gcd(2^m−1,2^n+1)=1 when m is odd
When m is odd, . Therefore
有序數對的個數
Count the number of ordered sets for when
That implies counting the number of ordered sets for
The number of when is
When m is odd, . Therefore
有序數對的個數
Count the number of ordered sets for when
That implies counting the number of ordered sets for
The number of when is
Proof
By LTE,
Proof
By LTE,
This post has been edited 3 times. Last edited by fungarwai, Feb 25, 2022, 12:32 PM
modular arithmetic on 1^1+2^2+3^3+...+n^n
by fungarwai, Dec 13, 2021, 1:45 PM
To find the modular residue ,
the main idea is rewriting as
While is enough small, would be simply zero.
has to be calculated manually. Make it as short as it can.
Here is the main problem.
Proof
(Refer Summation with polynomial)
Note 1
Note 2
Note 3
Proof
Example
Python program for general cases
input values for n, m to get
input values for N, p, s to get for
the main idea is rewriting as
While is enough small, would be simply zero.
has to be calculated manually. Make it as short as it can.
Here is the main problem.
Proof
(Refer Summation with polynomial)
Note 1
Note 2
Note 3
By Kummer's theorem, is equal to the number of carries
when is added to in base p
There are at least number of carries when
Otherwise,
when is added to in base p
There are at least number of carries when
Otherwise,
Proof
Example
Summation
Find the units digit of
program check
program check
A spin off an old USAMTS
Determine the rightmost three digits of the number
program check
program check
(Refer Application of elementary operations in Euclidean algorithm)
Find the units digit of
program check
N = 1010 p = 2 s = 1 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
program check
N = 404 p = 5 s = 1 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
sum=0;n=2021;m=10; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
A spin off an old USAMTS
Determine the rightmost three digits of the number
program check
N = 500 p = 2 s = 3 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
program check
N = 200 p = 5 s = 3 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
(Refer Application of elementary operations in Euclidean algorithm)
sum=0;n=1000;m=1000; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
Python program for general cases
input values for n, m to get
n = int(input("n=")) m = int(input("m=")) sum=0; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
input values for N, p, s to get for
N = int(input("N=")) p = int(input("p=")) s = int(input("s=")) sum=0;m=p**s; for r in range(1,p): for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
This post has been edited 2 times. Last edited by fungarwai, Dec 14, 2021, 12:15 PM
Coincidence on Linear Regression Analysis with president election data
by fungarwai, Feb 16, 2021, 12:58 AM
The Linear Regression model with president election data indicates that a candidate has stolen other candidates averagely 120 votes on each ward in Milwaukee
Here are data sources from Milwaukee
11-3-20 General and Presidential Election - Unofficial Results
My Regression Model is
Candidate's vote = Candidate's voting rate × Total votes
which is no constant term expected
Form data at Nov. 4, 2020
Biden's vote = 5.3191 + 0.5821 × Total votes
R^2=0.9087
Trump's vote = -6.6928 + 0.4002 × Total votes
R^2=0.8255
No constant term is expected.
This constant term is possibly caused by Biden stealing other candidate's vote.
However, the constant term lies on the convincible interval involving 0.
Without constant term, my Linear Regression model at Nov. 4, 2020 becomes:
Biden's vote = 0.5877 × Total votes
R^2=0.9085
Trump's vote = 0.3931 × Total votes
R^2=0.8262
which is Candidate's vote = Candidate's voting rate × Total votes
Guess what?
Form data at Nov. 5, 2020
Biden's vote = 121.6115 + 0.5629 × Total votes
R^2=0.8128
Trump's vote = -120.573 + 0.4171 × Total votes
R^2=0.7051
The constant term lies on the convincible interval far from 0.
My Linear Regression model indicates that Biden has stolen other candidates averagely 120 votes on each ward.
What a Coincidence!
That's all.
Here is my video concerning this Linear Regression Analysis if you're interested.
Possible leakage of this Linear Regression model
Suppose there are two different groups of votes (mail-in ballots and in-person ballots) with different voting rate
holds when
The nature of mail-in ballots and in-person ballots possibly fluctrates the constant term.
Proof
holds when
which implies the nature of independent variable remains unchanged.
Here are data sources from Milwaukee
11-3-20 General and Presidential Election - Unofficial Results
My Regression Model is
Candidate's vote = Candidate's voting rate × Total votes
which is no constant term expected
Form data at Nov. 4, 2020
Biden's vote = 5.3191 + 0.5821 × Total votes
R^2=0.9087
Trump's vote = -6.6928 + 0.4002 × Total votes
R^2=0.8255
No constant term is expected.
This constant term is possibly caused by Biden stealing other candidate's vote.
However, the constant term lies on the convincible interval involving 0.
Without constant term, my Linear Regression model at Nov. 4, 2020 becomes:
Biden's vote = 0.5877 × Total votes
R^2=0.9085
Trump's vote = 0.3931 × Total votes
R^2=0.8262
which is Candidate's vote = Candidate's voting rate × Total votes
Guess what?
Form data at Nov. 5, 2020
Biden's vote = 121.6115 + 0.5629 × Total votes
R^2=0.8128
Trump's vote = -120.573 + 0.4171 × Total votes
R^2=0.7051
The constant term lies on the convincible interval far from 0.
My Linear Regression model indicates that Biden has stolen other candidates averagely 120 votes on each ward.
What a Coincidence!
That's all.
Here is my video concerning this Linear Regression Analysis if you're interested.
Possible leakage of this Linear Regression model
Suppose there are two different groups of votes (mail-in ballots and in-person ballots) with different voting rate
holds when
The nature of mail-in ballots and in-person ballots possibly fluctrates the constant term.
Proof
holds when
which implies the nature of independent variable remains unchanged.
This post has been edited 3 times. Last edited by fungarwai, Feb 18, 2021, 12:40 AM
Subsequent factor of binomial coefficients
by fungarwai, Sep 20, 2020, 11:31 AM
Proof
Proof
Example
Proof
, specially
Proof
Example
This post has been edited 7 times. Last edited by fungarwai, Mar 20, 2021, 12:52 PM
The product of fraction with arithmetic sequence
by fungarwai, Sep 20, 2020, 2:38 AM
An inequality concerning limit of this product
Proof
Example
Concerning the limit
https://artofproblemsolving.com/community/c6h2275801_find_limit
Concerning the limit
https://artofproblemsolving.com/community/u345311h2270603p17759776
An identity of this product
Proof
Example
Summation of this product
Proof
Example
Proof
Example
Concerning the limit
https://artofproblemsolving.com/community/c6h2275801_find_limit
Concerning the limit
https://artofproblemsolving.com/community/u345311h2270603p17759776
An identity of this product
Proof
Example
Wallis product
https://artofproblemsolving.com/community/c4h2565088_prod_limit_n0infty_frac5n25n35n15n4
https://artofproblemsolving.com/community/c4h2565088_prod_limit_n0infty_frac5n25n35n15n4
Summation of this product
Proof
Idea provided by RagvaloD on 2/3*6 + 2*5/3*6*9 + ... + 2*5*...*2015/3*6...*2019
By Hypergeometric function
By Hypergeometric function
Example
This post has been edited 7 times. Last edited by fungarwai, May 19, 2021, 6:07 AM
Summation with polynomial roots
by fungarwai, May 26, 2020, 12:52 PM
Reciprocal type
Credit to the idea posted by ccmmjj in mathchina forum
Proof
Identity of a conditional symmetric polynomial
Let
Proof
Example
Proof
Suppose is true for
Example
Lagrange polynomial type
Proof
Best Proof Credit to the idea with four variables posted by natmath at #2
Proof Credit to the idea with three variables posted by gasgous at #10
Other Proof
where
Proof
Example
Credit to the idea posted by ccmmjj in mathchina forum
Proof
Identity of a conditional symmetric polynomial
Let
Proof
Distribute balls into boxes
Each box has balls
Let be the event of box contains at least one ball
By Inclusion–exclusion principle
satisfies for the number of any combinations of , therefore
Each box has balls
Let be the event of box contains at least one ball
By Inclusion–exclusion principle
satisfies for the number of any combinations of , therefore
Example
For the combination as example
which is the same as the situation of the coefficient of
Other examples
which is the same as the situation of the coefficient of
Other examples
Proof
Suppose is true for
Example
Lagrange polynomial type
Proof
Best Proof Credit to the idea with four variables posted by natmath at #2
Proof Credit to the idea with three variables posted by gasgous at #10
Other Proof
Let
such that
where
The coefficient of should be 0
i.e.
And then,
Let
As
Credit to the proof posted by natmath at #4
such that
where
The coefficient of should be 0
i.e.
And then,
Let
As
Credit to the proof posted by natmath at #4
https://artofproblemsolving.com/community/c4h2901132
Consider the polynomial
The desired expression is the coefficient of of . We know that (and cyclically) so
But is a quadratic so the coefficient of and should be . This means that So
The coefficient of is .
Consider the polynomial
The desired expression is the coefficient of of . We know that (and cyclically) so
But is a quadratic so the coefficient of and should be . This means that So
The coefficient of is .
where
Proof
When ,
When ,
Suppose
When ,
Suppose
Example
This post has been edited 23 times. Last edited by fungarwai, May 19, 2023, 12:07 PM
Chromatic polynomial of a 3×n grid
by fungarwai, Apr 26, 2020, 1:26 AM
Denote Chromatic polynomial of a m×n grid as
Chromatic polynomial of a 2×n grid has been found and named as ladder graph
My recurrence equation found for Chromatic polynomial of a 3×n grid is as follow
Chromatic polynomial of a 2×n grid has been found and named as ladder graph
My recurrence equation found for Chromatic polynomial of a 3×n grid is as follow
This post has been edited 17 times. Last edited by fungarwai, Aug 27, 2021, 12:50 PM
The module distribution for Pascal's triangle row
by fungarwai, Sep 13, 2019, 12:14 PM
Let
For p=2,
There are different ways to choose for
For p=3,
There are different ways to choose for and
different ways to choose for
Proof
Let
There are different ways to choose for
Consider the sum of coefficient of the odd power of generating function
There are different ways to choose for and
different ways to choose for
Multiplying the result
There are different ways to choose for and
different ways to choose for
For p=5,
The number of is
The number of is
The number of is
The number of is
Proof
Consider generating functions
1:
2:
4:
3:
1:
3:
4:
2:
Here define when to maintain the equivalent
1:
4:
Combining the results
The number of is
The number of is
The number of is
The number of is
Example
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
For p=2,
There are different ways to choose for
For p=3,
There are different ways to choose for and
different ways to choose for
Proof
Let
There are different ways to choose for
Consider the sum of coefficient of the odd power of generating function
There are different ways to choose for and
different ways to choose for
Multiplying the result
There are different ways to choose for and
different ways to choose for
For p=5,
The number of is
The number of is
The number of is
The number of is
Proof
Consider generating functions
1:
2:
4:
3:
1:
3:
4:
2:
Here define when to maintain the equivalent
1:
4:
Combining the results
The number of is
The number of is
The number of is
The number of is
Example
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
The number of is
This post has been edited 1 time. Last edited by fungarwai, Sep 13, 2019, 12:15 PM
Notable algebra methods with proofs and examples
fungarwaiArchives
March 2024
February 2022
December 2021
September 2020
May 2020
April 2020
September 2019
January 2019
December 2018
Shouts
Submit
20 shouts
Tags
About Owner
- Posts: 859
- Joined: Mar 11, 2017
Blog Stats
- Blog created: Sep 15, 2018
- Total entries: 18
- Total visits: 5839
- Total comments: 8
Search Blog