Problems & Puzzles: Conjectures
Conjecture 95. Pascal triangle (2,1), two Conjectures
On Jan 14, 2023, Davide Rotondo sent these nice Conjectures:Consider the 2,1 Pascal triangle ( http://oeis.org/wiki/(2,1)-
Pascal_triangle)12. 1.2. 3. 1.2. 5. 4. 1.2. 7. 9. 5. 1.2. 9. 16. 14. 6. 1.2. 11. 25. 30. 20. 7. 1.2. 13. 36. 55. 50. 27. 8. 1...First conjecture.
If the second coefficient starting from the right of a row is a prime number, then also the other coefficients in the same row will be divisible by the second coefficient. To do this, the coefficients must be properly corrected as follows:
3rd coefficient +1
4th coefficient -2
5th coefficient +3
6th coefficient -4
where +1,-2,+3,-4, ... are the natural numbers with alternating signs.
the coefficients in the fifth row haveIf the second coefficient from the right is prime, then also the other coefficients taken diagonally to find the Lucas numbers excluding 1 are divisible by the second coefficient.
2. 7. 9. 5. 1.
(9+1)/5 = 2
(7-2)/5 = 1
(2+3)/5 = 1
5 is a prime number
Second conjectureFor example in the seventh row we have 7 as the second coefficient and on its diagonal 1. 7. 14. 7. that are all divisible by 7.
7 is a prime numberQ1. prove that the two conjectures are true or false.
During the week 21-27 Jan 2923, contributions from Mauro Fiorentini, Jan van Delden, Emmanuel Vantieghem,Giorgos Kalogeropoulos
Both conjectures are true.
The k-th term of row n is the absolute values of the (n – k)-th
coefficient of the Dickson polynomials of first kind (
ticle/1279) D2n – k – 1(α, x) and the
next to last number of row n (numbering from 1) is n.
The k-th coefficient of Dn(α, x) is n / (n – k) * C(n – k, k), thus the
k-th term of row n is P(n, k) = (2n – k – 1) / (n – 1) * (n – 1)! / ((n
– k)! * (k – 1)!) ≡ –(k + 1) * (n – 2)! / ((n – k)! * (k – 1)!) mod n.
Now if n is prime, from wilson's theorem (n – 2)! ≡ 1 mod n and ((n –
k)! * (k – 1)!) ≡ (–1)^k mod n, so P(n, k) ≡ (–1)^(k + 1) * (k + 1) mod
The diagonals are the absolute values of the coefficients of a single
Dickson polynomials of first kind.
For example D7(α, x) = x7 – 7αx5 + 14α2x3 – 7α3x.
They are D(n, k) = n / (n – k) * C(n – k, k); as C(n – k, k) is an
integer, if n is prime, all of them, except the first one, are
multiples of n so all numbers of the diagonal, except 1, are multiples
My contribution in the form of a pdf, this way the typesetting is nicer, I think.
Emmanuel wrote:First of all, let us denote the rows of the triangle by
T(0), T(1), T(2), ...and let the elements of the row T(n) be denoted asT(n,0), T(n,1), T(n,2), ..., T(n,n).Proof of conjecture 1 :
We know (following the given link) that T(n) is the coefficient list of the polynomial
(2 + x)(1 + x)^(n-1) = (1 + (1 + x))(1 + x)^(n-1) = (1 + x)^(n-1) + (1 + x)^n
(the powers of x must being in ascending order).
Thus,we have :
T(n,k) = B(n-1,k) + B(n,k) (*)
where B(m,u) is the binomial coefficient m(m-1)...(m-i+1) / u! ( and 0 when u > m).
Let p, the second element of T(p-1) counted from the right be an odd prime.
For k = 1 to p - 2 we then have
B(p - 2, k) = (p - 2)(p - 3) ...(p - k - 1) / k! === (-2)(-3)...(-k-1) / k! === (k+1)*(-1)^k (mod p)
B(p - 1, k) = (p - 1)(p - 2) ...(p - k) / k! === (-1)(-2)...(-k) / k! === (-1)^k (mod p).
T(p - 1,k) === (k + 2)*(-1)^k (mod p). (*)
Since T(p - 1,0) = 2, this congruence holds for k = 0, 1, ..., p - 1.
To make this result match with the formulation of the conjecture we sometimes must replace (*) by
T(p - 1,k) === +or -p + (k + 2)*(-1)^k (mod p), for k = 0 to p - 1,
which is precisely the formulation of the conjecture 1.
Proof of conjecture 2 :
For n > k >= 1 we have :
T(n,k) = [(n-1)(n-2)...(n-k) + n(n-1)...(n-k+1)] / k! = (n-1)(n-2)...(n-k)*[n - k +n] / k!.
If we take k and n such that 2n - k = p, an odd prime, then T(n,k) will be divisible by p.
The smallest n for which this is the case is (p + 1) / 2 = u. The next cases are then T(u+1, 3), T(u+2, 5), ..., T(p-1, p-2) = p.
These are precisely the elements on the "diagonal" as formulated in conjecture 2.
The first conjecture is true.
For binomial(n,k) we will use the notation b(n,k).We can express our starting triangle in the form:
T(n,k) = b(n, k+1) - b(n-2, k-1) for n>1 and -1<= k <= p-2
If we adjust the coefficients with +1,-2,+3,-4,+5... then we get
T(n,k) = b(n, k+1) - b(n-2, k-1) + (-1)^(k+1)*k for n>1 and -1<= k <= p-2.
We want b(n, k+1) - b(n-2, k-1) + (-1)^(k+1)*k ≡ 0 mod n for any n prime.
If p is prime we know that b(p,k) ≡ 0 mod p for 0<k<p
So, in our case b(n, k+1) ≡ 0 mod n if n is prime for -1<k<p-1.
Now, we have to show that - b(n-2, k-1) + (-1)^(k+1)*k ≡ 0 mod n for any n prime.
Let's assume that it is true
b(n-2, k-1) ≡ (-1)^(k+1)*k mod n for any n prime.
(n-2)! / ((n-1-k)! (k-1)!) ≡ (-1)^(k+1)*k mod n for any n prime.
(n-2)! / ((n-1-k)! (k-1)! * k) ≡ (-1)^(k+1) mod n for any n prime because gcd(k,n)=1
(n-2)! / ((n-1-k)! k!) ≡ (-1)^(k+1) mod n for any n prime
(n-1)*(n-2)! / ((n-1-k)! k!) ≡ (n-1) (-1)^(k+1) mod n for any n prime
b(n-1, k) ≡ (n-1) (-1)^(k+1) mod n for any n prime
We know from Lucas that b(p-1, k) ≡ (-1)^k mod p for p prime and 0<k<p-1
So, (-1)^k ≡ (n-1) (-1)^(k+1) mod n for any n prime
1 ≡ - (n - 1) mod n for any n prime
n ≡ 0 mod n for any n prime
which is true.
Records | Conjectures | Problems | Puzzles