A mod 2 binomial identity
up vote
2
down vote
favorite
I would like to show the following identity: for all $n, q geq 0$,
$$sum_k binom{2k}{4k-2n} binom{n+3q}{2k+2q+1} equiv binom{n+3q}{2q-1} pmod{2}.$$
This has been computer-tested for all $n, q leq 100$.
Remarks:
- My convention is that the binomial coefficient $binom{m}{n}$ is nonzero only if $m geq n geq 0$.
- If it helps, in terms of generating functions, the sum on the left hand side is $$[x^n y^{2q-1}] , frac{(1+y)^{n+3q}}{x+x^2+y^2}.$$ Of course, the right hand side is equal to $[y^{2q-1}] , (1+y)^{n+3q}$.
- The identity is not true without modulo $2$.
combinatorics summation modular-arithmetic binomial-coefficients
add a comment |
up vote
2
down vote
favorite
I would like to show the following identity: for all $n, q geq 0$,
$$sum_k binom{2k}{4k-2n} binom{n+3q}{2k+2q+1} equiv binom{n+3q}{2q-1} pmod{2}.$$
This has been computer-tested for all $n, q leq 100$.
Remarks:
- My convention is that the binomial coefficient $binom{m}{n}$ is nonzero only if $m geq n geq 0$.
- If it helps, in terms of generating functions, the sum on the left hand side is $$[x^n y^{2q-1}] , frac{(1+y)^{n+3q}}{x+x^2+y^2}.$$ Of course, the right hand side is equal to $[y^{2q-1}] , (1+y)^{n+3q}$.
- The identity is not true without modulo $2$.
combinatorics summation modular-arithmetic binomial-coefficients
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I would like to show the following identity: for all $n, q geq 0$,
$$sum_k binom{2k}{4k-2n} binom{n+3q}{2k+2q+1} equiv binom{n+3q}{2q-1} pmod{2}.$$
This has been computer-tested for all $n, q leq 100$.
Remarks:
- My convention is that the binomial coefficient $binom{m}{n}$ is nonzero only if $m geq n geq 0$.
- If it helps, in terms of generating functions, the sum on the left hand side is $$[x^n y^{2q-1}] , frac{(1+y)^{n+3q}}{x+x^2+y^2}.$$ Of course, the right hand side is equal to $[y^{2q-1}] , (1+y)^{n+3q}$.
- The identity is not true without modulo $2$.
combinatorics summation modular-arithmetic binomial-coefficients
I would like to show the following identity: for all $n, q geq 0$,
$$sum_k binom{2k}{4k-2n} binom{n+3q}{2k+2q+1} equiv binom{n+3q}{2q-1} pmod{2}.$$
This has been computer-tested for all $n, q leq 100$.
Remarks:
- My convention is that the binomial coefficient $binom{m}{n}$ is nonzero only if $m geq n geq 0$.
- If it helps, in terms of generating functions, the sum on the left hand side is $$[x^n y^{2q-1}] , frac{(1+y)^{n+3q}}{x+x^2+y^2}.$$ Of course, the right hand side is equal to $[y^{2q-1}] , (1+y)^{n+3q}$.
- The identity is not true without modulo $2$.
combinatorics summation modular-arithmetic binomial-coefficients
combinatorics summation modular-arithmetic binomial-coefficients
asked Nov 17 at 18:31
JHF
4,3211024
4,3211024
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
Here is a tentative proof:
We first notice that by Kummer theorem $binom{2n}{2m} equiv binom{n}{m} bmod 2$, so that it suffices to show that $$ S_q(n) equiv T_q(n) pmod 2$$ where
begin{align*}
S_q(n):=&sum_k binom{k}{n-k}binom{n+3q}{2k+2q+1}\
T_q(n):=&binom{n+3q}{2q-1}.
end{align*}
From here, the symbol $sim$ means has the same parity as.
We have
$binom{a+1}{b+1}sim binom{a}{b+1}+binom{a}{b}$ but also $binom{a+2}{b+2}sim binom{a+2}{b}+binom{a}{b}$.
We have
begin{align*} T_q(n+2)&sim binom{n+3q+2}{2q-1} sim binom{n+3q}{2q-1}+binom{n+3q}{2q-3}\
&sim T_q(n) +binom{n+3+3(q-1)}{2(q-1)-1} \
&sim T_q(n) +T_{q-1}(n+3) \
T_q(n+3)&sim T_{q+1}(n+2)+ T_{q+1}(n)
end{align*}
On the other hand, we have
begin{align*}S_q(n+3)& sim sum_k binom{k}{n+3-k}binom{n+3q+3}{2k+2q+1}\
&sim sum_k binom{k}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2(k-1)+2q+3}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
& sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\
&+sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim S_{q+1}(n+2) +sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2k+2(q+1)-1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2) \&+sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n-(k-1)}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
S_q(n+3)&sim S_{q+1}(n+2)+ S_{q+1}(n)
end{align*}
So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) sim T_q(n)$, it suffices to show that $ S_q(0) sim T_q(0)$, $ S_q(1) sim T_q(1)$ and $ S_q(2) sim T_q(2)$.
$S_q(0)-T_q(0)$ is clearly an even integer since
$$S_q(0)-T_q(0)= binom{3q}{q+1}-binom{3q}{q-1}=2 binom{3q+1}{q-1}.$$
We have $T_q(1)-S_q(1)= binom{3q+1}{q+2}-binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2frac{5q+7}{3q+3}binom{3q+3}{q-1}$$ which is an even integer since begin{align*}binom{3q+3}{q-1}(5q+7) &equiv binom{3q+3}{q-1}(2q+4)pmod {3q+3}\
&equiv-binom{3q+3}{q-1}(q-1)pmod {3q+3}\
&equiv-binom{3q+2}{q-2}(3q+3)pmod {3q+3}\
&equiv 0pmod {3q+3}end{align*}
Also, after some calculation, it can be shown that
begin{align*}
T_q(2)-S_q(2) &= binom{3q+2}{q+3}-binom{3q+2}{q-1}-binom{3q+2}{q-3}\
&= 2 binom{3q+5}{q-1} frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}.
end{align*}
Then, to complete the proof, we need to show that
$$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3)equiv 0 pmod {(3q+5)(3q+4)(3q+3)}.$$
We have $$ (54+301q+258q^2+59q^3) equiv (q-1)(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then $$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3) equiv (3q+5)binom{3q+4}{q-2}(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then it suffices to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {(3q+4)(3q+3)}.$$
But $3q+4$ and $3q+3$ are coprime, so we need to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+4}$$
and
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+3}.$$
That is
$$ binom{3q+4}{q-2}(14-q^2)equiv 0 pmod {3q+4} tag1$$
and
$$ binom{3q+4}{q-2}(24-q-q^2)equiv 0 pmod {3q+3}.tag2$$
(1) is equivalent to
begin{align*} frac{3q+4}{q-2}binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {3q+4} \
binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {q-2}\
10binom{3q+3}{q-3}&equiv 0 pmod {q-2}\
10frac{q-2}{3q+4}binom{3q+4}{q-2}&equiv 0 pmod {q-2}\
10binom{3q+4}{q-2}&equiv 0 pmod {3q+4}.\
end{align*}
But the last line holds true indeed, because we know from here that
begin{align*} binom{3q+4}{q-2}&equiv 0 pmod {frac{3q+4}{gcd(3q+4,q-2)}}\
&equiv 0 pmod {frac{3q+4}{gcd(10,q-2)}}end{align*}
There remains to show the validity of (2). We have
$$ binom{3q+4}{q-2}(24-q-q^2)= (3q+3)binom{3q+4}{q-4} frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$
so that we need to show that
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {(q-2)(q-3)}. $$
That is
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-2} $$
and
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-3}. $$
That is
$$ 180binom{3q+2}{q-4}equiv 0pmod {q-2} $$
and
$$ 156 binom{3q+2}{q-4}equiv 0pmod {q-3}. $$
That is
$$ 180frac{(q-2)(q-3)}{(3q+4)(q-2)}binom{3q+4}{q-2}equiv 0pmod {q-2} $$
and
$$ 156 frac{q-3}{3q+3}binom{3q+3}{q-3}equiv 0pmod {q-3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {(3q+4)(3q+3)} $$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+4} tag3$$
and
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+3} tag4$$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. tag5$$
For (5) it holds true because we have $156=13cdot 12$ a multiple of $12$ and from here, we have
begin{align*}binom{3q+3}{q-3}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-3)}} \
&equiv 0pmod {frac{3q+3}{gcd(12,q-3)}} end{align*}
For (3) it holds true because we have $180=18cdot 10$ a multiple of $10$ and from here, we have
begin{align*}binom{3q+4}{q-2}&equiv 0pmod {frac{3q+4}{gcd(3q+4,q-2)}} \
&equiv 0pmod {frac{3q+2}{gcd(10,q-2)}} end{align*}
We have seen that there exist an integer $K$, such that $binom{3q+3}{q-3}=Kfrac{3q+3}{gcd(12,q-3)}$. Now, with the same argument from here, we have
begin{align*}binom{3q+3}{q-2}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-2)}} \
&equiv 0pmod {frac{3q+3}{gcd(9,q-2)}} end{align*}
so there exists an integer $L$ such that $binom{3q+3}{q-2}=Lfrac{3q+3}{gcd(9,q-2)}$.
Then
begin{align*} 180(q-3)binom{3q+4}{q-2}&=180(q-3)left(binom{3q+3}{q-2}+binom{3q+3}{q-3}right)\
&= (3q+3)left( frac{180L(q-3)}{gcd(9,q-2)}+frac{180K(q-3)}{gcd(12,q-3)}right). end{align*}
The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.
Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction.
– JHF
Nov 21 at 15:54
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Here is a tentative proof:
We first notice that by Kummer theorem $binom{2n}{2m} equiv binom{n}{m} bmod 2$, so that it suffices to show that $$ S_q(n) equiv T_q(n) pmod 2$$ where
begin{align*}
S_q(n):=&sum_k binom{k}{n-k}binom{n+3q}{2k+2q+1}\
T_q(n):=&binom{n+3q}{2q-1}.
end{align*}
From here, the symbol $sim$ means has the same parity as.
We have
$binom{a+1}{b+1}sim binom{a}{b+1}+binom{a}{b}$ but also $binom{a+2}{b+2}sim binom{a+2}{b}+binom{a}{b}$.
We have
begin{align*} T_q(n+2)&sim binom{n+3q+2}{2q-1} sim binom{n+3q}{2q-1}+binom{n+3q}{2q-3}\
&sim T_q(n) +binom{n+3+3(q-1)}{2(q-1)-1} \
&sim T_q(n) +T_{q-1}(n+3) \
T_q(n+3)&sim T_{q+1}(n+2)+ T_{q+1}(n)
end{align*}
On the other hand, we have
begin{align*}S_q(n+3)& sim sum_k binom{k}{n+3-k}binom{n+3q+3}{2k+2q+1}\
&sim sum_k binom{k}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2(k-1)+2q+3}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
& sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\
&+sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim S_{q+1}(n+2) +sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2k+2(q+1)-1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2) \&+sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n-(k-1)}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
S_q(n+3)&sim S_{q+1}(n+2)+ S_{q+1}(n)
end{align*}
So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) sim T_q(n)$, it suffices to show that $ S_q(0) sim T_q(0)$, $ S_q(1) sim T_q(1)$ and $ S_q(2) sim T_q(2)$.
$S_q(0)-T_q(0)$ is clearly an even integer since
$$S_q(0)-T_q(0)= binom{3q}{q+1}-binom{3q}{q-1}=2 binom{3q+1}{q-1}.$$
We have $T_q(1)-S_q(1)= binom{3q+1}{q+2}-binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2frac{5q+7}{3q+3}binom{3q+3}{q-1}$$ which is an even integer since begin{align*}binom{3q+3}{q-1}(5q+7) &equiv binom{3q+3}{q-1}(2q+4)pmod {3q+3}\
&equiv-binom{3q+3}{q-1}(q-1)pmod {3q+3}\
&equiv-binom{3q+2}{q-2}(3q+3)pmod {3q+3}\
&equiv 0pmod {3q+3}end{align*}
Also, after some calculation, it can be shown that
begin{align*}
T_q(2)-S_q(2) &= binom{3q+2}{q+3}-binom{3q+2}{q-1}-binom{3q+2}{q-3}\
&= 2 binom{3q+5}{q-1} frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}.
end{align*}
Then, to complete the proof, we need to show that
$$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3)equiv 0 pmod {(3q+5)(3q+4)(3q+3)}.$$
We have $$ (54+301q+258q^2+59q^3) equiv (q-1)(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then $$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3) equiv (3q+5)binom{3q+4}{q-2}(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then it suffices to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {(3q+4)(3q+3)}.$$
But $3q+4$ and $3q+3$ are coprime, so we need to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+4}$$
and
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+3}.$$
That is
$$ binom{3q+4}{q-2}(14-q^2)equiv 0 pmod {3q+4} tag1$$
and
$$ binom{3q+4}{q-2}(24-q-q^2)equiv 0 pmod {3q+3}.tag2$$
(1) is equivalent to
begin{align*} frac{3q+4}{q-2}binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {3q+4} \
binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {q-2}\
10binom{3q+3}{q-3}&equiv 0 pmod {q-2}\
10frac{q-2}{3q+4}binom{3q+4}{q-2}&equiv 0 pmod {q-2}\
10binom{3q+4}{q-2}&equiv 0 pmod {3q+4}.\
end{align*}
But the last line holds true indeed, because we know from here that
begin{align*} binom{3q+4}{q-2}&equiv 0 pmod {frac{3q+4}{gcd(3q+4,q-2)}}\
&equiv 0 pmod {frac{3q+4}{gcd(10,q-2)}}end{align*}
There remains to show the validity of (2). We have
$$ binom{3q+4}{q-2}(24-q-q^2)= (3q+3)binom{3q+4}{q-4} frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$
so that we need to show that
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {(q-2)(q-3)}. $$
That is
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-2} $$
and
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-3}. $$
That is
$$ 180binom{3q+2}{q-4}equiv 0pmod {q-2} $$
and
$$ 156 binom{3q+2}{q-4}equiv 0pmod {q-3}. $$
That is
$$ 180frac{(q-2)(q-3)}{(3q+4)(q-2)}binom{3q+4}{q-2}equiv 0pmod {q-2} $$
and
$$ 156 frac{q-3}{3q+3}binom{3q+3}{q-3}equiv 0pmod {q-3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {(3q+4)(3q+3)} $$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+4} tag3$$
and
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+3} tag4$$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. tag5$$
For (5) it holds true because we have $156=13cdot 12$ a multiple of $12$ and from here, we have
begin{align*}binom{3q+3}{q-3}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-3)}} \
&equiv 0pmod {frac{3q+3}{gcd(12,q-3)}} end{align*}
For (3) it holds true because we have $180=18cdot 10$ a multiple of $10$ and from here, we have
begin{align*}binom{3q+4}{q-2}&equiv 0pmod {frac{3q+4}{gcd(3q+4,q-2)}} \
&equiv 0pmod {frac{3q+2}{gcd(10,q-2)}} end{align*}
We have seen that there exist an integer $K$, such that $binom{3q+3}{q-3}=Kfrac{3q+3}{gcd(12,q-3)}$. Now, with the same argument from here, we have
begin{align*}binom{3q+3}{q-2}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-2)}} \
&equiv 0pmod {frac{3q+3}{gcd(9,q-2)}} end{align*}
so there exists an integer $L$ such that $binom{3q+3}{q-2}=Lfrac{3q+3}{gcd(9,q-2)}$.
Then
begin{align*} 180(q-3)binom{3q+4}{q-2}&=180(q-3)left(binom{3q+3}{q-2}+binom{3q+3}{q-3}right)\
&= (3q+3)left( frac{180L(q-3)}{gcd(9,q-2)}+frac{180K(q-3)}{gcd(12,q-3)}right). end{align*}
The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.
Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction.
– JHF
Nov 21 at 15:54
add a comment |
up vote
3
down vote
accepted
Here is a tentative proof:
We first notice that by Kummer theorem $binom{2n}{2m} equiv binom{n}{m} bmod 2$, so that it suffices to show that $$ S_q(n) equiv T_q(n) pmod 2$$ where
begin{align*}
S_q(n):=&sum_k binom{k}{n-k}binom{n+3q}{2k+2q+1}\
T_q(n):=&binom{n+3q}{2q-1}.
end{align*}
From here, the symbol $sim$ means has the same parity as.
We have
$binom{a+1}{b+1}sim binom{a}{b+1}+binom{a}{b}$ but also $binom{a+2}{b+2}sim binom{a+2}{b}+binom{a}{b}$.
We have
begin{align*} T_q(n+2)&sim binom{n+3q+2}{2q-1} sim binom{n+3q}{2q-1}+binom{n+3q}{2q-3}\
&sim T_q(n) +binom{n+3+3(q-1)}{2(q-1)-1} \
&sim T_q(n) +T_{q-1}(n+3) \
T_q(n+3)&sim T_{q+1}(n+2)+ T_{q+1}(n)
end{align*}
On the other hand, we have
begin{align*}S_q(n+3)& sim sum_k binom{k}{n+3-k}binom{n+3q+3}{2k+2q+1}\
&sim sum_k binom{k}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2(k-1)+2q+3}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
& sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\
&+sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim S_{q+1}(n+2) +sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2k+2(q+1)-1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2) \&+sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n-(k-1)}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
S_q(n+3)&sim S_{q+1}(n+2)+ S_{q+1}(n)
end{align*}
So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) sim T_q(n)$, it suffices to show that $ S_q(0) sim T_q(0)$, $ S_q(1) sim T_q(1)$ and $ S_q(2) sim T_q(2)$.
$S_q(0)-T_q(0)$ is clearly an even integer since
$$S_q(0)-T_q(0)= binom{3q}{q+1}-binom{3q}{q-1}=2 binom{3q+1}{q-1}.$$
We have $T_q(1)-S_q(1)= binom{3q+1}{q+2}-binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2frac{5q+7}{3q+3}binom{3q+3}{q-1}$$ which is an even integer since begin{align*}binom{3q+3}{q-1}(5q+7) &equiv binom{3q+3}{q-1}(2q+4)pmod {3q+3}\
&equiv-binom{3q+3}{q-1}(q-1)pmod {3q+3}\
&equiv-binom{3q+2}{q-2}(3q+3)pmod {3q+3}\
&equiv 0pmod {3q+3}end{align*}
Also, after some calculation, it can be shown that
begin{align*}
T_q(2)-S_q(2) &= binom{3q+2}{q+3}-binom{3q+2}{q-1}-binom{3q+2}{q-3}\
&= 2 binom{3q+5}{q-1} frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}.
end{align*}
Then, to complete the proof, we need to show that
$$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3)equiv 0 pmod {(3q+5)(3q+4)(3q+3)}.$$
We have $$ (54+301q+258q^2+59q^3) equiv (q-1)(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then $$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3) equiv (3q+5)binom{3q+4}{q-2}(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then it suffices to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {(3q+4)(3q+3)}.$$
But $3q+4$ and $3q+3$ are coprime, so we need to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+4}$$
and
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+3}.$$
That is
$$ binom{3q+4}{q-2}(14-q^2)equiv 0 pmod {3q+4} tag1$$
and
$$ binom{3q+4}{q-2}(24-q-q^2)equiv 0 pmod {3q+3}.tag2$$
(1) is equivalent to
begin{align*} frac{3q+4}{q-2}binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {3q+4} \
binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {q-2}\
10binom{3q+3}{q-3}&equiv 0 pmod {q-2}\
10frac{q-2}{3q+4}binom{3q+4}{q-2}&equiv 0 pmod {q-2}\
10binom{3q+4}{q-2}&equiv 0 pmod {3q+4}.\
end{align*}
But the last line holds true indeed, because we know from here that
begin{align*} binom{3q+4}{q-2}&equiv 0 pmod {frac{3q+4}{gcd(3q+4,q-2)}}\
&equiv 0 pmod {frac{3q+4}{gcd(10,q-2)}}end{align*}
There remains to show the validity of (2). We have
$$ binom{3q+4}{q-2}(24-q-q^2)= (3q+3)binom{3q+4}{q-4} frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$
so that we need to show that
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {(q-2)(q-3)}. $$
That is
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-2} $$
and
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-3}. $$
That is
$$ 180binom{3q+2}{q-4}equiv 0pmod {q-2} $$
and
$$ 156 binom{3q+2}{q-4}equiv 0pmod {q-3}. $$
That is
$$ 180frac{(q-2)(q-3)}{(3q+4)(q-2)}binom{3q+4}{q-2}equiv 0pmod {q-2} $$
and
$$ 156 frac{q-3}{3q+3}binom{3q+3}{q-3}equiv 0pmod {q-3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {(3q+4)(3q+3)} $$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+4} tag3$$
and
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+3} tag4$$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. tag5$$
For (5) it holds true because we have $156=13cdot 12$ a multiple of $12$ and from here, we have
begin{align*}binom{3q+3}{q-3}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-3)}} \
&equiv 0pmod {frac{3q+3}{gcd(12,q-3)}} end{align*}
For (3) it holds true because we have $180=18cdot 10$ a multiple of $10$ and from here, we have
begin{align*}binom{3q+4}{q-2}&equiv 0pmod {frac{3q+4}{gcd(3q+4,q-2)}} \
&equiv 0pmod {frac{3q+2}{gcd(10,q-2)}} end{align*}
We have seen that there exist an integer $K$, such that $binom{3q+3}{q-3}=Kfrac{3q+3}{gcd(12,q-3)}$. Now, with the same argument from here, we have
begin{align*}binom{3q+3}{q-2}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-2)}} \
&equiv 0pmod {frac{3q+3}{gcd(9,q-2)}} end{align*}
so there exists an integer $L$ such that $binom{3q+3}{q-2}=Lfrac{3q+3}{gcd(9,q-2)}$.
Then
begin{align*} 180(q-3)binom{3q+4}{q-2}&=180(q-3)left(binom{3q+3}{q-2}+binom{3q+3}{q-3}right)\
&= (3q+3)left( frac{180L(q-3)}{gcd(9,q-2)}+frac{180K(q-3)}{gcd(12,q-3)}right). end{align*}
The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.
Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction.
– JHF
Nov 21 at 15:54
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Here is a tentative proof:
We first notice that by Kummer theorem $binom{2n}{2m} equiv binom{n}{m} bmod 2$, so that it suffices to show that $$ S_q(n) equiv T_q(n) pmod 2$$ where
begin{align*}
S_q(n):=&sum_k binom{k}{n-k}binom{n+3q}{2k+2q+1}\
T_q(n):=&binom{n+3q}{2q-1}.
end{align*}
From here, the symbol $sim$ means has the same parity as.
We have
$binom{a+1}{b+1}sim binom{a}{b+1}+binom{a}{b}$ but also $binom{a+2}{b+2}sim binom{a+2}{b}+binom{a}{b}$.
We have
begin{align*} T_q(n+2)&sim binom{n+3q+2}{2q-1} sim binom{n+3q}{2q-1}+binom{n+3q}{2q-3}\
&sim T_q(n) +binom{n+3+3(q-1)}{2(q-1)-1} \
&sim T_q(n) +T_{q-1}(n+3) \
T_q(n+3)&sim T_{q+1}(n+2)+ T_{q+1}(n)
end{align*}
On the other hand, we have
begin{align*}S_q(n+3)& sim sum_k binom{k}{n+3-k}binom{n+3q+3}{2k+2q+1}\
&sim sum_k binom{k}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2(k-1)+2q+3}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
& sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\
&+sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim S_{q+1}(n+2) +sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2k+2(q+1)-1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2) \&+sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n-(k-1)}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
S_q(n+3)&sim S_{q+1}(n+2)+ S_{q+1}(n)
end{align*}
So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) sim T_q(n)$, it suffices to show that $ S_q(0) sim T_q(0)$, $ S_q(1) sim T_q(1)$ and $ S_q(2) sim T_q(2)$.
$S_q(0)-T_q(0)$ is clearly an even integer since
$$S_q(0)-T_q(0)= binom{3q}{q+1}-binom{3q}{q-1}=2 binom{3q+1}{q-1}.$$
We have $T_q(1)-S_q(1)= binom{3q+1}{q+2}-binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2frac{5q+7}{3q+3}binom{3q+3}{q-1}$$ which is an even integer since begin{align*}binom{3q+3}{q-1}(5q+7) &equiv binom{3q+3}{q-1}(2q+4)pmod {3q+3}\
&equiv-binom{3q+3}{q-1}(q-1)pmod {3q+3}\
&equiv-binom{3q+2}{q-2}(3q+3)pmod {3q+3}\
&equiv 0pmod {3q+3}end{align*}
Also, after some calculation, it can be shown that
begin{align*}
T_q(2)-S_q(2) &= binom{3q+2}{q+3}-binom{3q+2}{q-1}-binom{3q+2}{q-3}\
&= 2 binom{3q+5}{q-1} frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}.
end{align*}
Then, to complete the proof, we need to show that
$$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3)equiv 0 pmod {(3q+5)(3q+4)(3q+3)}.$$
We have $$ (54+301q+258q^2+59q^3) equiv (q-1)(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then $$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3) equiv (3q+5)binom{3q+4}{q-2}(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then it suffices to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {(3q+4)(3q+3)}.$$
But $3q+4$ and $3q+3$ are coprime, so we need to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+4}$$
and
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+3}.$$
That is
$$ binom{3q+4}{q-2}(14-q^2)equiv 0 pmod {3q+4} tag1$$
and
$$ binom{3q+4}{q-2}(24-q-q^2)equiv 0 pmod {3q+3}.tag2$$
(1) is equivalent to
begin{align*} frac{3q+4}{q-2}binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {3q+4} \
binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {q-2}\
10binom{3q+3}{q-3}&equiv 0 pmod {q-2}\
10frac{q-2}{3q+4}binom{3q+4}{q-2}&equiv 0 pmod {q-2}\
10binom{3q+4}{q-2}&equiv 0 pmod {3q+4}.\
end{align*}
But the last line holds true indeed, because we know from here that
begin{align*} binom{3q+4}{q-2}&equiv 0 pmod {frac{3q+4}{gcd(3q+4,q-2)}}\
&equiv 0 pmod {frac{3q+4}{gcd(10,q-2)}}end{align*}
There remains to show the validity of (2). We have
$$ binom{3q+4}{q-2}(24-q-q^2)= (3q+3)binom{3q+4}{q-4} frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$
so that we need to show that
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {(q-2)(q-3)}. $$
That is
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-2} $$
and
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-3}. $$
That is
$$ 180binom{3q+2}{q-4}equiv 0pmod {q-2} $$
and
$$ 156 binom{3q+2}{q-4}equiv 0pmod {q-3}. $$
That is
$$ 180frac{(q-2)(q-3)}{(3q+4)(q-2)}binom{3q+4}{q-2}equiv 0pmod {q-2} $$
and
$$ 156 frac{q-3}{3q+3}binom{3q+3}{q-3}equiv 0pmod {q-3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {(3q+4)(3q+3)} $$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+4} tag3$$
and
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+3} tag4$$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. tag5$$
For (5) it holds true because we have $156=13cdot 12$ a multiple of $12$ and from here, we have
begin{align*}binom{3q+3}{q-3}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-3)}} \
&equiv 0pmod {frac{3q+3}{gcd(12,q-3)}} end{align*}
For (3) it holds true because we have $180=18cdot 10$ a multiple of $10$ and from here, we have
begin{align*}binom{3q+4}{q-2}&equiv 0pmod {frac{3q+4}{gcd(3q+4,q-2)}} \
&equiv 0pmod {frac{3q+2}{gcd(10,q-2)}} end{align*}
We have seen that there exist an integer $K$, such that $binom{3q+3}{q-3}=Kfrac{3q+3}{gcd(12,q-3)}$. Now, with the same argument from here, we have
begin{align*}binom{3q+3}{q-2}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-2)}} \
&equiv 0pmod {frac{3q+3}{gcd(9,q-2)}} end{align*}
so there exists an integer $L$ such that $binom{3q+3}{q-2}=Lfrac{3q+3}{gcd(9,q-2)}$.
Then
begin{align*} 180(q-3)binom{3q+4}{q-2}&=180(q-3)left(binom{3q+3}{q-2}+binom{3q+3}{q-3}right)\
&= (3q+3)left( frac{180L(q-3)}{gcd(9,q-2)}+frac{180K(q-3)}{gcd(12,q-3)}right). end{align*}
The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.
Here is a tentative proof:
We first notice that by Kummer theorem $binom{2n}{2m} equiv binom{n}{m} bmod 2$, so that it suffices to show that $$ S_q(n) equiv T_q(n) pmod 2$$ where
begin{align*}
S_q(n):=&sum_k binom{k}{n-k}binom{n+3q}{2k+2q+1}\
T_q(n):=&binom{n+3q}{2q-1}.
end{align*}
From here, the symbol $sim$ means has the same parity as.
We have
$binom{a+1}{b+1}sim binom{a}{b+1}+binom{a}{b}$ but also $binom{a+2}{b+2}sim binom{a+2}{b}+binom{a}{b}$.
We have
begin{align*} T_q(n+2)&sim binom{n+3q+2}{2q-1} sim binom{n+3q}{2q-1}+binom{n+3q}{2q-3}\
&sim T_q(n) +binom{n+3+3(q-1)}{2(q-1)-1} \
&sim T_q(n) +T_{q-1}(n+3) \
T_q(n+3)&sim T_{q+1}(n+2)+ T_{q+1}(n)
end{align*}
On the other hand, we have
begin{align*}S_q(n+3)& sim sum_k binom{k}{n+3-k}binom{n+3q+3}{2k+2q+1}\
&sim sum_k binom{k}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3q+1}{2(k-1)+2q+3}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\
&+ sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
& sim sum_k binom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n+2-(k-1)}binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\
&+sum_k binom{k-1}{n+1-(k-1)}binom{n+2+3q+1}{2k+2q+1}\
&sim S_{q+1}(n+2) +sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2k+2(q+1)-1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2) \&+sum_kbinom{k}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_kbinom{k-1}{n-(k-1)}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\
&+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n) \&+sum_kbinom{k-1}{n+2-k}binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
&sim S_{q+1}(n+2)+ S_{q+1}(n)+2sum_k binom{k}{n+1-k}binom{n+3(q+1)}{2k+2(q+1)+1}\
S_q(n+3)&sim S_{q+1}(n+2)+ S_{q+1}(n)
end{align*}
So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) sim T_q(n)$, it suffices to show that $ S_q(0) sim T_q(0)$, $ S_q(1) sim T_q(1)$ and $ S_q(2) sim T_q(2)$.
$S_q(0)-T_q(0)$ is clearly an even integer since
$$S_q(0)-T_q(0)= binom{3q}{q+1}-binom{3q}{q-1}=2 binom{3q+1}{q-1}.$$
We have $T_q(1)-S_q(1)= binom{3q+1}{q+2}-binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2frac{5q+7}{3q+3}binom{3q+3}{q-1}$$ which is an even integer since begin{align*}binom{3q+3}{q-1}(5q+7) &equiv binom{3q+3}{q-1}(2q+4)pmod {3q+3}\
&equiv-binom{3q+3}{q-1}(q-1)pmod {3q+3}\
&equiv-binom{3q+2}{q-2}(3q+3)pmod {3q+3}\
&equiv 0pmod {3q+3}end{align*}
Also, after some calculation, it can be shown that
begin{align*}
T_q(2)-S_q(2) &= binom{3q+2}{q+3}-binom{3q+2}{q-1}-binom{3q+2}{q-3}\
&= 2 binom{3q+5}{q-1} frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}.
end{align*}
Then, to complete the proof, we need to show that
$$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3)equiv 0 pmod {(3q+5)(3q+4)(3q+3)}.$$
We have $$ (54+301q+258q^2+59q^3) equiv (q-1)(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then $$ binom{3q+5}{q-1} (54+301q+258q^2+59q^3) equiv (3q+5)binom{3q+4}{q-2}(66+47q+5q^2)pmod {(3q+5)(3q+4)(3q+3)}.$$
Then it suffices to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {(3q+4)(3q+3)}.$$
But $3q+4$ and $3q+3$ are coprime, so we need to show that
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+4}$$
and
$$ binom{3q+4}{q-2}(66+47q+5q^2)equiv 0 pmod {3q+3}.$$
That is
$$ binom{3q+4}{q-2}(14-q^2)equiv 0 pmod {3q+4} tag1$$
and
$$ binom{3q+4}{q-2}(24-q-q^2)equiv 0 pmod {3q+3}.tag2$$
(1) is equivalent to
begin{align*} frac{3q+4}{q-2}binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {3q+4} \
binom{3q+3}{q-3}(14-q^2)&equiv 0 pmod {q-2}\
10binom{3q+3}{q-3}&equiv 0 pmod {q-2}\
10frac{q-2}{3q+4}binom{3q+4}{q-2}&equiv 0 pmod {q-2}\
10binom{3q+4}{q-2}&equiv 0 pmod {3q+4}.\
end{align*}
But the last line holds true indeed, because we know from here that
begin{align*} binom{3q+4}{q-2}&equiv 0 pmod {frac{3q+4}{gcd(3q+4,q-2)}}\
&equiv 0 pmod {frac{3q+4}{gcd(10,q-2)}}end{align*}
There remains to show the validity of (2). We have
$$ binom{3q+4}{q-2}(24-q-q^2)= (3q+3)binom{3q+4}{q-4} frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$
so that we need to show that
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {(q-2)(q-3)}. $$
That is
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-2} $$
and
$$ binom{3q+2}{q-4}(3q+4)(24-q-q^2)equiv 0pmod {q-3}. $$
That is
$$ 180binom{3q+2}{q-4}equiv 0pmod {q-2} $$
and
$$ 156 binom{3q+2}{q-4}equiv 0pmod {q-3}. $$
That is
$$ 180frac{(q-2)(q-3)}{(3q+4)(q-2)}binom{3q+4}{q-2}equiv 0pmod {q-2} $$
and
$$ 156 frac{q-3}{3q+3}binom{3q+3}{q-3}equiv 0pmod {q-3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {(3q+4)(3q+3)} $$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. $$
That is
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+4} tag3$$
and
$$ 180(q-3)binom{3q+4}{q-2}equiv 0pmod {3q+3} tag4$$
and
$$ 156binom{3q+3}{q-3}equiv 0pmod {3q+3}. tag5$$
For (5) it holds true because we have $156=13cdot 12$ a multiple of $12$ and from here, we have
begin{align*}binom{3q+3}{q-3}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-3)}} \
&equiv 0pmod {frac{3q+3}{gcd(12,q-3)}} end{align*}
For (3) it holds true because we have $180=18cdot 10$ a multiple of $10$ and from here, we have
begin{align*}binom{3q+4}{q-2}&equiv 0pmod {frac{3q+4}{gcd(3q+4,q-2)}} \
&equiv 0pmod {frac{3q+2}{gcd(10,q-2)}} end{align*}
We have seen that there exist an integer $K$, such that $binom{3q+3}{q-3}=Kfrac{3q+3}{gcd(12,q-3)}$. Now, with the same argument from here, we have
begin{align*}binom{3q+3}{q-2}&equiv 0pmod {frac{3q+3}{gcd(3q+3,q-2)}} \
&equiv 0pmod {frac{3q+3}{gcd(9,q-2)}} end{align*}
so there exists an integer $L$ such that $binom{3q+3}{q-2}=Lfrac{3q+3}{gcd(9,q-2)}$.
Then
begin{align*} 180(q-3)binom{3q+4}{q-2}&=180(q-3)left(binom{3q+3}{q-2}+binom{3q+3}{q-3}right)\
&= (3q+3)left( frac{180L(q-3)}{gcd(9,q-2)}+frac{180K(q-3)}{gcd(12,q-3)}right). end{align*}
The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.
edited Nov 18 at 23:25
answered Nov 18 at 22:51
René Gy
1,081613
1,081613
Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction.
– JHF
Nov 21 at 15:54
add a comment |
Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction.
– JHF
Nov 21 at 15:54
Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction.
– JHF
Nov 21 at 15:54
Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction.
– JHF
Nov 21 at 15:54
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%2f3002663%2fa-mod-2-binomial-identity%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