7
$\begingroup$

Conjecture. Assume that $(a_i)_{i = 1}^{\infty}$ is a sequence of positive integers such that $a_{n+1} \leq 1+\sum_{i = 1}^n a_i$ for sufficiently large $n$. If $A_n$ denotes the number of distinct possible values of $\pm a_1 \pm a_2 \pm \cdots \pm a_n$, $m$ denotes the number of positive integers not the sum of distinct numbers in the sequence $(a_i)_{i = 1}^{\infty}$, and $m$ is finite then $A_n = \sum_{i = 1}^n a_i-2m+1$ if $n$ is sufficiently large.

We have the following: Assume that $a_n$ is a sequence of positive integers such that $a_{n+1} \geq 1+\sum_{i = 1}^n a_i$ for all $n$. Then all the sums $\pm a_1 \pm a_2 \pm \cdots \pm a_n$ must be distinct.

But it is still possible the sums could all be distinct $\pm a_1 \pm a_2 \pm \cdots \pm a_n$ if $a_{n+1} < \sum_{i = 1}^n a_i$ for all $n$.

This question has been answered in the case $a_i = i$ in this post, where it was found that the number of distinct values that $\pm 1 \pm 2 \pm \cdots \pm n$ takes is equal to $\sum_{i = 1}^n i+1 = 1/2(2+n+n^2)$.

The condition $a_{n+1} \leq 1+\sum_{i = 1}^n a_i$ seems to be needed because of this:

(A) If $a_{n+1} = 1+\sum_{i = 1}^n a_i$ and $a_1 = 1$ it implies that $a_n = 2^{n-1}$ and so in this case $A_n-\sum_{i = 1}^n a_i = 2^n-(2^n-1) = 1$ and this is constant.

(B) If $a_{n+1} = 2+\sum_{i = 1}^n a_i$ and $a_1 = 1$ it implies that $a_1 = 1$ and $a_n = 3 \cdot 2^{n-2}$ if $n \geq 2$. Now in this case $A_n-\sum_{i = 1}^n a_i = 2^n-(1+\sum_{i = 2}^n 3 \cdot 2^{i-2}) = 2-2^{n-1}$ is not eventually constant but in this case $m$ is infinite.

Note that we do not need the condition $a_1 = 1$.

If $a_1 = 3$ and $a_{n+1} = 1+\sum_{i = 1}^n a_i$ it means that $a_n = 2^n$ if $n \geq 2$ and so $A_n-\sum_{i = 1}^n a_i = 2^n-(3+\sum_{i = 2}^n 2^i) = 1-2^n$ and this is not eventually constant. But in this case $m$ is infinite since the set of all possible values of distinct sums of numbers in the set $(3,2^2,2^3,\ldots)$ is missing $n = 2 \pmod{4}$.

Improve this question
$\endgroup$
10
  • $\begingroup$ @GHfromMO OK, thanks. I changed the condition to "It is not the case that $\gcd(a_n,a_{n+1},a_{n+2},\ldots) > 1$ if $n$ is sufficiently big." $\endgroup$ Commented Nov 10 at 17:39
  • $\begingroup$ @GHfromMO You could have $\gcd(1,3,6,9,\ldots) = 1$ but $\gcd(3,6,9,\ldots) = 3$. $\endgroup$ Commented Nov 10 at 17:47
  • 2
    $\begingroup$ You probably mean that $\gcd(a_n, a_{n+1} ,\dots)=1$ for all $n$ but use confusing double negation instead $\endgroup$ Commented Nov 10 at 17:48
  • 1
    $\begingroup$ "Moving target" type questions, where you edit the question in response to an answer, are considered bad form on MO. You should leave your question as is, accept the answer of Ilya Bogdanov (if it correctly answers what you asked), and, if you have a follow up question, ask it separately as a new question. $\endgroup$ Commented Nov 13 at 19:01
  • 1
    $\begingroup$ @SamHopkins OK, sorry about that. I will do that now. $\endgroup$ Commented Nov 13 at 19:02

2 Answers 2

Reset to default
4
$\begingroup$

The conjecture seems to be false in general.

Denote $S_n=\sum_{i=1}^n a_i$. First of all, subtracting all the alternating sums under the question from $S_n$, we immediately see that $A_n$ is just the cardinality of the set $K_n$ of all sums of subsequences in $a_1,a_2,\dots,a_n$ (i.e., of subsets in $\{a_1,a_2,\dots,a_n\}$ provided that all the $a_i$ are distinct). Further we deal with this interpretation. Notice that this set $K_n$ is always symmetric with respect to $\frac12\sum_{i=1}^n a_i$.

Now, set $a_1=2$, $a_2=3$, $a_3=4$. Then $K_3=\{0,2,3,4,5,6,7,9\}=[0,S_3]\setminus\{1,S_3-1\}$.

Assume that $a_1,\dots,a_{2n-1}$ have been already defined, and $K_{2n-1}=[0,S_{2n-1}]\setminus\{1,S_{2n-1}-1\}$. Define $a_{2n}=S_{2n-1}-2$, $a_{2n+1}=S_{2n-1}-1$. Then we have $K_{2n}=[0,2S_{2n-1}-2]\setminus\{1,S_{2n-1}-1,2S_{2n-1}-3\}=[0,S_{2n}]\setminus\{1,S_{2n-1}-1,S_{2n}-1\}$ and $K_{2n+1}=[0,3S_{2n-1}-3]\setminus\{1,S_{2n-1}-4\}=[0,3S_{2n+1}]\setminus\{1,3S_{2n+1}-1\}$,

The last expression shows that all positive interers except for $1$ are the subset sums of $(a_i)$, so that $m=1$. Moreover, it is easily seen that all the $a_i$ are distinct. However, $A_{2n}=|K_{2n}|=S_{2n}-2\neq S_{2n}-2m+1$, so the conjecture is violated for all even indices.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Why is my conjecture, for example, true with $a_n = n^k$ and $a_n = p_n$ if $p_n$ is the $n$th prime? $\endgroup$ Commented Nov 12 at 16:12
  • $\begingroup$ Perhaps, because they behave more nicely.. The crucial point is that you need, eventually, the "holes" in $K_n$ to be situated below $a_{n+1}$ (orsummertrically to those). I would expect all sequences of at most polynomial growth (under your assumptions) to satisfy this condition. $\endgroup$ Commented Nov 12 at 17:18
  • $\begingroup$ I suppose this is the question I am asking then: Find all sequences $(a_i)_{i = 1}^{\infty}$ of positive integers that satisfy this: If $A_n$ denotes the number of distinct possible values of $\pm a_1 \pm a_2 \pm \cdots \pm a_n$, $m$ denotes the number of positive integers not the sum of distinct numbers in the sequence $(a_i)_{i = 1}^{\infty}$, and $m$ is finite then $A_n = \sum_{i = 1}^n a_i-2m+1$ if $n$ is sufficiently large. $\endgroup$ Commented Nov 12 at 18:01
  • $\begingroup$ You can ask it as a separate question here at MO. Usually one post here is for one question, not for a possibly infinite series. $\endgroup$ Commented Nov 12 at 18:20
  • $\begingroup$ Also, I should say that I doubt there is a comprehensible answer to such a general question. $\endgroup$ Commented Nov 12 at 18:22
0
$\begingroup$

Let $M$ be the largest number not representable as a sum of distinct $a_k$. Although the conjecture is false in general, it still holds for sequences satisfying $a_n > a_{n - 1} + M$ for large enough $n$.

Let $S_n = \sum_{i = 1}^n a_i$. Let $D_n$ be a set of integers which can be represented as $\sum_{j = 1}^l a_{i_j}$ where $1 \le i_1 < i_2 < \cdots < i_l \le n$. All numbers greater than $M$ are elements of $D_m$ for some $m$. A certain choice of signs in $\pm a_1 \pm a_2 \cdots \pm a_n$ can be represented as $S_n - 2d$ for some $d \in D_n$. Hence $A_n = |D_n|$. $d \in D_n$ if and only if $S_n - d \in D_n$. Hence it is enough to prove that all numbers between $M$ and $\frac{S_n}{2}$ are elements of $D_n$.

Consider the case $M < d < a_n$. For large enough $n$ the sequence $a_n$ is increasing. Then the representarion $d = \sum_{j = 1}^l a_{i_j}$ contains only $a_{i_j} < a_n$. Hence $d \in D_n$.

Consider the case $a_n \le d \le \frac{S_n}{2}$. If $d = \sum_{i = 0}^t a_{n - i}$ for some $t$, then $d \in D_n$. Otherwise $d = \sum_{i = 0}^t a_{n - i} + q$ for some $t$, $q$ such that $0  < q < a_{n - t - 1}$. For large enough $n$ the sequence $a_n$ is increasing. Using $d \le \frac{S_n}{2}$ it can be shown that $t < \frac{2n}{3}$ and $a_{n - t} > M$ for large enough $n$. If $q$ is representable as $\sum_{j = 1}^l a_{i_j}$, then $a_{i_j} < a_{n - t - 1}$, $q \in D_{n - t - 1}$, $d \in D_n$. Suppose that $q$ is not representable as $\sum_{j = 1}^l a_{i_j}$. Then $q \le M$ and $d = \sum_{i = 0}^{t - 1} a_{n - i} + (a_{n - t} + q)$. From $M < a_{n - t} + q < a_{n - t + 1}$ we have $a_{n - t} + q \in D_{n - t}$. Hence $d \in D_n$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I think it is true more generally if $m$ is finite and $\lim_{n \to \infty}(A_n-\sum_{i = 1}^n a_i)$ must exist. Do you know how to prove that? Also, doesn't your proof miss cases like $a_n = p_n$ if $p_n$ denotes the $n$th prime for cases like $p_n-p_{n-1} = 2$ and I believe my conjecture is true for such sequences. $\endgroup$ Commented Nov 15 at 18:39
  • $\begingroup$ Since $p_n-p_{n-1} > M = 6$ for sufficiently large $n$ is most likely false. $\endgroup$ Commented Nov 15 at 18:49
  • $\begingroup$ @JohnC The conjecture should be true for $p_n$. As Ilya Bogdanov mentioned, it should be true for all sequences of at most polynomial growth. But I don't have a proof. $\endgroup$ Commented Nov 15 at 19:08
  • $\begingroup$ I think the conjecture is true much more generally than just "sequences of at most polynomial growth": Assume that $(a_i)_{i = 1}^{\infty}$ is a sequence of positive integers, $A_n$ denotes the number of distinct possible values of $\pm a_1 \pm a_2 \pm \cdots \pm a_n$, and $m$ denotes the number of positive integers not the sum of distinct numbers in the sequence $(a_i)_{i = 1}^{\infty}$. If $a_n$ is such that $\lim_{n \to \infty}(A_n-\sum_{i = 1}^n a_i)$ must exist and $m$ is finite then $\lim_{n \to \infty}(A_n-\sum_{i = 1}^n a_i) = 1-2m$. $\endgroup$ Commented Nov 15 at 19:12
  • $\begingroup$ And even with the proof for sequences of at most polynomial growth that still misses sequences like Fibonacci numbers, which I also believe satisfy this. $\endgroup$ Commented Nov 15 at 19:13

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.