https://spherical-harmonics.hateblo.jp/entry/Todai/2001/Bunka

[3] コインを投げる試行の結果によって，数直線上にある $2$ 点 $\mbox{A}$ ， $\mbox{B}$ を次のように動かす．

表が出た場合：点 $\mbox{A}$ の座標が点 $\mbox{B}$ の座標より大きいときは， $\mbox{A}$ と $\mbox{B}$ を共に正の方向に1動かす．そうでないときは， $\mbox{A}$ のみ正の方向に1動かす．

裏が出た場合：点 $\mbox{B}$ の座標が点 $\mbox{A}$ の座標より大きいときは， $\mbox{A}$ と $\mbox{B}$ を共に正の方向に1動かす．そうでないときは， $\mbox{B}$ のみ正の方向に1動かす．

最初 $2$ 点 $\mbox{A}$ ， $\mbox{B}$ は原点にあるものとし，上記の試行を $n$ 回繰り返して $\mbox{A}$ と $\mbox{B}$ を動かしていった結果， $\mbox{A}$ ， $\mbox{B}$ の到達した点の座標をそれぞれ $a$ ， $b$ とする．

(1) $n$ 回コインを投げたときの表裏の出方の場合の数 $2^n$ 通りのうち， $a=b$ となる場合の数を $X_n$ とおく． $X_{n+1}$ と $X_n$ の間の関係式を求めよ．

(2) $X_n$ を求めよ．

2021.01.17記
2001年(平成13年)東京大学前期-数学(理科)[6] - [別館]球面倶楽部零八式markIISR
の(1)(2)

2021.01.17記（2020.09.04記の理科[6]の略解を補足）

[解答]
(1) $n$ 回コインを投げたときの $\rm A，B$ の座標を $a_n，b_n$ とする．

$a_n$ と $b_n$ が等しいとき， $a_{n+1}$ と $b_{n+1}$ の差は $1$ となり，
$a_n$ と $b_n$ の差が $1$ となるとき， $a_{n+1}$ と $b_{n+1}$ の差は $0$ または $1$ となる．

$a_0=b_0$ により， $a_n$ と $b_n$ の差は $0$ または $1$ となる．

$a_n-b_n=-1，1$ となる場合の数を $Y_n，Z_n$ とすると対称性から $Y_n=Z_n$ であり， $X_n+Y_n+Z_n=2^n$ となる．

$X_{n+1}=Y_n+Z_n$ であるから， $X_{n+1}=2^n-X_n$ となる．

(2) $\dfrac{X_n}{2^n}=p_n$ とおくと
$2p_{n+1}=1-p_n$ となるので， $p_1=0$ から
$p_n=-\dfrac{1}{3}\Bigl(-\dfrac{1}{2}\Bigr)^{n-1}+\dfrac{1}{3}$
となり
$X_n=\dfrac{2\times (-1)^n+2^n}{3}$