AFTD Auto-Formalizing Theoretical Domains

forest_carpool_fibonacci_envelope_decay

theoremverified

At every level at least four the proposed tail envelope is at least the next-level envelope plus the square of the previous-level envelope.

Statement

theorem forest_carpool_fibonacci_envelope_decay (k : ℕ) (hk : 4 ≤ k) : forest_carpool_tail_envelope (k + 1) + forest_carpool_tail_envelope (k - 1) ^ 2 ≤ forest_carpool_tail_envelope k
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • forest_carpool_tail_envelopeThe proposed one-sided discrepancy tail envelope is 3/8 at level 2 and otherwise two to the negative Fibonacci number of the level.
Used by 2

The proof, explained

The decay inequality ℰ(k + 1) + ℰ(k - 1)^2 ≤ ℰ(k) is proved by writing k = n + 4 for n ≥ 0, where the tail envelope definition simplifies to (1/2)^F_m because no relevant index equals 2. Using the Fibonacci recurrences, the exponents satisfy F_{n+5} = F_{n+4} + F_{n+3} and 2 * F_{n+3} = F_{n+4} + F_{n+1}, which allows a common factor of (1/2)^F_{n+4} to be factored out of both terms on the left. Because F_{n+3} ≥ 1 and F_{n+1} ≥ 1, the remaining factors (1/2)^F_{n+3} and (1/2)^F_{n+1} are each bounded above by 1/2. Their sum is at most 1, yielding the desired upper bound (1/2)^F_{n+4} * 1 = (1/2)^F_{n+4}.

  1. The Fibonacci numbers at offsets 3, 4, 5 satisfy their standard recurrence relations, and in particular 2 * F_{n+3} = F_{n+4} + F_{n+1}.

    The definition of the Fibonacci sequence provides F_{n+3} = F_{n+1} + F_{n+2}, F_{n+4} = F_{n+2} + F_{n+3}, and F_{n+5} = F_{n+3} + F_{n+4} using `Nat.fib_add_two`. Combining the equations for F_{n+4} and F_{n+3} shows that F_{n+4} + F_{n+1} = (F_{n+2} + F_{n+3}) + F_{n+1} = (F_{n+1} + F_{n+2}) + F_{n+3} = 2 * F_{n+3}, verified by linear integer arithmetic (`omega`).

    lines 5–11

    uses Nat.fib_add_two, Nat.add_assoc

      have f3 : Nat.fib (n + 3) = Nat.fib (n + 1) + Nat.fib (n + 2) := by
        simpa [Nat.add_assoc] using (Nat.fib_add_two (n := n + 1))
      have f4 : 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))
      have f5 : Nat.fib (n + 5) = Nat.fib (n + 3) + Nat.fib (n + 4) := by
        simpa [Nat.add_assoc] using (Nat.fib_add_two (n := n + 3))
      have fdouble : Nat.fib (n + 3) * 2 = Nat.fib (n + 4) + Nat.fib (n + 1) := by omega
  2. The powers (1/2)^F_{n+1} and (1/2)^F_{n+3} are each at most 1/2.

    Because 0 ≤ 1/2 ≤ 1 and the Fibonacci numbers F_{n+1} and F_{n+3} are non-zero for any n ∈ ℕ, applying `pow_le_of_le_one` bounds each power from above by (1/2)^1 = 1/2.

    lines 12–17

    uses pow_le_of_le_one

      have p1 : (1 / 2 : ℝ) ^ Nat.fib (n + 1) ≤ 1 / 2 := by
        apply pow_le_of_le_one (by norm_num) (by norm_num)
        simp
      have p3 : (1 / 2 : ℝ) ^ Nat.fib (n + 3) ≤ 1 / 2 := by
        apply pow_le_of_le_one (by norm_num) (by norm_num)
        simp
  3. Both (1/2)^F_{n+5} and ((1/2)^F_{n+3})^2 factor with a shared factor of (1/2)^F_{n+4}.

    Since F_{n+5} = F_{n+3} + F_{n+4}, power addition gives (1/2)^F_{n+5} = (1/2)^F_{n+4} * (1/2)^F_{n+3}. Similarly, squaring ((1/2)^F_{n+3})^2 doubles the exponent to 2 * F_{n+3} = F_{n+4} + F_{n+1}, which factors into (1/2)^F_{n+4} * (1/2)^F_{n+1}.

    lines 18–23

    uses pow_add, mul_comm, pow_mul

      have e5 : (1 / 2 : ℝ) ^ Nat.fib (n + 5) =
          (1 / 2 : ℝ) ^ Nat.fib (n + 4) * (1 / 2 : ℝ) ^ Nat.fib (n + 3) := by
        rw [f5, pow_add, mul_comm]
      have e3 : ((1 / 2 : ℝ) ^ Nat.fib (n + 3)) ^ 2 =
          (1 / 2 : ℝ) ^ Nat.fib (n + 4) * (1 / 2 : ℝ) ^ Nat.fib (n + 1) := by
        rw [← pow_mul, fdouble, pow_add]
  4. The shifted Fibonacci decay inequality (1/2)^F_{n+5} + ((1/2)^F_{n+3})^2 ≤ (1/2)^F_{n+4} holds.

    Substituting the factorizations, we factor out (1/2)^F_{n+4}, leaving the sum (1/2)^F_{n+3} + (1/2)^F_{n+1}. Since each summand is at most 1/2, their sum is bounded by 1. Multiplying this by the non-negative factor (1/2)^F_{n+4} establishes the upper bound (1/2)^F_{n+4} * 1 = (1/2)^F_{n+4}.

    lines 24–30

    uses mul_le_mul_of_nonneg_left

      rw [e5, e3]
      calc
        _ = (1 / 2 : ℝ) ^ Nat.fib (n + 4) *
            ((1 / 2 : ℝ) ^ Nat.fib (n + 3) + (1 / 2 : ℝ) ^ Nat.fib (n + 1)) := by ring
        _ ≤ (1 / 2 : ℝ) ^ Nat.fib (n + 4) * 1 :=
          mul_le_mul_of_nonneg_left (by linarith) (by positivity)
        _ = _ := by ring
  5. For every level k ≥ 4, the tail envelope satisfies the decay inequality ℰ(k + 1) + ℰ(k - 1)^2 ≤ ℰ(k).

    Since k ≥ 4, we write k = 4 + n for some n ∈ ℕ. For every level involved (k - 1 = n + 3, k = n + 4, and k + 1 = n + 5), the index is strictly greater than 2, so the definition of `forest_carpool_tail_envelope` reduces to (1/2)^F_m. The required inequality then coincides exactly with the shifted lemma `forest_carpool_fib_decay_shifted n`.

    lines 33–35

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

      obtain ⟨n, rfl⟩ := Nat.exists_eq_add_of_le hk
      simpa [forest_carpool_tail_envelope, Nat.add_comm, Nat.add_left_comm,
        Nat.add_assoc] using forest_carpool_fib_decay_shifted n
Nat.fib_add_two
The (n + 2)-th Fibonacci number is the sum of the n-th and (n + 1)-th Fibonacci numbers (F_{n+2} = F_n + F_{n+1}).
Nat.add_assoc
Addition of natural numbers is associative: (n + m) + k = n + (m + k).
pow_le_of_le_one
If 0 ≤ a ≤ 1 in an ordered monoid and n is a non-zero natural number, then a^n ≤ a.
pow_add
In a monoid, powers add under multiplication: a^(m + n) = a^m * a^n.
mul_comm
Multiplication is commutative: a * b = b * a.
pow_mul
In a monoid, iterated powering corresponds to exponent multiplication: a^(m * n) = (a^m)^n.
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality b ≤ c by a non-negative element a preserves the inequality: a * b ≤ a * c.
Nat.exists_eq_add_of_le
If m ≤ n for natural numbers, then n = m + k for some natural number k.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.
Nat.add_left_comm
For natural numbers, the first two summands in an addition can be commuted: n + (m + k) = m + (n + k).
forest_carpool_fib_decay_shifted
For every natural number n, the decay inequality (1/2)^F_{n+5} + ((1/2)^F_{n+3})^2 ≤ (1/2)^F_{n+4} holds.

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_carpool_fib_decay_shifted (n : ℕ) :    (1 / 2 : ℝ) ^ Nat.fib (n + 5) +      ((1 / 2 : ℝ) ^ Nat.fib (n + 3)) ^ 2 ≤      (1 / 2 : ℝ) ^ Nat.fib (n + 4) := by  have f3 : Nat.fib (n + 3) = Nat.fib (n + 1) + Nat.fib (n + 2) := by    simpa [Nat.add_assoc] using (Nat.fib_add_two (n := n + 1))  have f4 : 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))  have f5 : Nat.fib (n + 5) = Nat.fib (n + 3) + Nat.fib (n + 4) := by    simpa [Nat.add_assoc] using (Nat.fib_add_two (n := n + 3))  have fdouble : Nat.fib (n + 3) * 2 = Nat.fib (n + 4) + Nat.fib (n + 1) := by omega  have p1 : (1 / 2 : ℝ) ^ Nat.fib (n + 1) ≤ 1 / 2 := by    apply pow_le_of_le_one (by norm_num) (by norm_num)    simp  have p3 : (1 / 2 : ℝ) ^ Nat.fib (n + 3) ≤ 1 / 2 := by    apply pow_le_of_le_one (by norm_num) (by norm_num)    simp  have e5 : (1 / 2 : ℝ) ^ Nat.fib (n + 5) =      (1 / 2 : ℝ) ^ Nat.fib (n + 4) * (1 / 2 : ℝ) ^ Nat.fib (n + 3) := by    rw [f5, pow_add, mul_comm]  have e3 : ((1 / 2 : ℝ) ^ Nat.fib (n + 3)) ^ 2 =      (1 / 2 : ℝ) ^ Nat.fib (n + 4) * (1 / 2 : ℝ) ^ Nat.fib (n + 1) := by    rw [← pow_mul, fdouble, pow_add]  rw [e5, e3]  calc    _ = (1 / 2 : ℝ) ^ Nat.fib (n + 4) *        ((1 / 2 : ℝ) ^ Nat.fib (n + 3) + (1 / 2 : ℝ) ^ Nat.fib (n + 1)) := by ring    _ ≤ (1 / 2 : ℝ) ^ Nat.fib (n + 4) * 1 :=      mul_le_mul_of_nonneg_left (by linarith) (by positivity)    _ = _ := by ringtheorem forest_carpool_fibonacci_envelope_decay (k : ℕ) (hk : 4 ≤ k) : forest_carpool_tail_envelope (k + 1) + forest_carpool_tail_envelope (k - 1) ^ 2 ≤ forest_carpool_tail_envelope k := by  obtain ⟨n, rfl⟩ := Nat.exists_eq_add_of_le hk  simpa [forest_carpool_tail_envelope, Nat.add_comm, Nat.add_left_comm,    Nat.add_assoc] using forest_carpool_fib_decay_shifted n
See it in the graphDiscuss this resultChallenge it