# How to manipulate this sum-product expression?

A machine randomly outputs either $$1$$ or $$2$$, each output being equally likely, and after each output we see the current sum on a screen. What is the probability that a given number $$n$$ will be displayed on the screen.

While I was doing “notes cleaning up,” I came with this problem, and saw that on the side of a paper I scribbled few test cases such as:

$$n=1, \quad \{1\}, \quad p=\frac{1}{2}$$

$$n=2, \quad \{11,2 \}, \quad p=\frac{3}{4}$$

$$n=3, \quad \{ 111,12,21\}, \quad p=\frac{5}{8}$$

(So, essentially, one counts all the cases that lead to $$n$$.) My notes further included my note that the solution should be:

$$\left( \frac{1}{2} \right)^n + \displaystyle \sum_{m=1}^n \left( \frac{1}{2} \right)^{n-m} \displaystyle \prod_{k=m}^{2k-1}(n-k)$$

1. I have extremely little experience with combinatorics problems and manipulating sums and products like the one above. Is there a way to turn the above expression into a formula so that it gives the probability for a given $$n$$? (This, I ask, irrespective of whether my solution is unnecessarily complex or not.)
2. I suspect that there should be a dynamic-programming-like approach. If I am correct, can someone give a hint about that?

The probability $$p_n$$ that some number appears follows a recurrence relation. $$n$$ can be attained from adding $$2$$ to $$n-2$$ or $$1$$ to $$n-1$$. Therefore we obtain the recurrence $$p_n = \frac{1}{2} (p_{n-1} + p_{n-2})$$. With initial values $$p_1=\frac{1}{2}, p_2=\frac{3}{4}$$, we solve the recurrence obtain the formula $$p_n=\frac{2+\left( \frac{-1}{2} \right)^n}{3}.$$