Problem 1781

To show that for all positive integers $k \geq 3$, we have $n_k < \left( \frac{13}{8} \right)^{k+2}$, we will use the Fibonacci sequence and properties of the set $A$ as described in the problem.

1. Define the Fibonacci Sequence:
Let $F_i$ be the Fibonacci sequence, with $F_1 = F_2 = 1$. The general term is given by:
$$F_{i+2} = F_{i+1} + F_i$$

2. **Construct the Set $A$:**
For a given $k$, consider the set $A = \{a_1, a_2, \ldots, a_{k+1}\}$ where:
$$a_i = (-1)^{k-1-i} F_{i+1} \quad \text{for} \quad i = 1, 2, \ldots, k-1$$
and
$$a_k = F_k + 1, \quad a_{k+1} = F_k + 2$$

3. **Sum of Elements in $A$:**
Calculate the sum of all elements in $A$:
$$a_1 + a_2 + \cdots + a_{k-1} + a_k + a_{k+1} = F_{k-1} + a_k + a_{k+1} = F_{k-1} + (F_k + 1) + (F_k + 2) = F_{k-1} + 2F_k + 3$$
Using the Fibonacci property $F_{k-1} + F_k = F_{k+1}$, we get:
$$F_{k-1} + 2F_k + 3 = F_{k+2} + 3$$
This suggests choosing $n = F_{k+2} + 3$.

4. Verify the First Condition:
We need to show that for every $a \in A$, there exist $x, y \in A$ such that $n_k \mid a - x - y$.

- **Case 1: $k$ is even.**
For $i = 1, 2, \ldots, k-3$:
$$a_i = a_{i+1} + a_{i+2}$$
Additionally:
$$a_{k-2} \equiv a_k + a_{k+1} \pmod{n}, \quad a_{k-1} = a_{k+1} + a_2, \quad a_k = a_{k-1} + a_1, \quad a_{k+1} = a_k + a_1$$

- **Case 2: $k$ is odd.**
For $i = 1, 2, \ldots, k-3$:
$$a_i = a_{i+1} + a_{i+2}$$
Additionally:
$$a_{k-2} \equiv a_k + a_{k+1} \pmod{n}, \quad a_{k-1} = a_k + a_1, \quad a_k = a_{k+1} + a_1, \quad a_{k+1} = a_{k-1} + a_2$$
In both cases, the first condition is satisfied.

5. Verify the Second Condition:
We need to show that there is no subset $B \subseteq A$ with $|B| \leq k$ such that $n_k \mid \sum_{b \in B} b$.

- **Base Case: $k = 3$**
For $k = 3$, $A = \{-1, 2, 3, 4\}$. No subset of 3 elements has a sum divisible by $F_5 + 3 = 8$.

- Inductive Step:
Assume the statement holds for $k-1$. Since the sum of the elements of $A$ is $0 \pmod{n}$, instead of $B$, we can consider $A \setminus B$ without changing anything. So our subset has only one of the elements $(a_{k-1}, a_k, a_{k+1}) = (F_k, F_k + 1, F_k + 2)$.

We can find the minimum and maximum of a subset with at most $k$ elements of $B$:
$$1 - F_k = -(F_{k-1} + F_{k-3} + \ldots) \leq \sum_{b \in B} b \leq (F_k + 2) + F_{k-2} + F_{k-4} + \ldots = F_{k+1} + 1$$
If $n = F_{k+2} + 3$ divides $\sum_{b \in B} b$, then $\sum_{b \in B} b$ must be 0. By the inductive step on $k-1$, $B$ can't be a subset of $\{a_1, a_2, \ldots, a_{k-2}\}$, so at least one of $F_k, F_k + 1, F_k + 2$ is in $B$. Then:
$$\sum_{b \in B} b \geq F_k - F_{k-1} - F_{k-2} - \ldots = 1 > 0$$
which gives us a contradiction. So the second condition is satisfied too.

6. Final Calculation:
Using $\phi = \frac{1 + \sqrt{5}}{2}$:
$$n_k \leq F_{k+2} + 3 < \phi^{k-3}(F_5 + 3) = 8\phi^{k-3}$$
But $8 < \phi^5$, and $\phi < \frac{13}{8}$, so:
$$n_k < \phi^{k+2} < \left( \frac{13}{8} \right)^{k+2}$$
The conclusion follows.

$\blacksquare$