Product with polynomial roots

by fungarwai, Mar 18, 2024, 11:35 AM

Vandermonde polynomial type

$\displaystyle \prod_{1\le i<j\le m} (x_j-x_i)^2
=(-1)^{\binom{m}{2}}\prod_{j=1}^m f'(x_j),
~f(x)=\prod_{i=1}^m (x-x_i)$

Proof

Example

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 $f(x)$
by dividing $f’(x)$ with $f(x)$

$f(x)=x^2+2x-3=0$ has two real roots $x_1=-3,~x_2=1$
$f’(x)=2x+2$

$\begin{array}{c|cccccccccccc}
~ & 2 & 2 \\
-2 & ~ & -4 & 4 & -20 & 52 & -164 & 484 & -1460 & 4372 & -13124 \\
3 & ~ & ~ & 6 & -6 & 30 & -78 & 246 & -726 & 2190 & -6558 & 19686 \\
\hline
~ & 2 & -2 & 10 & -26 & 82 & -242 & 730 & -2186 & 6562 & -19682 & 19686 \end{array}$

The coefficients of the quotient show that
$\displaystyle \sum_{k=1}^2 x_k^0=2,~\sum_{k=1}^2 x_k^1=-2,~\sum_{k=1}^2 x_k^2=10,~\sum_{k=1}^2 x_k^3=-26,\dots$

This result is caused by the formula $\dfrac{f'(x)}{f(x)}=\sum_{k=0}^\infty \dfrac{1}{x^{k+1}}\left(\sum_{j=1}^n x_j^k\right)$

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

  1. dividend=[27,-18,0];#input by user, 27x^2-18x for example
  2. divisor=[9,-9,0,1];#input by user, 9x^3-9x^2+1 for example
  3.  
  4. def roundint(x):
  5. if x == int(x):
  6. return str(int(x))
  7. else:
  8. for k in range(1,100):
  9. T=0
  10. if x*k == int(x*k):
  11. T=1;break;
  12. if T==1:
  13. return "\dfrac{"+str(int(x*k))+"}{"+str(k)+"}"
  14. else:
  15. return str(round(x,3))
  16. qlen=11;e=0;
  17. dlen=len(divisor)-1;
  18. ddlen=len(dividend);
  19. dd="~ "
  20. for k in range(0,ddlen):
  21. dividend[k]=dividend[k]/divisor[0]
  22. dd=dd+"& "+roundint(dividend[k])+" "
  23. for k in range(0,qlen-ddlen+1):
  24. dividend.append(0)
  25. dd=dd+"\\\\\n"
  26. for k in range(1,dlen+1):
  27. divisor[k]=-divisor[k]/divisor[0]
  28. q=[]
  29. q.append(dividend[0])
  30. qq="~ & "+roundint(q[0])+" "
  31. s="$\\begin{array}{c|"
  32. s2=[]
  33. for k in range(1,dlen+1):
  34. s2.append(roundint(divisor[k])+" ")
  35. for k in range(0,dlen):
  36. for i in range(0,k+1):
  37. s2[k]=s2[k]+"& ~ "
  38. for i in range(0,qlen-dlen):
  39. t=dividend[i+1]
  40. for k in range(0,dlen):
  41. tt=q[i]*divisor[k+1]
  42. s2[k]=s2[k]+"& "+roundint(tt)+" "
  43. if i-k >= 0:
  44. t=t+q[i-k]*divisor[k+1]
  45. q.append(t)
  46. if t==0:
  47. e=e+1
  48. else:
  49. e=0
  50. if e>=dlen and i>=ddlen-1:
  51. break
  52. qq=qq+"& "+roundint(t)+" "
  53. for i in range(qlen-dlen,qlen-1):
  54. if e>=dlen and i>=ddlen-1:
  55. break
  56. t=dividend[i+1]
  57. for k in range(0,dlen):
  58. if i-k < qlen-dlen:
  59. t=t+q[i-k]*divisor[k+1]
  60. q.append(t)
  61. qq=qq+"& "+roundint(t)+" "
  62. for k in range(0,qlen+1):
  63. s=s+"c"
  64. s=s+"}\n"+dd
  65. for k in range(0,dlen):
  66. s=s+s2[k]+"\\\\\n"
  67. s=s+"\\hline\n"+qq+"\\end{array}$"
  68. print(s)


pywindow code
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

$(x^n-1,x^m-1)=x^{(n,m)}-1$
Proof

$(n,p^k m)=\begin{cases}
(n,m) & \nu_p(n)\le \nu_p(m)\\
p^k(n,m) & \nu_p(n)\ge \nu_p(m)+k
\end{cases}$
Proof

If $(m_1,m_2)=p^k$,
$\quad(n,m_1 m_2)=\begin{cases}
p^{-\nu_p(n)}(n,m_1)(n,m_2) & \nu_p(n)\le\nu_p(m_1),~\nu_p(n)\le\nu_p(m_2)\\
(n,m_1)(n,m_2) & \nu_p(n)\ge \nu_p(m_1)+\nu_p(m_2)
\end{cases}$
Proof

$(2^n-1,2^m+1)=\begin{cases}
1 & \nu_2(n)\le \nu_2(m)\\
2^{(n,m)}+1 & \nu_2(n)\ge \nu_2(m)+1
\end{cases}$
Proof
Example

$(3^n-1,3^m+1)=\begin{cases}
2 & \nu_2(n)\le \nu_2(m)\\
3^{(n,m)}+1 & \nu_2(n)\ge \nu_2(m)+1\end{cases}$
Proof

$(x^n-1,x^m+1)=\begin{cases}(x-1,2) & \nu_2(n)\le \nu_2(m)\\
x^{(n,m)}+1 & \nu_2(n)\ge \nu_2(m)+1\end{cases}$
Proof
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 $1^1+2^2+3^3+\dots+n^n \pmod{p^s}$,

the main idea is rewriting $1^1+2^2+3^3+\dots+n^n$ as
$1^1+2^2+\dots+(p-1)^{p-1}+p^p$
$+(p+1)^1+(p+2)^2+\dots+(2p-1)^{2p-1}+(2p)^{2p}+\dots$
$=\sum_{r=1}^{p-1}\sum_{k=1}^N (pk-p+r)^{pk-p+r}+\sum_{k=1}^N (pk)^{pk}+\sum_{k=N+1}^n k^k$

While $s$ is enough small, $\sum_{k=1}^N (pk)^{pk}\pmod{p^s}$ would be simply zero.

$\sum_{k=N+1}^n k^k$ has to be calculated manually. Make it as short as it can.

Here $\sum_{r=1}^{p-1}\sum_{k=1}^N (pk-p+r)^{pk-p+r}\pmod{p^s}$ is the main problem.

$p^{s-1}\mid N\implies \sum_{k=1}^N (pk-p+1)^{pk-p+1}
\equiv (1-\frac{p}{2})N\equiv 
\begin{cases} 0 \pmod{p^s} & p=2\\
N\pmod{p^s} & p\neq 2\end{cases}$

Proof

$\varphi(p^s)=p^{s-1}(p-1)\mid N \Rightarrow \sum_{k=1}^N (pk-p+r)^{pk-p+r}
\equiv 0 \pmod{p^s} (2\le r\le p-1)$

Proof

Example

Python program for general cases

input values for n, m to get $\sum_{k=1}^n k^k\pmod{m}$

  1. n = int(input("n="))
  2. m = int(input("m="))
  3. sum=0;
  4. for k in range(1,n+1):
  5. p=1
  6. for t in range(1,k+1):
  7. p=(p*k) % m
  8. sum=(sum+p) % m
  9. print(sum)


input values for N, p, s to get $\sum_{k=1}^N (pk-p+r)^{pk-p+r}\pmod{p^s}$ for $1\le r\le p-1$

  1. N = int(input("N="))
  2. p = int(input("p="))
  3. s = int(input("s="))
  4. sum=0;m=p**s;
  5. for r in range(1,p):
  6. for k in range(1,N+1):
  7. P=1
  8. for t in range(1,p*(k-1)+r+1):
  9. P=(P*(p*(k-1)+r)) % m
  10. sum=(sum+P) % m
  11. 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
$\begin{cases}y_A=\hat{\beta_A} x_A,~\hat{\alpha_A}=\bar{y_A}-\bar{x_A}\hat{\beta_A}=0\\
y_B=\hat{\beta_B} x_B,~\hat{\alpha_B}=\bar{y_B}-\bar{x_B}\hat{\beta_B}=0\end{cases}$
$\hat{\alpha}=\frac{p_A p_B \bar{x_A}\bar{x_B}(\hat{\beta_B}-\hat{\beta_A})}
{p_A D(x_A)+p_B D(x_B)}
(\bar{x_A}-\bar{x_B}+\frac{D(x_A)}{\bar{x_A}}-\frac{D(x_B)}{\bar{x_B}})$
$\hat{\alpha}=y-x\hat{\beta}=0$ holds when $E(x_A)=E(x_B)~\text{and}~D(x_A)=D(x_B)$
The nature of mail-in ballots and in-person ballots possibly fluctrates the constant term.

Proof
Attachments:
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

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

Summation with polynomial roots

by fungarwai, May 26, 2020, 12:52 PM

Reciprocal type

$\sum_{i=1}^m \frac{1}{x-x_i}=\frac{f'(x)}{f(x)},~f(x)=\prod_{i=1}^m (x-x_i)$

Credit to the idea posted by ccmmjj in mathchina forum

Proof

$\sum_{i=1}^m \frac{-1}{(x-x_i)^2}=\frac{f''(x)f(x)-[f'(x)]^2}{[f(x)]^2}$

$\sum_{i=1}^m \frac{2}{(x-x_i)^3}=\frac{f'''(x)[f(x)]^2-3f''(x)f'(x)f(x)+2[f'(x)]^3}{[f(x)]^3}$

Identity of a conditional symmetric polynomial

Let $\displaystyle S_{n,m}=\sum_{r_1+r_2+\cdots+r_m=n} x_1^{r_1}x_2^{r_2}\cdots x_m^{r_m},~\sigma_{k,m} =\sum_{1\le j_1 < j_2 < \cdots < j_k \le m} x_{j_1} \dots x_{j_k}$
$\displaystyle \boxed{S_{j,m}=\sum_{k=1}^{m-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{m-1}\sigma_{m,m} S_{j-m,m}}$
$\displaystyle \text{or}~ \boxed{S_{j,m}=\sum_{k=1}^{j-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{j-1}\sigma_{j,m}}$

Proof

Example

$\displaystyle S_{j,K}=\sum_{k=1}^{M-1} (-1)^{k-1}
\sigma_{k,M} S_{j-k,K}+(-1)^{M-1}\sigma_{M,M}S_{j-M,K},~\forall K\le M\le m$

Proof

Example

Lagrange polynomial type

$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}
=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\end{cases}$

Proof

$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}
=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\\
\displaystyle
\boxed{\sum_{r_1+r_2+\cdots+r_m=n-m+1} x_1^{r_1}x_2^{r_2}\cdots x_m^{r_m}}
 & n\ge m
\end{cases}$

$S_{m,m}=\sum a$
$S_{m+1,m}=\sum a^2+\sum ab$
$S_{m+2,m}=\sum a^3+\sum a^2 b+\sum abc$
$S_{m+3,m}=\sum a^4+\sum a^3 b+\sum a^2 b^2+\sum a^2 bc+\sum abcd$

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

$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\\
\displaystyle
\boxed{\sum_{r_1 + 2r_2 + \cdots + mr_m = s \atop r_1\ge 0, \ldots, r_m\ge 0} (-1)^n \frac{(r_1 + r_2 + \cdots + r_m)!}{r_1!r_2! \cdots r_m!} \prod_{i=1}^m (-\sigma_{i,m})^{r_i}} & n=s+m-1\ge m
\end{cases}$

where $\sigma_{k,m} =\sigma_k (x_1 , \ldots , x_m )=\sum_{1\le  j_1 < j_2 < \cdots < j_k \le m} x_{j_1} \dots x_{j_k}$

$S_{m,m}=\sigma_{1,m}$
$S_{m+1,m}=\sigma_{1,m}^2-\sigma_{2,m}$
$S_{m+2,m}=\sigma_{1,m}^3-2\sigma_{1,m}\sigma_{2,m}+\sigma_{3,m}$
$S_{m+3,m}=\sigma_{1,m}^4-3\sigma_{1,m}^2\sigma_{2,m}+\sigma_{2,m}^2-2\sigma_{1,m}\sigma_{3,m}+\sigma_{4,m}$

Proof

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 $P(G_{m,n},t)$

Chromatic polynomial of a 2×n grid has been found and named as ladder graph

$P(G_{2,n},t)=t(t-1)(t^2-3t+3)^{n-1}$

My recurrence equation found for Chromatic polynomial of a 3×n grid is as follow

$P(G_{3,n},t)=(t^3-5t^2+11t-10)P(G_{3,n-1},t)-(t^4-7t^3+19t^2-24t+11)P(G_{3,n-2},t)$
$~=(t-2)(t^2-3t+5)P(G_{3,n-1},t)-(t-1)(t^3-6t^2+13t-11)P(G_{3,n-2},t)$

$P(G_{3,1},t)=t(t-1)^2,~P(G_{3,2},t)=t(t-1)(t^2-3t+3)^2$
$P(G_{3,3},t)=(t^3-5t^2+11t-10)t(t-1)(t^2-3t+3)^2
-(t^4-7t^3+19t^2-24t+11)t(t-1)^2$
$~=t(t-1)(t^7-11t^6+55t^5-161t^4+298t^3-350t^2+244t-79)$

[asy]
unitsize(5mm);
int i, j, k;
k=0;
for(i=0; i<k+7; i=i+1){
if(i!=2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((0,j)--(k+6,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+7; i=i+1){
if(i!=10){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((k,j)--(k+5,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
dot((k+6,0.5));dot((k+6,1.5));
draw((k+5,0)--(k+6,0.5));
draw((k+5,1)--(k+6,0.5));
draw((k+5,1)--(k+6,1.5));
draw((k+5,2)--(k+6,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
draw((k+6,1)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,1));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (23,1));
k=24;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (31,1));
k=32;
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((k,j)--(k+5,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
dot((k+6,0.5));dot((k+6,1.5));
draw((k+5,0)--(k+6,0.5));
draw((k+5,1)--(k+6,0.5));
draw((k+5,1)--(k+6,1.5));
draw((k+5,2)--(k+6,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=[(t-1)^3-(t-2)^2]$", (17,1));
k=22;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (28,1));
k=29;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=(t^3-4t^2+7t-5)$", (17,1));
k=22;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (28,1));
k=29;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy][asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,2)--(k+6,0));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy][asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-7,1));label("$=$", (7,1));
k=8;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,0));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (23,1));
k=24;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-14,1));label("$=[(t-1)^2-(t-1)]$", (3,1));
k=8;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (15,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-11,1));label("$=(t-1)(t-2)$", (3,1));
k=7;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$+$", (14,1));
k=15;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
k=0;
for(i=0; i<k+7; i=i+1){
if(i!=2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
draw((0,j)--(k+6,j));
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=[(t-1)^3-(t-2)^2]$", (11,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (22,1));
k=23;
draw((k,0)--(k+6,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+6,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
draw((k+6,0)--(k+6,2));dot((k+6,0));dot((k+6,2));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-10,1));label("$=[(t-1)^3-(t-2)^2-(t-1)^2+(t-1)]$", (11,1));
k=20;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (26,1));
k=27;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (0,1));label("$=(t^3-5t^2+10t-7)$", (11,1));
k=16;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (22,1));
k=23;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
draw((k+5,0)..(k+6,1)..(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+5,0));
draw((k,1)--(k+5,1));
draw((k,2)--(k+5,2));
for(i=k; i<k+6; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+4,0));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));
draw((k+4,2)--(k+6,1));
draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
k=0;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$=$", (7,1));
k=8;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;
draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+6,1));
draw((k,2)--(k+4,2));draw((k+4,2)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,1));
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);int i, j, k;
label("$=$", (7,1));
k=8;draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k+4,2)--(k+5,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+6,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (23,1));
k=24;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,2)--(k+6,1));draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$+$", (31,1));
k=32;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);int i, j, k;
label("$=$", (7,1));
k=8;draw((k,0)--(k+4,0));draw((k+4,0)--(k+6,1));
draw((k,1)--(k+4,1));draw((k+5,1)--(k+6,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
dot((k+5,1));dot((k+6,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$-$", (15,1));
k=16;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k+4,2)--(k+5,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+6,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}dot((k+5,1));
label("...", (k+2,0.5));label("...", (k+2,1.5));label("$-$", (23,1));
k=24;draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,0)--(k+6,1));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){if(i!=k+2){dot((i,j));}}}
dot((k+6,1));label("...", (k+2,0.5));label("...", (k+2,1.5));label("$+$", (31,1));
k=32;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
label("$+$", (39,1));
k=40;draw((k,0)--(k+4,0));draw((k,1)--(k+4,1));draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));label("...", (k+2,1.5));
[/asy]


[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-14,1));label("$=[(t-1)^2-(t-1)+1]$", (3,1));
k=8;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-(t-2)$", (14,1));
k=16;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
[asy]
unitsize(5mm);
int i, j, k;
label("$~$", (-10,1));label("$=(t^2-3t+3)$", (3,1));
k=6;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
label("$-(t-2)$", (12,1));
k=14;
draw((k,0)--(k+4,0));
draw((k,1)--(k+4,1));
draw((k,2)--(k+4,2));
draw((k+4,0)..(k+5,1)..(k+4,2));
for(i=k; i<k+5; i=i+1){
if(i!=k+2){draw((i,0)--(i,2));}
for(j=0; j<3; j=j+1){
if(i!=k+2){dot((i,j));}}}
label("...", (k+2,0.5));
label("...", (k+2,1.5));
[/asy]
$a_n=(t^3-5t^2+10t-7)a_{n-1}-b_{n-1}$
$b_n=a_n-(t^2-3t+3)a_{n-1}+(t-2)b_{n-1}$

$b_{n-1}=(t^3-5t^2+10t-7)a_{n-1}-a_n$
$b_n=(t^3-5t^2+10t-7)a_n-a_{n+1}$
$(t^3-5t^2+10t-7)a_n-a_{n+1}=a_n-(t^2-3t+3)a_{n-1}+(t-2)[(t^3-5t^2+10t-7)a_{n-1}-a_n]$
$a_{n+1}=(t^3-5t^2+11t-10)a_n-(t^4-7t^3+19t^2-24t+11)a_{n-1}$

[asy]
unitsize(5mm);int i, j, k;
label("$a_1:$", (0,1));
k=2;
for(i=k; i<k+1; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){dot((i,j));}}
label("$a_2:$", (5,1));
k=7;
for(i=k; i<k+2; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){
draw((k,j)--(k+1,j));
dot((i,j));}}
label("$a_3:$", (11,1));
k=13;
for(i=k; i<k+3; i=i+1){
draw((i,0)--(i,2));
for(j=0; j<3; j=j+1){
draw((k,j)--(k+2,j));
dot((i,j));}}
[/asy]

$a_1=t(t-1)^2,~a_2=t(t-1)(t^2-3t+3)^2$
$a_3=(t^3-5t^2+11t-10)t(t-1)(t^2-3t+3)^2-(t^4-7t^3+19t^2-24t+11)t(t-1)^2$
$~=t(t-1)(t^7+11t^6+55t^5-161t^4+298t^3-350t^2+244t-79)$
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 $n=\sum_{k=0}^\infty n_k p^k, N_r=\{k|n_k=r\}$

For p=2,

There are $2^{|N_1|}$ different ways to choose $m$ for $\binom{n}{m}\equiv 1\pmod{2}$

For p=3,

There are $2^{|N_1|}\cdot \frac{3^{|N_2|}-1}{2}$ different ways to choose $m$ for $\binom{n}{m}\equiv 2\pmod{3}$ and
$2^{|N_1|}\cdot \frac{3^{|N_2|}+1}{2}$ different ways to choose $m$ for $\binom{n}{m}\equiv 1\pmod{3}$

Proof

For p=5,

The number of $\binom{n}{m}\equiv 1\pmod{5}$ is $
\frac{1}{4}2^{|N_1|}5^{|N_4|}(3^{|N_2|}4^{|N_3|}+0^{|N_3|})
+\frac{1}{2}2^{|N_1|}5^{\frac{|N_2|}{2}}2^{\frac{3|N_3|}{2}}
\cos\left(|N_2|\tan^{-1}\frac{1}{2}-|N_3|\frac{\pi}{4}\right)$
The number of $\binom{n}{m}\equiv 2\pmod{5}$ is $
\frac{1}{4}2^{|N_1|}5^{|N_4|}(3^{|N_2|}4^{|N_3|}-0^{|N_3|})
+\frac{1}{2}2^{|N_1|}5^{\frac{|N_2|}{2}}2^{\frac{3|N_3|}{2}}
\sin\left(|N_2|\tan^{-1}\frac{1}{2}-|N_3|\frac{\pi}{4}\right)$
The number of $\binom{n}{m}\equiv 3\pmod{5}$ is $
\frac{1}{4}2^{|N_1|}5^{|N_4|}(3^{|N_2|}4^{|N_3|}-0^{|N_3|})
-\frac{1}{2}2^{|N_1|}5^{\frac{|N_2|}{2}}2^{\frac{3|N_3|}{2}}
\sin\left(|N_2|\tan^{-1}\frac{1}{2}-|N_3|\frac{\pi}{4}\right)$
The number of $\binom{n}{m}\equiv 4\pmod{5}$ is $
\frac{1}{4}2^{|N_1|}5^{|N_4|}(3^{|N_2|}4^{|N_3|}+0^{|N_3|})
-\frac{1}{2}2^{|N_1|}5^{\frac{|N_2|}{2}}2^{\frac{3|N_3|}{2}}
\cos\left(|N_2|\tan^{-1}\frac{1}{2}-|N_3|\frac{\pi}{4}\right)$

Proof

Example
This post has been edited 1 time. Last edited by fungarwai, Sep 13, 2019, 12:15 PM

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
Submit
  • Nice blog!

    by Inconsistent, Mar 18, 2024, 2:41 PM

  • hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe! :)

    by thedodecagon, Jan 22, 2022, 1:33 AM

  • thanks for this

    by jasperE3, Dec 3, 2021, 10:01 PM

  • I am working as accountant and studying as ACCA student now.
    I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..

    by fungarwai, Aug 28, 2021, 4:54 AM

  • Awesome algebra blog :)

    by Euler1728, Mar 22, 2021, 5:37 AM

  • I wonder if accountants need that kind of math tho

    by Hamroldt, Jan 14, 2021, 10:55 AM

  • Nice!!!!

    by Delta0001, Dec 12, 2020, 10:20 AM

  • this is very interesting i really appericate it :)

    by vsamc, Oct 29, 2020, 4:42 PM

  • this is god level

    by Hamroldt, Sep 4, 2020, 7:48 AM

  • Super Blog! You are Pr0! :)

    by Functional_equation, Aug 23, 2020, 7:43 AM

  • Great blog!

    by freeman66, May 31, 2020, 5:40 AM

  • cool thx! :D

    by erincutin, May 18, 2020, 4:55 PM

  • How so op???

    by Williamgolly, Apr 30, 2020, 2:42 PM

  • Beautiful

    by Al3jandro0000, Apr 25, 2020, 3:11 AM

  • Nice method :)

    by Feridimo, Jan 23, 2020, 5:05 PM

  • This is nice!

    by mufree, May 26, 2019, 6:40 AM

  • Wow! So much Algebra.

    by AnArtist, Mar 15, 2019, 1:19 PM

  • :omighty: :omighty:

    by AlastorMoody, Feb 9, 2019, 5:17 PM

  • 31415926535897932384626433832795

    by lkarhat, Dec 25, 2018, 11:53 PM

  • rip 0 shouts and 0 comments until now

    by harry1234, Nov 17, 2018, 8:56 PM

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
a