For each positive integer $n$, set $x_n=\binom{2n}{n}$. a. Prove that if $\frac{2017^k}{2}<n<2017^k$ for some positive integer $k$ then $2017$ divides $x_n$. b. Find all positive integer $h>1$ such that there exists positive integers $N,T$ such that $(x_n)_{n>N}$ is periodic mod $h$ with period $T$.
Problem
Source: Vietnam TST 2017
Tags: binomial coefficients, Integer sequence, Periodic sequence
26.03.2017 14:24
We can prove A easily with Lucas theorem
27.03.2017 08:01
who can solve it
27.03.2017 16:19
Part a) $v_{2017}((2n)!)=[2n/2017]+[2n/2017^2]+...+[2n/2017^k]$ $v_{2017}((n)!)=[n/2017]+[n/2017^2]+...+[n/2017^{k-1}]$ $v_{2017}(x_n)=v_{2017}((2n)!)-2v_{2017}((n)!) \geq [2n/2017^k]=1$ Part b) Let $p|h, p>2$ - prime. Let we find such $N,T$ It always possible to find such natural $a,k$ that $p^k>N$ and $p^k(p-2)<2aT<2p^k(p-1)$ Let $n_1=p^k,n_2=p^k+aT$ $p^k+aT>p^{k+1}/2$ and $p^k+aT<p^{k+1}$ Similar way, as in part a) we can prove, that $p|x_{n_2}$ But $v_p(x_{n_1})=v_p((2p^k)!)-2v_p((p^k)!)=0$ So $x_{n_1} \neq x_{n_2} \pmod p$ -contradiction. So $h=2^m$ For $h=2$ $x_n =0 \pmod 2$, so $h=2$ is answer. If it true for $h=2^m,m>1$, then must be true for $h=4$ Let we find such $N,T$ for $h=4$. $2^k<T<2^{k+1}$ and $2^m>N,m>k+1$ $v_2(x_{2^m})=v_2((2^{m+1})!)-2v_2((2^m)!)=2^{m+1}-1-2(2^m-1)=1$ so $x_{2^m}=2 \pmod 4$ $v_2(x_{2^m+T})=v_2((2^{m+1}+2T)!)-2v_2((2^m+T)!)=2^{m+1}-1+2^{k+1}-1-2(2^m-1+2^k-1)=2$ so $x_{2^m+T} =0 \pmod 4$ - contradiction. Answer: Only for $h=2$
15.05.2017 18:16
RagvaloD wrote: Part a) $v_{2017}((2n)!)=[2n/2017]+[2n/2017^2]+...+[2n/2017^k]$ $v_{2017}((n)!)=[n/2017]+[n/2017^2]+...+[n/2017^{k-1}]$ $v_{2017}(x_n)=v_{2017}((2n)!)-2v_{2017}((n)!) \geq [2n/2017^k]=1$ Part b) Let $p|h, p>2$ - prime. Let we find such $N,T$ It always possible to find such natural $a,k$ that $p^k>N$ and $p^k(p-2)<2aT<2p^k(p-1)$ Let $n_1=p^k,n_2=p^k+aT$ $p^k+aT>p^{k+1}/2$ and $p^k+aT<p^{k+1}$ Similar way, as in part a) we can prove, that $p|x_{n_2}$ But $v_p(x_{n_1})=v_p((2p^k)!)-2v_p((p^k)!)=0$ So $x_{n_1} \neq x_{n_2} \pmod p$ -contradiction. So $h=2^m$ For $h=2$ $x_n =0 \pmod 2$, so $h=2$ is answer. If it true for $h=2^m,m>1$, then must be true for $h=4$ Let we find such $N,T$ for $h=4$. $2^k<T<2^{k+1}$ and $2^m>N,m>k+1$ $v_2(x_{2^m})=v_2((2^{m+1})!)-2v_2((2^m)!)=2^{m+1}-1-2(2^m-1)=1$ so $x_{2^m}=2 \pmod 4$ $v_2(x_{2^m+T})=v_2((2^{m+1}+2T)!)-2v_2((2^m+T)!)=2^{m+1}-1+2^{k+1}-1-2(2^m-1+2^k-1)=2$ so $x_{2^m+T} =0 \pmod 4$ - contradiction. Answer: Only for $h=2$ What if T is larger than 2p^k(p-1)
15.05.2017 18:38
For (b) the answer is $h=1$ and $h=2$. For $h=4$ (and hence all periods divisible by $4$), one can show that $x_n\equiv 2\bmod4$ whenever $n$ is a power of $2$, and $x_n\equiv 0\bmod4$ otherwise. Hence there is no periodicity. For $h$ an odd prime (and hence all periods divisible by an odd prime), a similar argument works. There is no periodicity.
15.05.2017 18:49
test20 wrote: For (b) the answer is $h=1$ and $h=2$. For $h=4$ (and hence all periods divisible by $4$), one can show that $x_n\equiv 2\bmod4$ whenever $n$ is a power of $2$, and $x_n\equiv 0\bmod4$ otherwise. Hence there is no periodicity. For $h$ an odd prime (and hence all periods divisible by an odd prime), a similar argument works. There is no periodicity. Be more detailed pls
15.05.2017 18:52
Erkhes wrote: RagvaloD wrote: Part a) $v_{2017}((2n)!)=[2n/2017]+[2n/2017^2]+...+[2n/2017^k]$ $v_{2017}((n)!)=[n/2017]+[n/2017^2]+...+[n/2017^{k-1}]$ $v_{2017}(x_n)=v_{2017}((2n)!)-2v_{2017}((n)!) \geq [2n/2017^k]=1$ Part b) Let $p|h, p>2$ - prime. Let we find such $N,T$ It always possible to find such natural $a,k$ that $p^k>N$ and $p^k(p-2)<2aT<2p^k(p-1)$ Let $n_1=p^k,n_2=p^k+aT$ $p^k+aT>p^{k+1}/2$ and $p^k+aT<p^{k+1}$ Similar way, as in part a) we can prove, that $p|x_{n_2}$ But $v_p(x_{n_1})=v_p((2p^k)!)-2v_p((p^k)!)=0$ So $x_{n_1} \neq x_{n_2} \pmod p$ -contradiction. So $h=2^m$ For $h=2$ $x_n =0 \pmod 2$, so $h=2$ is answer. If it true for $h=2^m,m>1$, then must be true for $h=4$ Let we find such $N,T$ for $h=4$. $2^k<T<2^{k+1}$ and $2^m>N,m>k+1$ $v_2(x_{2^m})=v_2((2^{m+1})!)-2v_2((2^m)!)=2^{m+1}-1-2(2^m-1)=1$ so $x_{2^m}=2 \pmod 4$ $v_2(x_{2^m+T})=v_2((2^{m+1}+2T)!)-2v_2((2^m+T)!)=2^{m+1}-1+2^{k+1}-1-2(2^m-1+2^k-1)=2$ so $x_{2^m+T} =0 \pmod 4$ - contradiction. Answer: Only for $h=2$ What if T is larger than 2p^k(p-1) Oh sry u r right
15.05.2017 19:39
Humm, I have heard that it is on AMM. Can anyone check it
03.12.2017 12:13
it is easy and general : find all h is in N such that : xn = C(an;bn) exist N,T : xn=xn+T (mod h) with n>= N and a>b positive integer I have similar solution with ravarlog
03.12.2017 16:37
it is easy , by legendre formula ,and $\forall x \in \mathbb{R} : \lfloor{2y \rfloor} > 2\lfloor{y\rfloor}$
22.05.2019 17:30
Here is a solution for part b) by tastymath75025 https://artofproblemsolving.com/community/c6h1545276p9373798
11.06.2019 11:08
Actually the result in part a is true for all $p$ is odd prime number a) Suppose there exist $k \in \mathbb{N}$ which satisfies $\dfrac{p^k}{2} < n < p^k$ Then: $p^k < 2n < 2 p^k < p^{k + 1}$ Combine with: $[2x] \ge 2[x], \forall x \in \mathbb{R}$, we have: $x_n \vdots p$ $\Leftrightarrow$ $v_p(C^n_{2n}) > 0$ $\Leftrightarrow$ $v_p((2n)!) > 2 v_p(n!)$ $\Leftrightarrow$ $\sum^k_{i = 1} \left[\dfrac{2n}{p^i} \right] - 2 \sum^{k - 1}_{j = 1} \left[\dfrac{n}{p^j} \right] > 0$ $\Leftrightarrow$ $\sum^{k - 1}_{i = 1} \left( \left[\dfrac{2n}{p^i} \right] - 2 \left[\dfrac{n}{p^i} \right] \right) + \left[\dfrac{2n}{p^k} \right] > 0$ which is true So: $x_n \vdots p$ with $\dfrac{p^k}{2} < n < p^k$ and $p$ is odd prime number
06.06.2021 22:57
a) We will prove a stronger claim: for any odd prime $p$, if $\frac{p^k}{2}<n<p^k$ for some positive integer $k$ and odd prime $p$, then $\binom{2n}{n}$ is a multiple of $p$. Proof: $\left\lfloor\frac{2n}{p^i}\right\rfloor\ge 2\left\lfloor\frac{n}{p^i}\right\rfloor$, and the equality is strict when $i=k$, hence we are done by Legendre formula. b) Part a) already shows that $h$ cannot have any odd prime divisors $p$, since $x_n$ is a multiple of $p$ for $\frac{p^k}{2}<n<p^k$ but not for $n=p^k$; for any value of $T$, we can always choose $k$ such that $p^k>T$. It's well known that $\nu_2\left(\binom{2n}{n}\right)=1$ if $n$ is a power of 2 and $\nu_2\left(\binom{2n}{n}\right)\ge 2$ otherwise, so the only power of 2 that works is $h=2$, which is our only solution.