問題
は2以上の整数とする．1枚の硬貨を続けて回投げる．このとき，回目に表が出たら，裏が出たらとして，を定める．
とするとき，が奇数である確率を求めよ．
出典：京都大学 2025年度 前期日程 第2次学力試験 理系 第6問
方針
の値そのものではなく偶奇だけを追う。 回投げた列に最後の2回を追加すると考えると，追加分による偶奇の変化は末尾 と追加2回だけで決まる。追加が のときは偶奇が変わらず， の2通りでは必ず片方だけが偶奇を反転させる。これにより状態を細かく列挙せずに を得る。初期値は を直接数え，偶数番目と奇数番目に分けて同じ漸化式を解く。
解答
回投げた後の列を一つ固定し，そのときの の偶奇を考える。この列の後ろに，さらに2回の結果を付け加える。追加する2回を と書くと，新しく増える隣接積は である。
追加が または のときは なので であり， の偶奇は変わらない。この2通りは全体の確率 で起こる。
追加が または のときを見る。 では増加分は ， では増加分は である。 が のどちらであっても， と の偶奇は逆である。したがって， の2通りのうち一方だけが の偶奇を反転させ，もう一方は偶奇を保つ。
よって，固定した最初の 回の列に対して，後ろ2回の4通りを平均すると， からの寄与は「もとの が奇数である確率」の半分， からの寄与は常に である。したがって を得る。
初期値を求める。 では であり，奇数になるのは のときだけなので である。 では であり，奇数になる列は の2通りであるから である。
偶数の場合を ，奇数の場合を と分ける。どちらの場合も を満たす。そこで とおくと であるから である。したがって となる。
以上より， または のとき である。まとめると である。