これも計算メモだ
Seven Treesの背景。
Tが二分木の領域だとして、
- Z := {1 + (-1) =} 1 + T3
- U := {1 + Z =} 2 + T3
- N := {Z - 1 = (-1)} = T3
と置く。波括弧内は、非形式的な心理的動機。
Z + Z = Z
展開予定を丸括弧、展開後を角括弧
Z + Z
= 1 + (T^3) + 1 + T^3
// X^3 = T^2 + T^4 （3-展開公式）
= 1 + [T^2 + T^4] + 1 + T^3
= (1 + T^2) + T^4 + 1 + T^3
// 1 + T^2 = T （1-縮約公式）
= [T] + T^4 + 1 + T^3
= 1 + T + T^3 + T^4
= 1 + (T + T^3) + T^4
// T + T^3 = T^2 （2-縮約公式）
= 1 + [T^2] + T^4
= 1 + (T^2 + T^4)
// T^2 + T^4 = T^3 (3-縮約公式）
= 1 + T^3
Tn + Z = Tn
n = 1
T + (1 + T^3)
= T + 1 + T^2 + T^4
// 1 + T^2 = T （1-縮約）
= T + T + T^4
// 下を参照
= T// 最後のステップの証明
T
= 1 + T^2
// 2-展開
= 1 + T + T^3
// 3-展開
= 1 + T + T^2 + T^4
= 1 + T^2 + T + T^4
// 1 + T^2 = T （1-縮約）
= T + T + T^4
一般のn
Tn + (1 + T^3)
// n-展開
= Tn-1 + Tn+1 + (1 + T^3)
= Tn+1 + (Tn-1 + (1 + T^3))
// 数学的帰納法の仮定
= Tn+1 + Tn-1
// n-縮約
= Tn
TnZ = Z
n = 1
T(1 + T^3)
= T + T^4
// 1-展開
= 1 + T^2 + T^4
// 3-縮約
= 1 + T^3
一般のn
T^n(1 + T^3)
= T^n + T^(n+3)
// n-展開
= T^(n-1) + T^(n+1) + T^(n+3)
// (n+2)-展開
= T^(n-1) + T^(n+2)
= T^(n-1)(1 + T^3)
// 数学的帰納法の仮定
= 1 + T^3
