わかりました、私はクヌースの具体的な数学に苦労しており、まだ理解していない例がいくつかあります.
J(n) = 2*J(n/2) - 1
第一章からです。具体的には、具体的な数学に精通している可能性のある人のために、ヨセフス問題を解決します。解決策はありますが、説明はまったくありません。イテレーション法で解いてみました。これがこれまでに思いついたものです
J(n) = (2^k)*J(n/(2^k)) - (2^k - 1)
そして、私はここで立ち往生しています。ヘルプやヒントをいただければ幸いです。
いくつかの簡単な例から始めて推測し、帰納法を使用してその推測を (反証) 証明します。
n = 2 の累乗と考えてください。
J(2^0) = 1 (与えられた)
J(2^1) = 2J(2^0) - 1 = 1
J(2^2) = 2J(2^1) - 1 = 1
さて、すべての n >= 1 に対して J(n) = 1 と推測しましょう。
基本ケース: J(1) = 1、これは定義上真です。
誘導ステップ: 任意の k に対して J(k) = 1 と仮定します。J(2k) = 2J(k) - 1 = 1 です。
したがって、帰納法により、すべての n に対して J(n) = 1 になります (除算が整数に切り捨てられると仮定します)。