\(N = 2K\) ［訳注: この \(K\) は入力の \(K\) と別］が偶数のとき、（例えば小さい \(N\) についての \(\mathrm{shuffle}\) の結果を眺めることで）次の性質が成り立つことが分かります。

• 連続する位置 \(2i - 1, 2i\) のペアについて、\(\mathrm{shuffle}(1, 2K)\) の実行後には \(A_{2i - 1} = 2i - 1\), \(A_{2i} = 2i\) であるか \(A_{2i - 1} = 2i\), \(A_{2i} = 2i - 1\) であるかのいずれかである。

つまり、\(\mathrm{shuffle}(1, 2K)\) は隣接要素のペアごとに独立に作動します。

これを帰納的に示します。\(N = 2\) のときは明らかです。\(N = 2K > 2\) のとき、\(\mathrm{shuffle}(1, 2K)\) を \(2\) ステップぶん展開すると、これは以下の手順からなります。

• \(\mathrm{shuffle}(1, 2K - 2)\)
• \(\mathrm{shuffle}(2, 2K - 1)\)
• \(\mathrm{shuffle}(2, 2K - 1)\)
• \(\mathrm{shuffle}(3, 2K)\)

仮定より、\(\mathrm{shuffle}(2, 2K - 1)\) は何個かのペアを入れ替えるのみであるため、中間の二つのステップは打ち消されます。残りの二つの \(\mathrm{shuffle}\) もやはり \(2i - 1, 2i\) というペアに作動するため、帰納法による証明が完結します。

\(2K > 2\) のときの \(\mathrm{shuffle}(L, L + 2K - 1)\) を「\(\mathrm{shuffle}(L, L + 2K - 3)\) を行ってから \(\mathrm{shuffle}(L + 2, L + 2K - 1)\) を行う」と定義し直すことで、任意の \(i = 1, \ldots, K\) について、\(\mathrm{shuffle}(1, 2K)\) がペア \(2i - 1, 2i\) をちょうど \({K - 1 \choose i - 1}\) 回入れ替えることが分かります。この二項係数が偶数なら \(A_i\) は \(i\) となり、奇数なら \(i\) のペアのもう一方の要素となります。ここで、\({n \choose k}\) が奇数であることの必要十分条件が \((n \& k) = k\) であることが使えます（\(\&\) はビット単位 AND）。

\(N\) が奇数の場合は、偶数の場合の手順二回に分ければ、それぞれを上のように解けます。