XXXV OM - III - Task 4

We toss a coin $ n $ times and record the result as a sequence $ (a_1, a_2, \ldots, a_n) $, where $ a_i = 1 $ or $ a_i = 2 $ depending on whether an eagle or a tail appeared in the $ i $-th toss. We assume $ b_j = a_1 + a_2 + \ldots + a_j $ for $ j = 1, 2, \ldots, n $, $ p(n) $ is the probability that the number $ n $ appears in the sequence $ (b_1, b_2, \ldots, b_n) $. Determine $ p(n) $ in terms of $ p(n-1) $ and $ p(n-2) $.
We directly observe that $ p(1) = \frac{1}{2} $, $ p(2) = \frac{1}{4} $. Suppose that $ n \geq 3 $. Notice that $ b_j \geq j $ for every $ j $. The number $ n $ can appear in the sequence $ (b_1, b_2, \ldots, b_n) $ in the following two cases:
1. Some term of this sequence is equal to $ n-1 $, for example, $ b_k = n-1 $ ($ k \leq n-1 $) and moreover $ a_{k+1} = 1 $,
2. Some term of this sequence is equal to $ n - 2 $, for example, $ b_r = n - 2 $ ($ r \leq n - 2 $) and moreover $ a_{r + 1} = 2 $.
The probability for the cases mentioned here is respectively $ p(n-1) \cdot \frac{1}{2} $ and $ p(n-2) \cdot \frac{1}{2} $, and these cases cannot occur simultaneously. Therefore