# Sequences $a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$

Consider the number $N(k)$ of sequences with $k$ terms $a_1,a_2,\dotsc,a_k$ satisfying $a_1=0$, ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$), and $a_i\neq a_j$ for $i\neq j$. How to prove that $\lim_{k\to\infty} \ln N(k)/k=1/2$?

Alternately, is there a heuristic argument for this conjecture?

Is there any chance of a reccurence relation, closed form or asymptotics for N(k)?

This is OEIS sequence A175941.

-
The first statement, $\lim_{k\to\infty} \ln N(k)/k=1/2$, is well-defined. The second one, $N(k)\rightarrow\sqrt{\mathrm e}^k$, isn't, and when interpreted as $N(k)\sim\sqrt{\mathrm e}^k$ it means something else. The equivalent of the first statement would be $N(k)\sim a\sqrt{\mathrm e}^k$ with $a\in\mathbb R^+$. – joriki Feb 18 '12 at 16:50
@Joriki: Careful, that last part isn't true. The equivalent of the first would be $N(k)\sim \sqrt{e}^k e^{f(k)}$ for some function $f(k)=o(k)$. For example, if $N(k)=\sqrt{e}^k e^{\sqrt{k}}$, then we still have $\log(N(k))/k\rightarrow \frac{1}{2}$ as $k\rightarrow \infty$. – Eric Naslund Feb 18 '12 at 17:11
The OEIS sequence is indexed by the number of steps; yours is indexed by the number of terms. – joriki Feb 18 '12 at 17:17
@Eric: Thanks, I didn't think about that carefully enough. – joriki Feb 18 '12 at 17:18

Here's numerical evidence against that conjecture (with the numbering as in your question, shifted by one with respect to the OEIS sequence). Here $R(k)=N(k)/N(k-1)$. This factor is systematically above $\sqrt{\mathrm e}$ for $k\ge26$. If it tends to a limit that has a closed form, a more likely guess is $5/3$, with $\log 5/3\approx0.5108$.

$$\begin{array}{r|r} k&N(k)&\log R(k)&\log N(k)/k\\\hline 1&1&&0.000000\\ 2&2&0.693147&0.346574\\ 3&4&0.693147&0.462098\\ 4&6&0.405465&0.447940\\ 5&10&0.510826&0.460517\\ 6&18&0.587787&0.481729\\ 7&30&0.510826&0.485885\\ 8&50&0.510826&0.489003\\ 9&78&0.444686&0.484079\\ 10&130&0.510826&0.486753\\ 11&210&0.479573&0.486101\\ 12&350&0.510826&0.488161\\ 13&586&0.515387&0.490255\\ 14&954&0.487344&0.490047\\ 15&1606&0.520838&0.492100\\ 16&2588&0.477139&0.491165\\ 17&4234&0.492262&0.491230\\ 18&6944&0.494731&0.491424\\ 19&11342&0.490635&0.491383\\ 20&18948&0.513186&0.492473\\ 21&31450&0.506701&0.493150\\ 22&52206&0.506798&0.493771\\ 23&85662&0.495212&0.493833\\ 24&141680&0.503162&0.494222\\ 25&233040&0.497639&0.494359\\ 26&385428&0.503144&0.494697\\ 27&644910&0.514756&0.495439\\ 28&1072074&0.508240&0.495897\\ 29&1783342&0.508894&0.496345\\ 30&2953094&0.504364&0.496612\\ 31&4897922&0.505958&0.496914\\ 32&8157096&0.510077&0.497325\\ 33&13571014&0.509048&0.497680\\ 34&22552212&0.507897&0.497981\\ 35&37486916&0.508159&0.498272\\ 36&62325564&0.508380&0.498552\\ 37&103508754&0.507285&0.498788\\ 38&172765524&0.512279&0.499143\\ 39&287428656&0.509039&0.499397\\ 40&479052200&0.510835&0.499683\\ 41&798944976&0.511483&0.499971\\ 42&1334245184&0.512829&0.500277\\ \end{array}$$

Here's the Java code to produce this table:

public class Question110661 {
final static int k = 42;
static int [] counts = new int [k];
static boolean [] used = new boolean [k * (k - 1) + 1];

static void recurse (int n,int an) {
if (n == k || used [an])
return;

counts [n++]++;

used [an] = true;
recurse (n,an + n);
recurse (n,an - n);
used [an] = false;
}

public static void main (String [] args) {
recurse (0,used.length / 2);

for (int n = 0;n < k;n++)
System.out.printf (java.util.Locale.ENGLISH,"%d&%d&%.6f&%.6f\\\\\n",n + 1,counts [n],n == 0 ? 0 : Math.log (counts [n] / (double) counts [n-1]),Math.log (counts [n]) / (n + 1));
}
}

-