ヨセフスの問題
この場合、 x {\displaystyle x} 番目の人は最初は 2 x + 1 {\displaystyle 2x+1} 番目に位置していたことになる。以上から次の漸化式が得られる。
f ( 2 n + 1 ) = 2 f ( n ) + 1 {\displaystyle f(2n+1)=2f(n)+1\,}
n {\displaystyle n} とそれに対応する f ( n ) {\displaystyle f(n)} の値を表にしてみると、次のようなパターンが出現する。
これを見ると、 f ( n ) {\displaystyle f(n)} は奇数の増加する数列であり、インデックス n が 2 のべき乗のときに f ( n ) = 1 {\displaystyle f(n)=1} にリセットされると思われる。したがって、 n = 2 m + l {\displaystyle n=2^{m}+l} かつ 0 ≤ l < 2 m {\displaystyle 0\leq l<2^{m}} となるような m と l を選択したとき、 f ( n ) = 2 ⋅ l + 1 {\displaystyle f(n)=2\cdot l+1} となる。上の表にある値は、この式に当てはまる。しかし、数学では厳密な証明が求められる。以下に帰納法による証明を示す。
定理: n = 2 m + l {\displaystyle n=2^{m}+l} かつ 0 ≤ l < 2 m {\displaystyle 0\leq l<2^{m}} なら、 f ( n ) = 2 l + 1 {\displaystyle f(n)=2l+1} である。
まず、 k = 2 {\displaystyle k=2} の場合の解法を示す( k ≠ 2 {\displaystyle k\neq 2} の場合については、概要を後述)。ここでは再帰的な解法を示す。 n {\displaystyle n} 人で始める場合の生き残り(の番号)を返す関数を f ( n ) {\displaystyle f(n)} とする( k = 2 {\displaystyle k=2} )。最初の1周で、全ての偶数番号の人が処刑される。2周目で、新たな2番目の人が処刑され、さらに新たな4番目の人が処刑され、と続く。最初の人数が偶数の場合、2周目で x {\displaystyle x} 番目の人は1周目では 2 x − 1 {\displaystyle 2x-1} 番目に位置している( x {\displaystyle x} は任意)。したがって、 f ( n ) {\displaystyle f(n)} 番目の人は最初は 2 f ( n ) − 1 {\displaystyle 2f(n)-1} 番目に位置している。このことから、次の漸化式が得られる。
f ( 2 n ) = 2 f ( n ) − 1 {\displaystyle f(2n)=2f(n)-1\,}
最初の人数が奇数の場合、1周目の最後に1番の人が処刑される。その後、2周目では新たな2番目の人が処刑され、新たな4番目の人が処刑され...と続く。