AFTD Auto-Formalizing Theoretical Domains

forest_carpool_envelope_exp

theoremverified

At every positive integer level, the Fibonacci tail envelope is at most exp(-(log 2 / 4) times 2 to the power of half the level).

Statement

theorem forest_carpool_envelope_exp (D : ℕ) (hD : 1 ≤ D) :
    forest_carpool_tail_envelope D ≤
      Real.exp (-(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2))
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The proof bounds the tail envelope forest_carpool_tail_envelope(D) from above by (1/2)^(F_D) and rewrites this base-1/2 power as exp(-ln(2) * F_D). A Fibonacci growth lower bound establishes that F_D ≥ 2^(D/2) / 4 for all D ≥ 1. Multiplying this inequality by -ln 2 reverses the inequality on the exponents, and applying the monotonicity of the exponential function completes the bound.

  1. The natural logarithm of 2 is strictly positive: ln 2 > 0.

    Since 1 < 2, the strict monotonicity of the logarithm (`Real.log_pos`) gives ln 2 > 0.

    line 4

    uses Real.log_pos

      have hlog : 0 < Real.log 2 := Real.log_pos (by norm_num)
  2. The tail envelope at D is bounded above by (1/2)^(F_D), where F_D is the D-th Fibonacci number.

    Unfolding the definition of `forest_carpool_tail_envelope`, there are two cases: when D = 2, the envelope is 3/8 and F_2 = 1, so 3/8 ≤ (1/2)¹ = 1/2; when D ≠ 2, the envelope is (1/2)^(F_D) by definition, which equals itself reflexively.

    lines 5–10

    uses Nat.fib

      have hU : forest_carpool_tail_envelope D ≤ (1 / 2 : ℝ) ^ Nat.fib D := by
        unfold forest_carpool_tail_envelope
        split_ifs with h
        · subst D
          norm_num [Nat.fib]
        · rfl
  3. The power (1/2)^(F_D) can be rewritten as exp(-ln(2) * F_D).

    By the definition of real powers, (1/2)^(F_D) = exp(ln(1/2) * F_D). Since 1/2 = 2⁻¹ and ln(2⁻¹) = -ln 2, this simplifies to exp(-ln(2) * F_D).

    lines 11–17

    uses Real.rpow_natCast, Real.rpow_def_of_pos, one_div, Real.log_inv

      have hpow : (1 / 2 : ℝ) ^ Nat.fib D =
          Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := by
        calc
          _ = (1 / 2 : ℝ) ^ ((Nat.fib D : ℕ) : ℝ) := (Real.rpow_natCast _ _).symm
          _ = Real.exp (Real.log (1 / 2 : ℝ) * (Nat.fib D : ℝ)) :=
            Real.rpow_def_of_pos (by norm_num) _
          _ = _ := by rw [show Real.log (1 / 2 : ℝ) = -Real.log 2 by rw [one_div, Real.log_inv]]
  4. The quantity 2^(D/2) is non-negative: 0 ≤ 2^(D/2). automation

    Powers of positive numbers are non-negative, which is verified automatically by the `positivity` tactic.

    line 18

      have hz : 0 ≤ (2 : ℝ) ^ ((D : ℝ) / 2) := by positivity
  5. The D-th Fibonacci number satisfies 2^(D/2) / 4 ≤ F_D.

    We split into cases on D ≥ 1. If D = 1, then F_1 = 1; since 1/2 ≤ 1, monotonicity of powers yields 2^(1/2) ≤ 2¹ = 2, and therefore 2^(1/2)/4 ≤ 2/4 ≤ 1. If D ≥ 2, we invoke `forest_carpool_fibonacci_growth` to get 2^((D - 2)/2) ≤ F_D. Rewriting the exponent as (D - 2)/2 = D/2 - 1, the power becomes 2^(D/2) / 2, which is at least 2^(D/2) / 4.

    lines 19–29

    uses Real.rpow_le_rpow_of_exponent_le, Nat.fib, Real.rpow_one, forest_carpool_fibonacci_growth, Real.rpow_sub

      have hfib : (2 : ℝ) ^ ((D : ℝ) / 2) / 4 ≤ (Nat.fib D : ℝ) := by
        by_cases h1 : D = 1
        · subst D
          have hr := 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 hr ⊢ <;> linarith
        · have h2 : 2 ≤ D := by omega
          have hg := forest_carpool_fibonacci_growth D h2
          have he : (((D : ℝ) - 2) / 2) = (D : ℝ) / 2 - 1 := by ring
          rw [he, Real.rpow_sub (by norm_num : (0 : ℝ) < 2), Real.rpow_one] at hg
          linarith
  6. The exponent satisfies -ln(2) * F_D ≤ -(ln(2) / 4) * 2^(D/2).

    Multiplying 2^(D/2) / 4 ≤ F_D by the non-negative scalar ln 2 preserves the inequality, giving ln(2) * (2^(D/2) / 4) ≤ ln(2) * F_D. Negating both sides reverses the direction, yielding -ln(2) * F_D ≤ -(ln(2) / 4) * 2^(D/2), which is closed by nonlinear arithmetic.

    lines 30–32

    uses mul_le_mul_of_nonneg_left, le_of_lt

      have hmul := mul_le_mul_of_nonneg_left hfib (le_of_lt hlog)
      have hexp : -Real.log 2 * (Nat.fib D : ℝ) ≤
          -(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2) := by nlinarith
  7. The tail envelope satisfies forest_carpool_tail_envelope D ≤ exp(-(ln(2) / 4) * 2^(D/2)).

    We chain the inequalities: the tail envelope is bounded by (1/2)^(F_D), which equals exp(-ln(2) * F_D). Since exp is monotonically increasing, applying it to -ln(2) * F_D ≤ -(ln(2) / 4) * 2^(D/2) yields the desired final bound.

    lines 33–36

    uses Real.exp_le_exp.mpr

      calc
        _ ≤ (1 / 2 : ℝ) ^ Nat.fib D := hU
        _ = Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := hpow
        _ ≤ _ := Real.exp_le_exp.mpr hexp
Real.log_pos
If x > 1, then ln(x) > 0.
Nat.fib
The n-th Fibonacci number.
Real.rpow_natCast
Real exponentiation by a natural number cast to the reals agrees with standard natural-power exponentiation.
Real.rpow_def_of_pos
For x > 0 and any real y, x^y = exp(ln(x) * y).
one_div
For any invertible element a, 1 / a = a⁻¹.
Real.log_inv
For any real x, ln(x⁻¹) = -ln(x).
Real.rpow_le_rpow_of_exponent_le
For base x ≥ 1, if y ≤ z then x^y ≤ x^z.
Real.rpow_one
Any real number raised to the power 1 equals itself.
forest_carpool_fibonacci_growth
For any integer D ≥ 2, the D-th Fibonacci number satisfies 2^((D - 2) / 2) ≤ F_D.
Real.rpow_sub
For x > 0 and real numbers y and z, x^(y - z) = x^y / x^z.
mul_le_mul_of_nonneg_left
If b ≤ c and a ≥ 0, then a * b ≤ a * c.
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.
Real.exp_le_exp.mpr
The real exponential function is order-preserving: if x ≤ y, then exp(x) ≤ exp(y).

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

theorem forest_carpool_envelope_exp (D : ℕ) (hD : 1 ≤ D) :    forest_carpool_tail_envelope D ≤      Real.exp (-(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2)) := by  have hlog : 0 < Real.log 2 := Real.log_pos (by norm_num)  have hU : forest_carpool_tail_envelope D ≤ (1 / 2 : ℝ) ^ Nat.fib D := by    unfold forest_carpool_tail_envelope    split_ifs with h    · subst D      norm_num [Nat.fib]    · rfl  have hpow : (1 / 2 : ℝ) ^ Nat.fib D =      Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := by    calc      _ = (1 / 2 : ℝ) ^ ((Nat.fib D : ℕ) : ℝ) := (Real.rpow_natCast _ _).symm      _ = Real.exp (Real.log (1 / 2 : ℝ) * (Nat.fib D : ℝ)) :=        Real.rpow_def_of_pos (by norm_num) _      _ = _ := by rw [show Real.log (1 / 2 : ℝ) = -Real.log 2 by rw [one_div, Real.log_inv]]  have hz : 0 ≤ (2 : ℝ) ^ ((D : ℝ) / 2) := by positivity  have hfib : (2 : ℝ) ^ ((D : ℝ) / 2) / 4 ≤ (Nat.fib D : ℝ) := by    by_cases h1 : D = 1    · subst D      have hr := 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 hr ⊢ <;> linarith    · have h2 : 2 ≤ D := by omega      have hg := forest_carpool_fibonacci_growth D h2      have he : (((D : ℝ) - 2) / 2) = (D : ℝ) / 2 - 1 := by ring      rw [he, Real.rpow_sub (by norm_num : (0 : ℝ) < 2), Real.rpow_one] at hg      linarith  have hmul := mul_le_mul_of_nonneg_left hfib (le_of_lt hlog)  have hexp : -Real.log 2 * (Nat.fib D : ℝ) ≤      -(Real.log 2 / 4) * (2 : ℝ) ^ ((D : ℝ) / 2) := by nlinarith  calc    _ ≤ (1 / 2 : ℝ) ^ Nat.fib D := hU    _ = Real.exp (-Real.log 2 * (Nat.fib D : ℝ)) := hpow    _ ≤ _ := Real.exp_le_exp.mpr hexp
See it in the graphDiscuss this resultChallenge it