nonclairvoyant_scheduling_term_U_at_one
For every natural number n ≥ 1 and every natural number i, the sequence term nonclairvoyant_scheduling_term_U n 1 i evaluated at parameter t = 1 equals 2 * (n : ℝ) / ((n : ℝ) + 1).
Statement
theorem nonclairvoyant_scheduling_term_U_at_one (n : ℕ) (i : ℕ) (hn : 1 ≤ n) :
nonclairvoyant_scheduling_term_U n 1 i = 2 * (n : ℝ) / ((n : ℝ) + 1)- Source
- arXiv:2610.29037, Appendix C.2, Proof of Theorem 4.6 (Step 1)
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- nonclairvoyant_scheduling_term_UThe sequence U_i(t) = (2*t*n^2 + (1-t)*i*(2*n+1-i)) / (t*n*(n+1) + (1-t)*i*(i+1)) for n jobs, index i, and parameter t.
Read back from the Lean
For all natural numbers $n$ and $i$, if $1 \le n$, then nonclairvoyant_scheduling_term_U n 1 i equals $2n / (n + 1)$ (where $n$ is coerced to the real numbers).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by direct calculation. Evaluating the definition of the sequence term U_i(t) at t = 1 causes all terms containing the factor (1 - t) to vanish, eliminating the dependence on i and leaving 2n^2 / (n(n+1)). Because n ≥ 1, the parameter n is non-zero, allowing field simplification to cancel n from the numerator and denominator to produce 2n / (n+1).
Evaluating U_i(1) by definition and simplifying arithmetic reduces the left-hand side to 2n^2 / (n(n+1)).
Expanding the definition of `nonclairvoyant_scheduling_term_U` at parameter t = 1 gives (2 * 1 * n^2 + (1 - 1) * i * (2n + 1 - i)) / (1 * n * (n + 1) + (1 - 1) * i * (i + 1)). Since 1 - 1 = 0, all terms depending on i vanish, simplifying the expression to 2n^2 / (n(n+1)).
uses
nonclairvoyant_scheduling_term_Udsimp [nonclairvoyant_scheduling_term_U] simp
(n : ℝ) ≠ 0
From the assumption 1 ≤ n (hn), n is a positive natural number, so its coercion to the real numbers is non-zero. The `positivity` tactic establishes this automatically.
have : (n : ℝ) ≠ 0 := by positivity
The rational expression 2n^2 / (n(n+1)) simplifies to 2n / (n+1).
Because n ≠ 0, we can cancel a factor of n from the numerator and denominator. The `field_simp` tactic clears the common factor in ℝ to establish the equality and close the goal.
field_simp
nonclairvoyant_scheduling_term_U- The upper bound sequence term U_i(t), defined as (2 * t * n^2 + (1 - t) * i * (2n + 1 - i)) / (t * n * (n + 1) + (1 - t) * i * (i + 1)).
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.
/-- At parameter t = 1, the upper bound sequence term U_i(1) equals 2n/(n+1) for all i. -/theorem nonclairvoyant_scheduling_term_U_at_one (n : ℕ) (i : ℕ) (hn : 1 ≤ n) : nonclairvoyant_scheduling_term_U n 1 i = 2 * (n : ℝ) / ((n : ℝ) + 1) := by dsimp [nonclairvoyant_scheduling_term_U] simp have : (n : ℝ) ≠ 0 := by positivity field_simp