suppose we have a markov process defined by $$P(X_{n+1} = 1+x_n | X_n = x_n) = \dfrac{0.5+x_n}{1+n}$$
Where $X_n = \sum_i^n Y_i$ where $Y_i$ are random variables taking values $0$ or $1$
I want to find the one-step transition probabilities $p_{ij} = P(X_{n+1} = j | X_n = i)$
I can see that for $j = i+1$ we have $$P(X_{n+1} = j | X_n = i) = \dfrac{0.5 + i}{1+n}$$ but I am not sure what the answer will be for $j = i$. The answer is listed as $$\dfrac{0.5+n-i}{1+n}$$ but cannot see how
There are clearly only two options: at step $n+1$, either $X_n$ is incremented by $1$, or it is not.
You have that the probability of incrementing (i.e. $i \neq j$) is $$ \frac{0.5 + i}{1+n} $$ Then the probability of no increment is $$ 1 - \frac{0.5 + i}{1+n} = \frac{1+n}{1+n} - \frac{0.5 + i}{1+n} = \frac{0.5 + n - i}{1+n} $$