AFTD Auto-Formalizing Theoretical Domains

forest_carpool_fibonacci_growth

theoremverified

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.

  1. 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.

    lines 1–4

    uses Nat.twoStepInduction, Nat.fib

    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]
  2. 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₃.

    lines 5–8

    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 h
  3. For 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.

    lines 9–15

    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))
          omega
  4. Over 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.

    lines 16–17

        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
  5. 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).

    lines 18–20

    uses Real.rpow_add, Real.rpow_one

        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
  6. 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.

    lines 21–24

    uses Nat.add_assoc

        calc
          _ = 2 * (2 : ℝ) ^ ((n : ℝ) / 2) := hexp
          _ ≤ 2 * (Nat.fib (n + 2) : ℝ) := by nlinarith
          _ ≤ _ := by simpa [Nat.add_assoc] using hr
  7. 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.

    lines 26–29

    uses Nat.exists_eq_add_of_le, Nat.add_comm, Nat.add_left_comm, Nat.add_assoc, forest_fib_rpow_shifted

    theorem 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).

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

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
See it in the graphDiscuss this resultChallenge it