Proof of COROLLARY 1, p. 604 — F_{k+2} ≥ φ^k
ProvedFibHeap.Amort.fib_add_two_ge_goldenRatio_powfibonacci-numbersgolden-ratiop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the Fibonacci numbers, , , for , and let be the golden ratio. Then for every ,
The paper calls this inequality well known; it converts the Fibonacci lower bound on tree sizes into an exponential one, and hence ranks into logarithms.
Formalization Note is Mathlib's Nat.fib and is Real.goldenRatio.
Preamble
import Mathlib
Formal statement
namespace FibHeap.Amort
theorem fib_add_two_ge_goldenRatio_pow (k : ℕ) :
Real.goldenRatio ^ k ≤ (Nat.fib (k + 2) : ℝ) := by sorry
end FibHeap.Amort
Source
Fredman and Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM 34 (1987), p. 604, proof of COROLLARY 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.