Determine all integers $k$ such that there exists infinitely many positive integers $n$ not satisfying \[n+k |\binom{2n}{n}\]
Problem
Source: China Mathematical Olympiad 2015 Q4
Tags: logarithms, number theory proposed, number theory
21.12.2014 12:59
For any natural $k$ there exist infinitely many primes $p>2k$, and for $n=p-k$ we have $n+k=p \mid \binom{2n}{n}$.
22.12.2014 02:00
The condition is :do not divide !
22.12.2014 07:46
fattypiggy123 wrote: Determine all integers $k$ such that there exists infinitely many positive integers $n$ satisfying \[n+k | \binom{2n}{n}\] The problem is Determine all integers $k$ such that there exists infinitely many positive integers $n$ not satisfying \[n+k | \binom{2n}{n}\] Solution: a)If $k=0$, we can choose $n = {2^\alpha }$ for any positve integer $\alpha \geqslant 2$, from Kummer theorem we have ${v_2}\left( {C_{2n}^n} \right) = 1$, but $4\left| {n + k} \right.$ . b)If $k \ne 0,1$, for any positve integer $\alpha \geqslant 3 + {\log _2}\left| k \right|$, we can choose $n = {2^\alpha } - k$, from Kummer theorem we have ${v_2}\left( {C_{2n}^n} \right) \leqslant \alpha - 1$, but $n + k = {2^\alpha }$. c)If $k = 1$, we have $\frac{1}{{n + 1}}C_{2n}^n = C_{2n}^n - \frac{n}{{n + 1}}C_{2n}^n = C_{2n}^n - C_{2n}^{n + 1}$ is an integer, so $\left( {n + 1} \right)\left| {C_{2n}^n} \right.$ for any n. ($\frac{1}{{n + 1}}C_{2n}^n$ is an $Catalan$ number.) So all integers $k \ne 1$ satisfy the condition.
04.01.2015 19:28
Case1:$k$ has an odd prime factor. Let $a$ be such that $p^a||k$ where $p$ is an odd prime.Then choose $n=p^m$ where $m>>a$.Then $n+k|\dbinom{2n}{n}$ (let use call this $D$) would imply that $p^a|\dbinom{2p^m}{p^m}$.But by De Polignac's expression we get $v_p{(2p^m)!}=\sum_{i=1}^{m}{[2p^m/p^_{i}]}=2\frac{p^m-1}{p-1}$.We also get $v_p{p^m!}=\sum_{i=1}^{m}{[p^m/p^i]}=\frac{p^m-1}{p-1}$.So $p \not | \dbinom{2p^m}{p^m}$.(One can also use Lucas' theorem) Case2:$k=2^\alpha$ for some $\alpha \ge 1$. If $\alpha \ge 2$ then choose $n=2^{m}$ where $m>>\alpha$.Then $D$ implies that $2^{\alpha}|\dbinom{2^{m+1}}{2^m}$.But again by De Polignac expression we get $2|| \dbinom{2^{m+1}}{2^m}$. If $\alpha=1$ then choose $n=2^m-2$.Then $D$ implies that $2^m| \dbinom{2^{m+1}-4}{2^m-2}$.Again by De Polignac expression we get $2^{m-1} || \dbinom{2^{m+1}-4}{2^m-2}$. Case 3:$k=1$. We know that the $n$-th Catalan number is $\frac{1}{n+1}\dbinom{2n}{n}$ and of course the Catalan numbers are integers. Since we can choose infinitely many $m$ and hence infinitely many $n$ in Cases 1 and 2, all numbers $k \not= 1$ satisfy the condition.
04.01.2015 22:46
for any k>1,m, suth that $2^{m-1}>k$ work $n=2^m-k$, because $v_2(\binom{2n}{n})=v_2((2n)!)-2v_2(n!)=[\frac{2n}{2}]+[\frac{2n}{4}]+...-2[\frac{n}{2}]-2[\frac{n}{4}]-...=r$, were $r$ is number of non zero digits of n and $r\le [log_2 n]+1<m$ (k>1).
10.01.2015 22:33
If $k<0$ we can use this way. Take $k=-g$ and choose big primes $p > 3g$ then $n+k=n-g=p \Rightarrow n=p+g$. Note that $v_p(n!)=1$ and $v_p((2n)!)=2$, because $3p = 3n - 3g = 2n + n-3g > 2n$. So $ n+k\not |\binom{2n}{n} $.
07.03.2015 16:03
We can use Bertrand's postulate to prove too
13.03.2015 23:33
06.09.2015 00:22
Here is a beautiful solution: We claim that the problem statement holds for all $k \ne 1.$ If $k = 1$, then note that $\tfrac{1}{n + 1}\tbinom{2n}{n}$ is the $n$th Catalan Number, which is always an integer. Meanwhile, if $k > 1$, by Bertrand's Postulate we may select an odd prime $k < p < 2k.$ Then choose $n = (p - k) + p^m$ for any $m \in \mathbb{N}.$ It follows from Legendre's Formula that \[v_p\left[\binom{2n}{n}\right] = \frac{2s_p(n) - s_p(2n)}{p - 1}.\] Since $2n = 2(p - k) + 2p^m$ and $2(p - k) < p$, it follows that $s_p(2n) = 2(p - k) + 2 = 2s_p(n).$ Consequently, $v_p\left[\tbinom{2n}{n}\right] = 0.$ However, $p \mid n + k$, so we have $n + k \nmid \tbinom{2n}{n}$ for infinitely many $n$, as desired. $\blacksquare$ Finally, if $k < 0$, Choose $n = -k + p^m$ for an odd prime $p > |2k|$ and any $m \in \mathbb{N}.$ In an identical manner as before, we obtain $v_p\left[\tbinom{2n}{n}\right] = 0$, but $p \mid n + k.$ Consequently, $n + k \nmid \tbinom{2n}{n}$ as desired. $\square$
09.04.2018 00:29
Its necessary to assume(or make a condition) that k<n?, because i suspect when k>n there are infinite numbers that satisfy the condition of divisibility. Sorry for my English.
15.01.2020 20:18
Case 1: $k>1$ Let $n=2^t-k$ for large $t$. $v_2(\binom{2n}{n})=S_2(2^t-k)<t$ for $k>1$, hence we're done. Case 2: $k<1$ Let $n=2^t-k$, and for large enough $t$ we get $S_2(2^t-k)=S_2(-k)+1 <t$, hence we're done. Case 3 (aka the point of the problem ): $k=1$ Note that $C_n=n^{\text{th}}$ Catalan number $=\frac{1}{n+1} \binom{2n}{n}$ is an integer, hence $k=1$ is the only integer that's not a solution.
23.06.2020 23:52
Solved with solver1104 (and by that I mean I got carried) The answer is all integers other than $1$. Consider some positive integer $k$ and a prime $p$ such that $p | k$. Assume $n+k | \binom{2n}{n}$ so $$v_p(n+k) + 2v_p(n!) \le v_p((2n)!)$$If $p > 2$, then when $n = p^x$ for some sufficiently large positive integer $x$, we have $2v_p(n!) = v_p((2n)!)$ by Legendre's, so $v_p(n+k) \le 0$ and thus $p$ can't divide $n+k$, which is obviously false. Thus, any positive integer $k$ with some $p > 2$ dividing $k$ causes a contradiction and satisfies the problem statement. It remains to check when $k$ is a power of $2$. Then when $n = 2^x$, $2v_p(n!) = v_p((2n)!)+1$ again by Legendre's, so $v_2(n+k) \le 1$. If $4 | k$ then choosing a sufficiently large $x$ will result in $v_2(n+k) \ge 2$, another contradiction. Thus, all powers of $2$ such that $4 | n$ also satisfy the problem statement. Furthermore, we can extend this reasoning to negatives. Thus, all we have to do is manually check the cases $k = -2, -1, 0, 1, 2$. When $k = 0$, then taking $n$ prime will not result in $n | \binom{2n}{n}$ by Legendre's, so $k = 0$ satisfies the problem statement. When $k = -1$ then taking $n-1$ prime with $n$ sufficiently large will not result in $n-1 | \binom{2n}{n}$ by Legendre's, so $k = -1$ satisfies the problem statement. The $k = -2$ case works similarly to $k = -1$ and $k = 0$ and thus satisfies the problem statement. When $k = 1$, then $n+1 | \binom{2n}{n}$ since $\frac{\binom{2n}{n}}{n+1}$ is a Catalan number and thus an integer. Finally, when $k = 2$, consider $n = 2^x-2$ for a sufficiently large $x$: it's easy to see that for $1 \le a \le x$, $\lfloor \frac{2n}{2^a} \rfloor - 2 \lfloor \frac{n}{2^a} \rfloor$ is either $0$ or $1$. By Legendre's, $v_2(\binom{2n}{n}) = \sum_{a=1}^n \left(\lfloor \frac{2n}{2^a} \rfloor - 2 \lfloor \frac{n}{2^a} \rfloor \right)$ and for $n+2 = 2^x | \binom{2n}{n}$ we need $x \le \sum_{a=1}^n \left(\lfloor \frac{2n}{2^a} \rfloor - 2 \lfloor \frac{n}{2^a} \rfloor \right)$ and thus $\left(\lfloor \frac{2n}{2^a} \rfloor - 2 \lfloor \frac{n}{2^a} \rfloor \right)$ must be $1$ for $1 \le a \le x$. However, $a = 1$ results in the expression equal to $0$, so $n+2$ will not divide $\binom{2n}{n}$. Thus, $k = 2$ satisfies the problem statement. We conclude the answer. $\blacksquare$
23.10.2020 12:02
The answer is all positive integers except 1.I will write my full answer below.
23.10.2020 12:26
oh no i can't use LaTeX because i'm new…… If k=1 then we have C(2n,n)/(n+1)=C(2n,n)-C(2n,n+1) is a integer,so 1 is not an answer. For k>=2,just notice a famous lemma: say v_p(n)=a if p^a|n and p^{a+1} not divides n,then for prime p and 0<=m<=n v_p(C(n,m))=(s_p(m)+s_p(n-m)-s_p(n))/(p-1),here s_p(n) is the sum of digits of n in base p. then,for k=2,we can choose n=2^a-2 then v_2(C(2n,n))=2s_2(2^a-2)-s_2(2^{a+1}-2)=a-1 so n+k=2^a not divide C(2n,n) for k=2^t(t>=2),we can choose n=2^a then v_2(C(2n,n))=2s_2(2^a)-s_2(2^(a+1))=1 then 4|2^t+2^a=n+k but 4 not divide C(2n,n) so n+k not divide C(2n,n) for k=pq,p is an odd prime,we can choose n=p^a then v_p(C(2n,n))=2s_2(p^a)-s_2(2p^a)=0 then p|pq+p^a=n+k but p not divide C(2n,n) so n+k not divide C(2n,n) so the answer is all positive integers except 1.
28.02.2021 01:33
The answer is all $k \neq 1$. Note that it is well-known (and not too hard to get with Legendre) that if $p$ is a prime and $a$ is positive, then we have: $$v_p\left(\binom{2p^a}{p^a}\right)= \begin{cases} 0& \text{if } p \neq 2\\ 1& \text{if } p=2. \end{cases}$$Suppose $k \neq -2,-1,0,1,2$, and let $p$ be some prime dividing $k$, where $p \neq 2$ unless $p$ is the only prime dividing 2. . Note that if $p=2$ then $a>1$, otherwise $a>0$. Then we can simply take $n=p^r$ for all $r>187\cdot a^{187}$. In this case, we get $v_p(n+k)=a$. But using our well-known identity shown above, we get that $v_p\left(\binom{2n}{n}\right)<a$, so there exist infinitely many positive integers $n$ not satisfying the divisibility criterion. Now suppose $k=-2$. Then we can pick $n=2^r+2$ for some $r>187^{187}$. Clearly we get $v_2(n+k)=r$, while we have by Legendre: $$v_2\left(\binom{2n}{n}\right)=\sum_{i=1}^\infty \left \lfloor \frac{2^{r+1}+4}{2^i} \right \rfloor-2\sum_{i=1}^{\infty} \left \lfloor \frac{2^r+2}{2^i} \right \rfloor.$$Since $r$ is massive, we have that for $r\geq i>2$: $$\left \lfloor \frac{2^{r+1}+4}{2^i}\right \rfloor=2^{r+1-i}=2\cdot 2^{r-i}=2\left \lfloor \frac{2^r+2}{2^i} \right \rfloor.$$Also note that for $i>r+1$, we have: $$\left \lfloor \frac{2^{r+1}+4}{2^i}\right \rfloor=2\left \lfloor \frac{2^r+2}{2^i} \right \rfloor=0.$$So in fact this expression is at most $3$, since the only time any difference can occur is if $i=1,2,r$, and when this happens the difference is at most $1$. Since $v_2(n+k)=r>3$, we conclude that all such $n$ do not satisfy the divisibility criterion. Now suppose $k=2$. Then we can pick $n=2^r-2$ for some $r>187^{187}$. Clearly we have $v_2(n+k)=r$, while by Legendre: $$v_2\left(\binom{2n}{n}\right)=\sum_{i=1}^\infty \left \lfloor \frac{2^{r+1}-4}{2^i} \right \rfloor-2\sum_{i=1}^{\infty} \left \lfloor \frac{2^r-2}{2^i} \right \rfloor.$$We note that $$\left \lfloor \frac{2^{r+1}-4}{2^i} \right \rfloor=2\left \lfloor \frac{2^r-2}{2^i} \right \rfloor$$when $i=1$ (in which case the quantities inside the floor functions are integers) and when $i \geq r+1$ (in which case both quantities are equal to zero). Further when the quantities are not equal, the LHS is at most 1 larger than the RHS. This means that: $$\sum_{i=1}^\infty \left \lfloor \frac{2^{r+1}-4}{2^i} \right \rfloor-2\sum_{i=1}^{\infty} \left \lfloor \frac{2^r-2}{2^i} \right \rfloor<r,$$so all such $n$ do not satisfy the divisibility criterion. If $k=0$ then simply let $n=p^r$ for some $r>187$. Analogous reasoning to the first case gives that the divisibility criterion is not satisfied. If $k=-1$ then let $n=199^r+1$ for some $r>187$. Note that $199$ is prime. We can verify with Legendre's that in this case we have $v_{199}\left(\binom{2n}{n}\right)=0$, while $v_{199}(n+k)>0$, so the divisibility criterion isn't satisfied. If $k=1$ then it is well-known that $n+1 \mid \binom{2n}{n}$ due to catalan numbers.
03.03.2021 10:44
See here (Theorem 1)
25.06.2022 06:05
Most of the $\nu_p$ are computed using Kummer's Theorem. We claim it is all integers $k\neq 1.$ Case 1: $k$ is a power of $2$ (or its negation) that is not $-2, 2$. Then we claim all $n= 2^m$ work for $m>1$. Notice that $\nu_2 \left( \dbinom{2^{m+1}}{2^m}\right)$ is equal to the number of carries when adding $2^m$ to itself in base $2$, and adding $10000\cdots$ and $1000\cdots$ yields one carry, but $\nu_2(n+k) \geq \min(\nu_2(n), \nu_2(k)) > 1$. So there are infinite integers that don't satisfy this for powers of $2$. Case 2: $k$ has a prime factor other than $2$, say $p$. We claim $n=p^m$ works for all $m\geq 1$. Notice that $\nu_p(n+k) \geq 1$ since both are divisible by $p$. But $\nu_p\left(\dbinom{2p^m}{p^m} \right) =0$, since adding $10000\cdots$ and $1000\cdots$ in a base greater than $2$ yields no carries. Since $n+k$ has more factors of $p$ than $\dbinom{2n}{n}$, it can't be a divisor of that. Case 3: Anything else. These are $k=-2, -1, 0, 1, 2$. Let's tackle these one by one. 1: All $n$ work, by Catalan Numbers. 0: $n=p$ works for all primes not equal to $2$, since $\nu_p(\dbinom{2p}{p}) = 0$. -1: We can let $n=2^m+1$ for $m>2$. Then $\nu_2(n+k) = m$ and $\dbinom{2^{m+1}+2}{2^{m+1}}$ only has $2$ powers of $2$, since adding $100\cdots 00 1$ to itself has 2 carries always. -2: Similarly, we let $n=2^m+2$ for $m>2$. Then $\nu_2(n+k) = m$, and $\nu_2 \left( \dbinom{2^{m+1}+4}{2^m + 2} \right) = 2$, so this again works. 2: We let $n=2^m-2$ for $m>2$. We again see that $\nu_2(n+k)=m$. This time, $\nu_2 \left( \dbinom{2^{m+1}-4}{2^m-2} \right)$ is a bit harder to find. We know that $2^m-2$ is $m-1$ ones followed by a $0$, so this will have $m-1$ carries when added to itself, and $n+k$ has $m$ powers of $2$, so all these $n$ work. We are done.
25.06.2022 09:18
The answer is only $k = 1$, which works because $\frac{1}{n+1} \binom{2n}{n}$ is the nth catalan number. First note that if $k$ is not positive, then picking $n+k$ to be a large odd prime, we see that both the numerator and denominator have $\nu_p = 1$ so $n+k$ cannot divide it. Suppose $k$ has an odd prime factor, say $p$. Then taking $n = p^z$, we have that the $\nu_p$ of the binomial coefficient is $\frac{2s_p(n) - s_p(2n)}{p-1} = 0$, so $p | n+k$ cannot divide it. So it suffices to consider the case when $k$ is a power of $2$, say $2^m$. Pick $n = 2^s - 2^m$ where $s >> m$. Then, the number $n$ in binary has $s-m$ ones followed by a bunch of zeroes, so the $\nu_2$ of the binomial coefficient is $2s_2(n) - s_2(2n) = s_2(n) = s-m$. But since $n+k = 2^s$ is supposed to divide it, this is not possible for $m \ge 1$. So indeed the only value of $k$ that works is $k = 1$, as claimed. $\blacksquare$