Suppose a robot is initially placed at $0$ on the number line, and is programmed to take steps of integer length in the positive direction between $1$ and $k$, inclusive, where $k$ is a positive integer. Each step is chosen uniformly at random. Suppose a bomb awaits the robot at position $n$. What is the probability, $P(k,n)$, that the robot steps on the bomb? Also, for fixed $k$, it seems the value of $P(k,n)$ should stabilize as $n$ gets large, so what is $f(k)=\lim_{n\to\infty}P(k,n)$?
First, we know that $P(1,n)=1$. Through some preliminary work, it seems that $P(2,1)=\frac{1}{2}$, and for $n\ge 2$
$$P(2,n)=\frac{1}{2}+\sum_{i=2}^n\left(-\frac{1}{2}\right)^{n}$$
so that $f(2)=\frac{2}{3}$. Any general formulas for all $k$?
This problem is motivated by a claim I saw that at some point the beginning digits of $\pi$ sum up to $666$, the number of the beast, which made me wonder about $P(9,666)$.
You can write a recurrence relation. The general form will be $P(k,n)=\sum_{i=n-k}^{n-1}\frac 1kP(k,n-i)$ because to land on $n$ you have to land on one of the steps $n-k$ through $n-1$ and take the appropriate step next. As you will take an average step of $\frac {k+1}2$, for large $n$ the chance of landing on $n$ will be $\frac 2{k+1}$. The characteristic equation for this relation will have one root at $1$ corresponding to the constant solution $P(k,n)=\frac 2{k+1}$ and $k-1$ other roots corresponding to solutions which die away. As $666$ is many times $9$, a very reasonable approximation for the probability is $\frac 2{10}$.