How many closed paths with the operations $+1$, $-1$, and $\times 2$?

Question

Consider a finite sequence of $n$ integers denoted $x_1,x_2,...,x_n$ where $x_1=x_n=0$ and $x_{n+1}$ is either equal to $x_n+1$, $x_n-1$ or $2x_n$. Is there a good way to count how many such sequences there are, with either an exact or asymptotic formula?

Phrased differently, if you start with the number $0$ and are allowed to add one to your number, subtract one from your number, or double your number $n$ times, how many ways can you end up back at $0$? Is there a good approximate/asymptotic formula for this in terms of $n$?

I have no idea how to start solving this. It would be nice to find some sort of generating function, but I’m not sure how to set one up.

Answer 1

It has (kinda) exponential growth.

Let $f_n$ be the number of solutions. Then, it is easy to see that $$f_{m+n-1}\geq f_n\cdot f_m$$

Indeed, if $x_1,.., x_n$ is a solution for $n$ and $y_1,.., y_m$ is a solution for $m$ then $$x_1,...,x_n,y_2,.., y_m$$ is a solution for $m+n-1$.

From here, you get that $$f_{n+2}\geq f_3 f_n= 3f_n$$

Hence, $$f_{2n}\geq 3^{n-1} f_2 =\frac{1}{3} \cdot (\sqrt{3})^{2n} \\ f_{2n+1}\geq 3^n f_1=\frac{1}{\sqrt{3}} \cdot (\sqrt{3})^{2n+1}$$

Also note that at each step there are at most 3 choices, therefore $$f_n \leq 3^{n-1}$$

From here, it follows that $$\frac{1}{3} \cdot (\sqrt{3})^{n} \leq f_n \leq \frac{1}{3} \cdot 3^n$$

Extra Same way, for each fixed $k$ we have $$f_{n+k-1} \geq f_n \cdot f_k$$ giving $$f_n \geq C (\sqrt[k-1]{f_k})^n$$

Note that $$\sqrt[6]{83}~2.088 \sqrt[7]{177}~2.095$$

Added Note that the equation $$f_{m+n-1}\geq f_n\cdot f_m$$ implies that $$g(m+n) \leq g(m)+g(n)$$ where $g(n)=- \ln(f(n+1))$.

Then, by Fekete's Subadditive Lemma the limit

$$l= \lim_n \frac{g(n)}{n}$$ exists and $l=\inf\frac{g(n)}{n}$.

Note that this gives that $$\lim_n \frac{\ln(f(n+1))}{n}=-l \\ \lim_n \ln(f(n+1)^{\frac{1}{n}})=-l \\ \lim_n f(n+1)^{\frac{1}{n}}=e^{-l}\\ \lim_n\sqrt[n]{ \frac{f(n+1)}{e^{-l}} }=1$$ meaning that the $b$ in your formula must be $e^-l$.

This show that asymptotically, in some sense, $f_n \simeq e^{-l}$. But it is not clear if you can get some $a$ so that, in a stronger sense $f_n\simeq ae^{-l}$.

As for finding the $l$, Fekete's Subadditive Lemma tells you exatly what it is, but I would be surprised if we can calculate it explicitely.

Note that $$l=\inf\frac{g(n)}{n} \Rightarrow l=\inf \frac{- \ln(f(n+1))}{n} \Rightarrow -l=\sup \ln(f(n+1)^\frac{1}{n}) \Rightarrow e^{-l}=\sup \sqrt[n]{f(n+1)}$$

Answer 2

Actually, we can set a function and try to find a formula. Though I haven't finished, I hope it will inspire you guys.

Let a function $f_{n} \left(x\right)$ mean that the number of ways to take $n$ steps from $x$ to $0$, which each step can only be $\boxed{+1}$, $\boxed{-1}$ and $\boxed{\times2}$ from the previous term. then, we get the following definition:

$1)$ $f_{n} \left(x\right)=\begin{cases} 1 & \text{when }n=0,x=0\\ 0 & \text{when }n=0,x\ne0\\ 0 & \text{when }n<0\end{cases}$

$2)$ $f_{n} \left(x\right)=f_{n} \left(-x\right)$

$3)$ $f_{n+1} \left(x\right)=f_{n} \left(x+1\right)+f_{n} \left(x-1\right)+f_{n} \left(2x\right)$

$4)$ Our answer is $f_n \left(0\right)$

Then, we try to generate a function $P_n \left(x\right)= \sum_{k=-\infty}^\infty f_n \left(k\right) x^k$. However, here's come the question:

$\quad P_{n+1} \left(x\right)\\=\sum_{k=-\infty}^\infty f_{n+1} \left(k\right) x^k\\ =\sum_{k=-\infty}^\infty \left[f_{n} \left(k+1\right)+f_{n} \left(k-1\right)+f_{n} \left(2k\right)\right]x^k \\=\sum_{k=-\infty}^\infty f_{n} \left(k-1\right) x^k+\sum_{k=-\infty}^\infty f_{n} \left(k+1\right) x^k+\sum_{k=-\infty}^\infty f_{n} \left(2k\right) x^k \\=x\sum_{k=-\infty}^\infty f_{n} \left(k-1\right) x^{k-1}+\dfrac{1}{x}\sum_{k=-\infty}^\infty f_{n} \left(k+1\right) x^{k+1}+\sum_{k=-\infty}^\infty f_{n} \left(2k\right) x^k \\= \left(x+\dfrac{1}{x}\right)P_n \left(x\right)+\sum_{k=-\infty}^\infty f_{n} \left(2k\right) x^k$

I can't find a way to express $f_{n} \left(2k\right)$ by $f_{n} \left(k\right)$, so I can't finish it. So, if you guys have some advices, please tell me in the comment immediately. Thank you!

Answer 3

If we restrict ourselves to sequences which stay between $A$ and $B$, we can get an exact count, and thus a lower bound for the original problem. Let $M$ be the matrix with rows and columns indexed by $\{A, A+1, \cdots, B-1,B \}$, with $M_{ij}=1$ if $j=i+1$, $i-1$ or $2i+1$, and $M_{ij}=0$ otherwise. Let $\vec{e}$ be the vector whose $0$-entry is $1$ and whose other entries are $0$. Then the number of sequences is $\vec{e}^T M^n \vec{e}$. For $n$ large, this grows like $\lambda^n$ where $\lambda$ is the largest eigenvalue of $M$.

I computed this largest eigenvalue for $A=-B$ with $5 \leq B \leq 20$ and got the following sequence, which seems to be approaching a limit around 2.3:

2.28034, 2.29867, 2.30516, 2.31369, 2.31662, 2.31967, 2.32071, 2.32196,
2.32238, 2.32282, 2.32296, 2.32313, 2.32319, 2.32325, 2.32327, 2.32329

The characteristic polynomial doesn't seem enlightening: For $(A,B) = (-10,10)$, I get

   (-1 + t) * (1 + t) * (1 - 3 t - t^2 + t^3) * (1 + 3 t - 3 t^2 - 4 t^3 + t^4 + t^5) *
   (-1 - 13 t - 6 t^2 + 53 t^3 + 21 t^4 - 76 t^5 - 21 t^6 + 44 t^7 + 8 t^8 - 11 t^9 - t^10 + t^11)

The largest root, 2.31967, is a root of the degree 11 factor.