素朴な再帰の呼び出し回数

命題 4.1（「動的計画法」§4）・ ✓公理まで証明済み

$T(n)$ を、fib_naive(n) の実行中に起きる関数呼び出しの総数（最初の 1 回を含む）とする。 $n \ge 0$ に対して

T(n) = 2F_{n+1} - 1

が成り立つ。さらに $n \ge 1$ に対して $2\varphi^{n-1} - 1 \le T(n) \le 2\varphi^{n} - 1$ であり、したがって $T(n) = \Theta(\varphi^n)$ である。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。

証明で明示的に参照している定理は、まだありません。