# Find all strictly increasing sequences $\{a_k\}_{k=1}^\infty$ of positive integers such that $\frac{a_{nk}}{a_na_k} \in (1,2)$ for any $n,k>1$

Find all strictly increasing sequences $$\{a_k\}_{k=1}^\infty$$ of positive integers such that $$\frac{a_{nk}}{a_na_k} \in (1,2)$$ for any $$n,k>1$$.

Motivation

First, I was wondering about the strictly increasing sequences of real numbers such that $$\frac{a_{nk}}{a_na_k}=1$$ for any integer $$n,k\ge 1.$$ I believe all such sequences look like $$a_k=k^\alpha$$ for some $$\alpha > 0$$ (due to Erdős’ result).

Then I started changing the conditions. What if I try to find all the strictly increasing sequences such that $$\frac{a_{nk}}{a_na_k}=2$$ for any integer $$n,k>1$$. We can’t deduce $$a_1=1$$ in this case. Since $$a_1$$ never participates in $$\frac{a_{nk}}{a_na_k}=2$$ anyway, it can be any number smaller than $$a_2$$. Overall, it seems to me that virtually the same reasoning as for the previous question could be made for this case, so $$a_k=k^\alpha$$ for some positive $$\alpha$$. But then from $$\frac{a_{nk}}{a_na_k}=2$$ we get that $$1=2$$. So such sequences don’t exist.

Now, what if we try the condition $$\frac{a_{nk}}{a_na_k}\in (1,2)?$$ If we ignore the monotonicity condition then $$a_k=2/3$$ would work. So something like $$a_k={2\over3} + \frac{\sum_{i=1}^k 1/2^k}{10^{100}}$$ is fine. There is a lot of such sequences.

Then let us make $$a_k$$ positive integers, arriving to our main question.

Hypothesis

I failed to find an example of such sequence yet. My intuition tells me that if $$\frac{a_{nk}}{a_na_k}>1$$ then $$\frac{a_{nk}}{a_na_k}$$ is not bounded. My hypothesis is that no such sequence exists.

Edit

Different examples of such sequences have appeared. The hypothesis is wrong. I still wonder if all these sequences can be described in a nice way though.

• By "increasing" do you mean strictly increasing? Feb 11 at 3:02
• @GregMartin yes, strictly increasing.
– Aig
Feb 11 at 3:03
• Such sequences certainly can't be bounded, since $a_2\ge2$ and thus $a_{2^m} > 2^m$ for all $m\ge2$. Feb 11 at 3:05
• @GregMartin I meant $a_{nk}/a_na_k$ is not bounded.
– Aig
Feb 11 at 3:06
• Consider the greedy sequence, where $a_n$ is chosen to be the smallest integer greater than $a_{n-1}$ such that $a_n/a_da_{n/d} > 1$ for all nontrivial divisors $d$ of $n$. (That sequence isn't in OEIS, fwiw.) Emperically it seems that $a_n/a_da_{n/d}$ is bounded by $1.5$. The largest ratios seem to correspond to certain numbers $n$ that are just greater than powers of $4$. Feb 11 at 4:40

Let $$a_n := n^2-1$$. Then $$\dfrac{a_{xy}}{a_xa_y}\in(1, 2)$$ for $$x, y\ge2$$. In fact

Proposition. $$a_{xy} > a_xa_y$$

Proof. \begin{aligned} (xy)^2-1 &> (x^2-1)(y^2-1)&\iff\\ x^2y^2-1 &>x^2y^2-x^2-y^2+1&\iff\\ x^2+y^2&>2 \end{aligned} which holds true because $$x, y>1.~\square$$

Proposition. $$a_{xy} < 2a_xa_y$$

Proof. \begin{aligned} (xy)^2-1 &< 2(x^2-1)(y^2-1)&\iff\\ x^2y^2-1 &<2x^2y^2-2x^2-2y^2+2&\iff\\ 1 &< x^2y^2-2x^2-2y^2+4&\iff\\ 1&<(x^2-2)(y^2-2) \end{aligned} which holds true because $$x, y\ge 2.~\square$$

• Yes, $n^\alpha-m$ seems to work for any integer $\alpha \ge 2$ and $m$ small enough. Probably $m$ doesn’t have to be a constant, too. So, there is probably a lot of such sequences, built from different ideas, and they are hard to charactarize in a nice way.
– Aig
Feb 12 at 5:16
• a minor thing, $a_1$ is not a positive integer. Feb 12 at 6:03
• @Yimin we can set $a_1$ any positive integer smaller than $a_2$. Since $a_2 = 2^2-1=3$ we can take $a_1=1$ or $2$. This number $a_1$ doesn’t participate in the condition anyway. Btw, a simple example $a_n=n-1$ would work too, if we “ignore” $a_1, a_2, a_3$ in a similar way.
– Aig
Feb 12 at 7:52