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.
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment