forest_carpool_fibonacci_envelope_decay
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
- forest_greedy_merge_large_levelsTwo independent enveloped laws remain within the Fibonacci tail envelope after a greedy step at every integer level at least four.
- forest_greedy_envelope_preserved_by_independent_mergeIndependent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step…
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}.
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`).
uses
Nat.fib_add_two,Nat.add_assochave 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
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.
uses
pow_le_of_le_onehave 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
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}.
uses
pow_add,mul_comm,pow_mulhave 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]
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}.
uses
mul_le_mul_of_nonneg_leftrw [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
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`.
uses
Nat.exists_eq_add_of_le,forest_carpool_fib_decay_shifted,Nat.add_comm,Nat.add_left_comm,Nat.add_assocobtain ⟨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.
- In line 11, `omega` verifies the identity 2 * F_{n+3} = F_{n+4} + F_{n+1} automatically from the three Fibonacci recurrence equations via Presburger arithmetic.
- In lines 34–35, `simpa` simplifies the index arithmetic (such as 4 + n - 1 = n + 3) and simplifies the piecewise definition of `forest_carpool_tail_envelope`, recognizing that n + 3, n + 4, n + 5 are never equal to 2 for any natural number n.
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_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