19
$\begingroup$

How many sequences $a_1,a_2,a_3,\dotsc$, satisfy:
i) $a_1=0$
ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$)
iii) $a_i\neq a_j$ for $i\neq j$
iiii) $\mathbb{Z}=\{a_i\}_{i>0}$

Are the two alternating sequences the only solutions?

$a_1,a_2,a_3,..=0,1,-1,2,-2,3,-3,4,...$
or
$a_1,a_2,a_3,..=0,-1,1,-2,2,-3,...$

Is there a sequence satsifying i),iii),iiii) and ii) ($a_{n+1}=a_n-n^2$ or $a_{n+1}=a_n+n^2$) ?

  • 1
    @LLLLL: Computational evidence? You have a sequence other than these two containing all of $\mathbb{Z}$? What is your evidence?2012-02-29

2 Answers 2

4

Only uncountably many. See this link to MO.

-2

Two obvious solutions are :-

  1. 0, 1, 3, 6, 10, 15, ... an = Sigma(n-1)

  2. 0, -1, -3, -6, -10, -15, ... an = -Sigma(n-1)

Here, I am considering only one of the Formulae at a time. Either an = a(n-1) - n OR an = a(n-1) + n for all the numbers in the series. And of course, here ai != aj (for i != j)

Now, considering the solutions that you gave :

$a_1,a_2,a_3,..=0,1,−1,2,−2,3,−3,4,...$

AND

$a_1,a_2,a_3,..=0,−1,1,−2,2,−3,...$

Here, you have used both the formulae in alternate fashion, starting from either one of them and thereby getting two series.

Now, consider an = a(n-1) - n as "Going Backwards" AND

an = a(n-1) + n as "Going Forwards".

Observe one solution below :-

$0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, ...$

Here I go forward 3 times, till I reach $6$ and then toggle between going backwards and going forwards from then on. Since my first few (say r) steps were forward, it could be possible that going backwards from some ak could lead to a number which already exists in the series and thereby violating the condition ai !+ aj (For i != j). Whenever such violation occurs, I would forward once again and then try to go backwards and the process continues.

Similarly, we can also go backwards a few steps (more specifically more than 1 step), and then keep toggling. Whenever there is a violation, we go back once again and try to come forward and the process continues.

When our initial step (before toggling) is only 1 time, then we get the two solutions that you gave. And there is no conflict in any step in that case. This can be generalized to going in one direction for r times, and then toggling. This would lead to INFINITE SUCH SERIES, since r E N (Natural Numbers) which are infinite.

However, this is only one such set of infinte series. We could go in any different fashion as follows :

$0, 1, 3, 6, 2, -3, -9, ... $(Going forward till 6 and then going back)

Or it can be any other random order too.

So, the possible number of sequences that satisfy all 4 conditions would be INFINITE.

And for the answer to the second question, series satisfying an+1=an−n2 or an+1=an+n2,

Following two are again the obvious solutions :

$1. 0, 1, 5, 14, ... $(Going forward)
$2. 0, -1, -5, -14, ...$ (Going backward)

  • 0
    @EmilJeřábek: Now that's interesting. I guess I need to learn some descriptive set theory as soon as possible. Thanks for pointing this out.2012-03-02