# Prove that there is only one sequence which meets the following conditions

Problem statement is as follows: Given $n\geq 2$, prove that you can choose $1 \lt a_1 \lt a_2 \lt ... \lt a_n$ such that $$a_i | 1 + a_1a_2...a_{i-1}a_{i+1}...a_n$$ Prove that if and only if $n \in \{2, 3, 4\}$ the sequence is unique.

I have solved the first part. A sequence that satisfies the conditions is $a_1 = 2$, $a_i = \prod_{j \lt i}{a_j} + 1$. You can see that because all $a_i$ with $i \gt j$ are equal $1$ modulo $a_j$. As for the second one I proved that in the case $n = 2$, which seems pretty easy. But I have no clue how to continue. Any help would be appreciated.

To prove the only if direction, it suffices to find more than one sequence if $n = 5$ since these can then be extended by the method you give in the problem statement.

For $n = 5$, we have the three sequences $$a_1 = 2,a_2 = 3,a_3 = 7,a_4 = 43,a_5 = 1807$$ $$a_1 = 2,a_2 = 3,a_3 = 7,a_4 = 47,a_5 = 395$$ $$a_1 = 2,a_2 = 3,a_3 = 11,a_4 = 23,a_5 = 31$$

Thus there are at least three sequences for $n \geq 5$.

I will now prove that the sequence is unique for $n = 3$ and $n = 4$. This completes the if direction since $n = 2$ is trivial.

Note first that the given condition implies that the $a_i$ are relatively prime.

The key observation (as stated in the other answer) is the following:

The above conditions imply that for any sequence of distinct indices $i_1,...,i_k$ we have $$a_{i_1}a_{i_2}...a_{i_k} | 1 + \displaystyle\sum_{m = 1}^k a_1a_2...a_{i_m - 1}a_{i_m + 1}...a_n$$ This follows by multiplying the relations $a_{i_m}|1+a_1a_2...a_{i_m - 1}a_{i_m + 1}...a_n$.

Now I will show uniqueness if $n = 3$. Note that the above observation implies that $$a_2a_3 | 1 + a_1a_3 + a_1a_2$$ I claim that we must in fact have $a_2a_3 = 1 + a_1a_3 + a_1a_2$. This follows since if $a_2a_3 < 1 + a_1a_3 + a_1a_2$, then in fact $$2a_2a_3 \leq 1 + a_1a_3 + a_1a_2$$ which is impossible since $a_2a_3 > a_1a_3$ and $a_2a_3 > a_1a_2$.

Also $a_1 | 1 + a_2a_3 = 1 + (1 + a_1a_3 + a_1a_2) = 2 + a_1(a_2 + a_3)$. Thus $a_1 | 2$ and $a_1 = 2$.

Now the other conditions on the sequence imply $a_2 | 1 + 2a_3$ and $a_3 | 1 + 2a_2$.

Notice that we must have $a_3 = 1 + 2a_2$ as otherwise $2a_3 \leq 1 + 2a_2$ which would mean $a_3 \leq a_2$.

Then $a_2 | 1 + 2(1 + 2a_2) = 3 + 4a_2$ so that $a_2 | 3$ and we have $a_2 = 3$, $a_3 = 7$. This completes the case $n = 3$.

Now I will prove uniqueness for $n = 4$. This proof will be more complicated than for $n = 3$ as there are many more possibilities to eliminate.

By the observation made at the beginning, we have that the case $k = 3$ implies that $$a_2a_3a_4 | 1 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4$$ Now since $a_2a_3a_4$ is strictly greater than all of the summands on the other side, we have that $$3a_2a_3a_4 > 1 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4$$ Thus we have two possibilities $$2a_2a_3a_4 = 1 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4$$ or $$a_2a_3a_4 = 1 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4$$ I will proceed to eliminate the first possibility. Note that in the first possibility, we cannot have that $a_1$ is even. Additionally we see that $$a_1|1 + a_2a_3a_4 = (2 + 1 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4)/2$$ as $a_1$ is odd we get $$a_1|3 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4$$ so that $a_1|3$ and $a_1 = 3$. Using this information we see that $$2a_2a_3a_4 = 1 + 3a_2a_3 + 3a_2a_4 + 3a_3a_4 < 1 + 9a_3a_4$$ consequently we obtain that $a_2 \leq 9/2$ so $a_2 = 4$.

Plugging this back in we see that $$8a_3a_4 = 1 + 12a_3 + 12a_4 + 3a_3a_4$$ or rearranging $$a_4 = \frac{12a_3 + 1}{5a_3 - 12}$$ Combining this with $a_3 \geq 5$ we see that $a_4 \leq 61/13 < 6$, a contradiction. This proves that in fact we must have $$a_2a_3a_4 = 1 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4$$ Now, we use the fact that $a_1 | 1 + a_2a_3a_4$ to conclude that $$a_1 | 2 + a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4$$ and so $a_1 = 2$. Again we plug this is to obtain $$a_2a_3a_4 = 1 + 2a_2a_3 + 2a_2a_4 + 2a_3a_4 < 1 + 6a_3a_4$$ So we have $a_2 \leq 6$. Since $a_2$ and $a_1$ are relatively prime we get that $a_2 = 3$ or $a_2 = 5$.

Suppose that $a_2 = 5$ and plug this in to get $$5a_3a_4 = 1 + 10a_3 + 10a_4 + 2a_3a_4$$ This implies that $$a_4 = \frac{10a_3 + 1}{3a_3 - 10}$$ Combining this with the fact that $a_3 \geq 7$ ($gcd(a_1,a_3) = 1$) we see that $a_4 \leq 71/11 < 7$, a contradiction.

Thus we must have $a_2 = 3$. Plugging this in we get $$3a_3a_4 = 1 + 6a_3 + 6a_4 + 2a_3a_4$$ Thus we have $$a_4 = \frac{6a_3 + 1}{a_3 - 6}$$ which implies $a_3 \geq 7$.

If $a_3 > 7$, then $a_3$ must be at least 17 ($a_3$ is relatively prime with $2$ and $3$, and $11$ and $13$ result in $a_4$ not being an integer). But if $a_3 \geq 17$, then $a_4 \leq 103/11 < 10$, a contradiction.

Thus $a_3 = 7$ and $a_4 = 43$. This completes the proof of uniqueness if $n = 4$.

This is my approach: Multiply all the relations, we get $$\prod\limits_{i=1}^{n}{a_i} \ | \ \prod\limits_{i=1}^{n}{\left(1+\prod\limits_{j=1,j!=i}^{n}{a_j}\right)}$$ It reduces to $$\prod\limits_{i=1}^{n}{a_i} \ | \ 1+\sum\limits_{i=1}^{n}{\prod\limits_{j=1,j!=i}^{j=n}{a_j}}$$ , which means that $$\prod\limits_{i=1}^{n}{a_i} \ \le \ 1+\sum\limits_{i=1}^{n}{\prod\limits_{j=1,j!=i}^{j=n}{a_j}}$$ When $n=2,3,4$, we can show that the sequence is unique by using the above inequality. And I think you can construct two sequences for $n>4$.

• Could you write another sequence? I couldn't think of any others. Anyway, a good idea. Thank you! – thefunkyjunky Jan 6 '16 at 18:17