Consider a sequence $\{a_i\}^\infty_{i\ge1}$ of positive integers. For all positvie integers $n$ prove that there exists infinitely many positive integers $k$ such that there is no pair $(m,t)$ of positive integers where $m>n$ and $$kn+a_n=tm(m+1)+a_m$$
Problem
Source: Iran 3rd round 2017 Number theory first exam-P2
Tags: number theory, number theory with sequences, Sequence
09.08.2017 16:40
For each fixed $m > n$, we require $kn = tm(m+1) + (a_{m} - a_n)$. Order the pairs of possible $(k,t)$ by size. Then for any two consecutive pairs, $(k,t)$ and $(k',t')$, one has $(k'-k)n = (t' - t)m(m+1)$ and so $(k' - k) \geq \frac{m(m+1)}{n}$. Hence at most $\frac{n}{m(m+1)}$ of $k$'s can be attained. Summing up, we get the density of $k$'s attained is $$n \left( \frac{1}{(n+1)(n+2)} + \frac{1}{(n+2)(n+3)} + \cdots \right) = \frac{n}{n+1} < 1$$and hence infinitely many positive integers $k$ cannot be attained.
27.05.2018 09:02
fattypiggy123 , i got that "solution" too, but it's wrong. Because, since we have infinitely many $m$'s we can't just sum the densities(We can if we have finite number of $m$'s). For example, consider for all $m$, exactly one $k$ satisfies this property, like when $k=m-n$ is only one $k$ for $m$ , then density of such $k$'s is zero for all $m$ but density of all attained $k$'s is 1(because every $k$ is attained) and $0+0+\cdots =0$ is not $1$
27.05.2018 17:08
Fix some $n\in \mathbb{N}$ and assume on the contrary, the claim doesn't hold for that $n$. It means there exists integer $k_0$ , such that for all integers $k\geq k_0$ there exists a pair $(m,t)\,,\,m>n$ for which: $$kn+a_n=tm(m+1)+a_m$$ Let us estimate the number of possible values of the LHS and the RHS of the above equality, belonging to some interval, when $k,m,t$ vary. The latter number should be bigger than the former one. Let $N$ be (a big) a natural number and consider the interval $I=[k_0 n+a_n, Nn+a_n]$. We have: $$(1)\,\,\,\,\,\,\,\,\,\, \#\{k\in \mathbb{N}\mid kn+a_n\in I \}=N-k_0+1 $$On the other hand: $$\#\{t,m\in \mathbb{N}\mid m>n, tm(m+1)+a_m\in I\}\leq \#\{t,m\in \mathbb{N}\mid m>n, tm(m+1)\leq N_1 \}$$where $N_1 := Nn +a_n$. Let's estimate it. Clearly the only possible values of $m$ are $m=n,n+1,\dots, \sqrt{N_1}$. For each of them the possible values of $t$ are $t=1,2,\dots,\frac{N_1}{m(m+1)}$. Thus: $$\#\{t,m\in \mathbb{N}\mid m>n, tm(m+1)\leq N_1 \}\leq N_1 \sum_{m=n}^{\sqrt{N_1}}\frac{1}{m(m+1)}=N_1\left(\frac{1}{n}-\frac{1}{\sqrt{N}+1}\right)$$ Hence: $$\#\{t,m\in \mathbb{N}\mid m>n, tm(m+1)+a_m\in I\} \leq N+\frac{a_n}{n} -\frac{Nn+a_n}{\sqrt{N}+1}<N+a_n/n-\sqrt{N}/2 $$ Combining it with $(1)$ it follows: $$N-k_0+1<N+a_n/n-\sqrt{N}/2$$But since $n$ and $k_0$ are fixed, if we choose large enough $N$ the above inequality fails, thus we get a contradiction.
23.07.2022 08:16
for some fixed n let $b_m = a_m - a_n$ if the verdict is not correct then for every $k$ bigger than $N$ we have : $\forall k \ge N : \exists m,t : kn = t_k.m(m+1) + b_m f(k) = t_k.m(m+1) + b_m \Rightarrow f(k) - f(k+1) = n (\forall k \ge N)$ but $2m - n$ is bigger than every numbers , so $b_i$ is strictly bearish and we know $\forall m : b_m \ge 1- n$
20.03.2024 01:05
Proposed by Hooman Fattahi.