9
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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 $.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.