forest_carpool_fibonacci_growth
For every integer level D at least 2, its Fibonacci number is at least 2 to the power (D-2)/2.
Statement
theorem forest_carpool_fibonacci_growth (D : ℕ) (hD : 2 ≤ D) :
(2 : ℝ) ^ (((D : ℝ) - 2) / 2) ≤ (Nat.fib D : ℝ)- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- forest_carpool_envelope_expAt every positive integer level, the Fibonacci tail envelope is at most exp(-(log 2 / 4) times 2 to the power of half the level).
The proof, explained
The theorem is proved by first establishing a shifted bound, 2^(n/2) ≤ F_(n+2) for all n ∈ ℕ, using two-step induction. In the inductive step, the recurrence F_(n+4) = F_(n+2) + F_(n+3) and monotonicity F_(n+2) ≤ F_(n+3) imply 2 · F_(n+2) ≤ F_(n+4), which matches the factor of 2 gained in the exponent when advancing from n/2 to (n+2)/2. Finally, writing any level D ≥ 2 as D = n + 2 specializes the shifted bound to 2^((D-2)/2) ≤ F_D.
For the shifted inequality 2^(n/2) ≤ F_(n+2), the base case n = 0 holds: 2^(0/2) ≤ F₂. automation
We initiate a two-step induction on n. When n = 0, the inequality simplifies to 2⁰ ≤ F₂, which evaluates to 1 ≤ 1 and is verified by evaluating the Fibonacci definition.
uses
Nat.twoStepInduction,Nat.fibprivate lemma forest_fib_rpow_shifted (n : ℕ) : (2 : ℝ) ^ ((n : ℝ) / 2) ≤ (Nat.fib (n + 2) : ℝ) := by induction n using Nat.twoStepInduction with | zero => norm_num [Nat.fib]
The base case n = 1 holds: 2^(1/2) ≤ F₃.
Since 1 ≤ 2 and 1/2 ≤ 1, monotonicity of exponentiation for base 2 (via Real.rpow_le_rpow_of_exponent_le) gives 2^(1/2) ≤ 2¹ = 2. Since F₃ = 2, this establishes 2^(1/2) ≤ F₃.
uses
Real.rpow_le_rpow_of_exponent_le,Nat.fib,Real.rpow_one| one => have h := Real.rpow_le_rpow_of_exponent_le (show (1 : ℝ) ≤ 2 by norm_num) (show (1 : ℝ) / 2 ≤ 1 by norm_num) norm_num [Nat.fib, Real.rpow_one] at h ⊢ <;> exact hFor the induction step, the Fibonacci recurrence implies 2 · F_(n+2) ≤ F_(n+4). automation
By monotonicity of the Fibonacci numbers (Nat.fib_le_fib_succ), F_(n+2) ≤ F_(n+3). By the recurrence relation (Nat.fib_add_two), F_(n+4) = F_(n+2) + F_(n+3). Adding F_(n+2) to both sides yields 2 · F_(n+2) ≤ F_(n+4), which is solved by linear integer arithmetic.
uses
Nat.add_assoc,Nat.fib_le_fib_succ,Nat.fib_add_two| more n ih0 ih1 => have hn : 2 * Nat.fib (n + 2) ≤ Nat.fib (n + 4) := by have hm : Nat.fib (n + 2) ≤ Nat.fib (n + 3) := by simpa [Nat.add_assoc] using (Nat.fib_le_fib_succ (n := n + 2)) have he : Nat.fib (n + 4) = Nat.fib (n + 2) + Nat.fib (n + 3) := by simpa [Nat.add_assoc] using (Nat.fib_add_two (n := n + 2)) omegaOver the real numbers, 2 · F_(n+2) ≤ F_(n+4), and the exponent splits as (n + 2)/2 = n/2 + 1.
We cast the natural-number inequality 2 · F_(n+2) ≤ F_(n+4) to the real numbers, and simplify the exponent fraction (n + 2)/2 into n/2 + 1 using ring arithmetic.
have hr : (2 : ℝ) * (Nat.fib (n + 2) : ℝ) ≤ (Nat.fib (n + 4) : ℝ) := by exact_mod_cast hn have he : (((n + 2 : ℕ) : ℝ) / 2) = (n : ℝ) / 2 + 1 := by push_cast; ring
2^((n+2)/2) = 2 · 2^(n/2).
Using the exponent split (n + 2)/2 = n/2 + 1, Real.rpow_add factors 2^(n/2 + 1) into 2^(n/2) · 2¹. Since 2¹ = 2 by Real.rpow_one, this equals 2 · 2^(n/2).
uses
Real.rpow_add,Real.rpow_onehave hexp : (2 : ℝ) ^ (((n + 2 : ℕ) : ℝ) / 2) = 2 * (2 : ℝ) ^ ((n : ℝ) / 2) := by rw [he, Real.rpow_add (by norm_num : (0 : ℝ) < 2), Real.rpow_one] ring
The inductive step is completed: 2^((n+2)/2) ≤ F_(n+4). automation
We form a chain of inequalities: 2^((n+2)/2) = 2 · 2^(n/2) ≤ 2 · F_(n+2) ≤ F_(n+4). The first inequality scales the induction hypothesis 2^(n/2) ≤ F_(n+2) by 2 (discharged by non-linear arithmetic), and the second inequality is the real-cast Fibonacci bound.
uses
Nat.add_assoccalc _ = 2 * (2 : ℝ) ^ ((n : ℝ) / 2) := hexp _ ≤ 2 * (Nat.fib (n + 2) : ℝ) := by nlinarith _ ≤ _ := by simpa [Nat.add_assoc] using hr
For every integer level D ≥ 2, 2^((D-2)/2) ≤ F_D. automation
Since D ≥ 2, Nat.exists_eq_add_of_le allows us to write D = 2 + n for some n ∈ ℕ. Substituting D = 2 + n transforms the inequality into 2^(n/2) ≤ F_(n+2), which is closed directly by the shifted lemma forest_fib_rpow_shifted n.
uses
Nat.exists_eq_add_of_le,Nat.add_comm,Nat.add_left_comm,Nat.add_assoc,forest_fib_rpow_shiftedtheorem forest_carpool_fibonacci_growth (D : ℕ) (hD : 2 ≤ D) : (2 : ℝ) ^ (((D : ℝ) - 2) / 2) ≤ (Nat.fib D : ℝ) := by obtain ⟨n, rfl⟩ := Nat.exists_eq_add_of_le hD simpa [Nat.add_comm, Nat.add_left_comm, Nat.add_assoc] using forest_fib_rpow_shifted n
Nat.twoStepInduction- Principle of two-step mathematical induction: a property holds for all n ∈ ℕ if it holds for 0 and 1, and whenever it holds for n and n + 1, it also holds for n + 2.
Nat.fib- The Fibonacci sequence on natural numbers, defined by F₀ = 0, F₁ = 1, and F_(n+2) = F_n + F_(n+1).
Real.rpow_le_rpow_of_exponent_le- For a real base x ≥ 1, the power function x^y is non-decreasing in the exponent y: if y ≤ z, then x^y ≤ x^z.
Real.rpow_one- Any real number raised to the power 1 equals itself: x¹ = x.
Nat.fib_le_fib_succ- The Fibonacci sequence is non-decreasing: F_n ≤ F_(n+1) for all n ∈ ℕ.
Nat.fib_add_two- The Fibonacci recurrence relation: F_(n+2) = F_n + F_(n+1) for all n ∈ ℕ.
Nat.add_assoc- Addition of natural numbers is associative: (n + m) + k = n + (m + k).
Real.rpow_add- For a positive real base x > 0, exponents add under multiplication: x^(y+z) = x^y · x^z.
Nat.exists_eq_add_of_le- If m ≤ n for natural numbers, there exists a natural number k such that n = m + k.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
Nat.add_left_comm- Left-commutativity of natural addition: n + (m + k) = m + (n + k).
forest_fib_rpow_shifted- The shifted growth lemma: for all n ∈ ℕ, 2^(n/2) ≤ F_(n+2).
- Although the two-step induction generates an induction hypothesis for n + 1 (namely 2^((n+1)/2) ≤ F_(n+3)), the inductive step only requires the hypothesis for n (2^(n/2) ≤ F_(n+2)), because advancing the index by 2 matches the factor of 2 in 2^((n+2)/2) = 2 · 2^(n/2).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private lemma forest_fib_rpow_shifted (n : ℕ) : (2 : ℝ) ^ ((n : ℝ) / 2) ≤ (Nat.fib (n + 2) : ℝ) := by induction n using Nat.twoStepInduction with | zero => norm_num [Nat.fib] | one => have h := Real.rpow_le_rpow_of_exponent_le (show (1 : ℝ) ≤ 2 by norm_num) (show (1 : ℝ) / 2 ≤ 1 by norm_num) norm_num [Nat.fib, Real.rpow_one] at h ⊢ <;> exact h | more n ih0 ih1 => have hn : 2 * Nat.fib (n + 2) ≤ Nat.fib (n + 4) := by have hm : Nat.fib (n + 2) ≤ Nat.fib (n + 3) := by simpa [Nat.add_assoc] using (Nat.fib_le_fib_succ (n := n + 2)) have he : Nat.fib (n + 4) = Nat.fib (n + 2) + Nat.fib (n + 3) := by simpa [Nat.add_assoc] using (Nat.fib_add_two (n := n + 2)) omega have hr : (2 : ℝ) * (Nat.fib (n + 2) : ℝ) ≤ (Nat.fib (n + 4) : ℝ) := by exact_mod_cast hn have he : (((n + 2 : ℕ) : ℝ) / 2) = (n : ℝ) / 2 + 1 := by push_cast; ring have hexp : (2 : ℝ) ^ (((n + 2 : ℕ) : ℝ) / 2) = 2 * (2 : ℝ) ^ ((n : ℝ) / 2) := by rw [he, Real.rpow_add (by norm_num : (0 : ℝ) < 2), Real.rpow_one] ring calc _ = 2 * (2 : ℝ) ^ ((n : ℝ) / 2) := hexp _ ≤ 2 * (Nat.fib (n + 2) : ℝ) := by nlinarith _ ≤ _ := by simpa [Nat.add_assoc] using hrtheorem forest_carpool_fibonacci_growth (D : ℕ) (hD : 2 ≤ D) : (2 : ℝ) ^ (((D : ℝ) - 2) / 2) ≤ (Nat.fib D : ℝ) := by obtain ⟨n, rfl⟩ := Nat.exists_eq_add_of_le hD simpa [Nat.add_comm, Nat.add_left_comm, Nat.add_assoc] using forest_fib_rpow_shifted n