Compfiles/Imo1997P6.lean
Explanation legend Lean4 Domain Explanation Language (L4DEL)
L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.
- L4DEL
- Lean4 Domain Explanation Language
Credit: The upstream authors and contributors retain credit for the project and mathematics. lean4-explainer only renders their pinned source and adds the separately disclosed explanation layer.
Project sources: Pinned compfiles documentation, Pinned compfiles corpus index
24 declarations, 0 contain sorry, 0 declared as axioms
International Mathematical Olympiad 1997, Problem 6
For each positive integer n, let f(n) denote the number of ways of representing n as a sum of powers of 2 with non-negative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For example, f(4) = 4, because 4 can be represented as 4, 2 + 2, 2 + 1 + 1 or 1 + 1 + 1 + 1. Prove that for any integer n ≥ 3, 2^(n²/4) < f(2^n) < 2^(n²/2).
Imports (2)
Imported by 1 file
- def
Imo1997P6.fDocumented declaration: f line 38 sourceSource documentation
f nis the number of ways of representingnas a sum of powers of two with non-negative integer exponents, where representations that differ only in the order of their summands are considered the same. Rather than definingfas a cardinality, we define it directly through its classical recurrence: a representation of an odd number2m + 1must use a1, hencef (2m + 1) = f (2m); a representation of2m + 2either uses a1(and deleting it gives a representation of2m + 1) or does not (and halving every summand gives a representation ofm + 1), hencef (2m + 2) = f (2m + 1) + f (m + 1).standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
NatProof uses:
WellFounded.Nat.fix,InvImage,LT.lt,Imo1997P6.f.match_1,Unit,OfNat.ofNat,Nat.succ,HAdd.hAdd,dite,Eq,HMod.hMod,HDiv.hDiv,Not11 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
def f : ℕ → ℕ | 0 => 1 | n + 1 => f n + if (n + 1) % 2 = 0 then f ((n + 1) / 2) else 0 termination_by n => n decreasing_by all_goals lia snip begin /-- Unfolding equation for the recursive definition. -/
- lemma
Imo1997P6.f_succUnfolding equation for the recursive definition line 47 sourceSource documentation
Unfolding equation for the recursive definition.
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Eq, Imo1997P6.f,HAdd.hAdd,OfNat.ofNat,ite,HMod.hMod,HDiv.hDivProof uses:
of_eq_true,Eq.trans,True,congrFun',congrArg,Imo1997P6.f.eq_2,eq_self16 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
lemma f_succ (n : ℕ) : f (n + 1) = f n + if (n + 1) % 2 = 0 then f ((n + 1) / 2) else 0 := by …Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_oddA representation of an odd number must contain a1line 52 sourceSource documentation
A representation of an odd number must contain a
1.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Eq, Imo1997P6.f,HAdd.hAdd,HMul.hMul,OfNat.ofNatProof uses:
Eq.mpr,ite,HMod.hMod,HDiv.hDiv,id,congrArg, Imo1997P6.f_succ,ite_eq_right,add_zero,Eq.refl22 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
lemma f_odd (m : ℕ) : f (2 * m + 1) = f (2 * m) := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_evenThe recurrence at even arguments line 56 sourceSource documentation
The recurrence at even arguments.
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Eq, Imo1997P6.f,HAdd.hAdd,HMul.hMul,OfNat.ofNatProof uses:
Eq.mpr,ite,HMod.hMod,HDiv.hDiv,id,congrArg, Imo1997P6.f_succ,add_assoc,Nat.add_mod_right,Nat.mul_mod_right,ite_eq_left,rfl,HAdd,Eq.rec,Eq.refl18 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma f_even (m : ℕ) : f (2 * m + 2) = f (2 * m + 1) + f (m + 1) := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_even'The recurrence at even arguments, shifted form line 62 sourceSource documentation
The recurrence at even arguments, shifted form.
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,Eq, Imo1997P6.f,HMul.hMul,HAdd.hAdd,HSub.hSubProof uses:
Eq.mpr,eq_of_heq,HEq,Eq.refl,HEq.refl,Eq.symm,outParam,HAdd, Imo1997P6.f_even21 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
lemma f_even' (m : ℕ) (hm : 1 ≤ m) : f (2 * m) = f (2 * m - 1) + f m := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_zeroline 65 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, Imo1997P6.f,OfNat.ofNatProof uses:
of_eq_true,Eq.trans,True,congrFun',congrArg,Imo1997P6.f.eq_1,eq_self2 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- lemma
Imo1997P6.f_oneline 67 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, Imo1997P6.f,OfNat.ofNatProof uses:
Eq.mpr,HMul.hMul,id,congrArg,HAdd.hAdd, Imo1997P6.f_odd, Imo1997P6.f_zero6 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
- lemma
Imo1997P6.f_twoline 71 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, Imo1997P6.f,OfNat.ofNatProof uses:
Eq.mpr,HAdd.hAdd,HMul.hMul,id,congrArg, Imo1997P6.f_even, Imo1997P6.f_one,Eq.refl6 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- lemma
Imo1997P6.f_threeline 74 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, Imo1997P6.f,OfNat.ofNatProof uses:
Eq.mpr,HMul.hMul,id,congrArg,HAdd.hAdd, Imo1997P6.f_odd, Imo1997P6.f_two6 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
- lemma
Imo1997P6.f_fourline 78 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Eq,Nat, Imo1997P6.f,OfNat.ofNatProof uses:
Eq.mpr,HAdd.hAdd,HMul.hMul,id,congrArg, Imo1997P6.f_even, Imo1997P6.f_three, Imo1997P6.f_two,Eq.refl6 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
- lemma
Imo1997P6.f_monofis monotone nondecreasing line 82 sourceSource documentation
fis monotone nondecreasing.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Monotone,Nat, Imo1997P6.fProof uses:
monotone_nat_of_le_succ,Eq.mpr,LE.le,HAdd.hAdd,OfNat.ofNat,ite,Eq,HMod.hMod,HDiv.hDiv,id,congrArg, Imo1997P6.f_succ,Nat.le_add_right11 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma f_mono : Monotone f := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_sumIterating the recurrence givesf (2N)as a sum of values offline 88 sourceSource documentation
Iterating the recurrence gives
f (2N)as a sum of values off.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,Eq, Imo1997P6.f,HMul.hMul,OfNat.ofNat,Finset.sum,Finset.range,HAdd.hAddProof uses:
Nat.recAux,of_eq_true,Eq.trans,True,congr,congrArg,MulZeroClass.mul_zero, Imo1997P6.f_zero,Singleton.singleton,Finset,congrFun',zero_add,Finset.sum_singleton,eq_self,Eq.mpr,id,mul_add,mul_one, Imo1997P6.f_even, Imo1997P6.f_odd and 3 more28 instances, coercions and auxiliary constants left out.
Tactic trace: 4 steps
Open to load the checked before-and-after goal states.
lemma f_sum (N : ℕ) : f (2 * N) = ∑ i ∈ Finset.range (N + 1), f i := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_two_mul_ltThe upper-bound engine:f (2m)is strictly less than(m + 1) * f mas soon asm ≥ 2(the termf 0 = 1 < f mmakes the inequality strict) line 97 sourceSource documentation
The upper-bound engine:
f (2m)is strictly less than(m + 1) * f mas soon asm ≥ 2(the termf 0 = 1 < f mmakes the inequality strict).standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,LT.lt, Imo1997P6.f,HMul.hMul,HAdd.hAddProof uses:
Eq,Finset.sum,Finset.range,Eq.mpr,HSMul.hSMul,Finset.card,id,congrArg,Finset.sum_const,Finset.card_range,smul_eq_mul,Eq.refl, Imo1997P6.f_sum,Finset.sum_lt_sum,Membership.mem,Finset, Imo1997P6.f_mono,Nat.le_of_lt_succ,Iff.mp,Nat.succand 10 more68 instances, coercions and auxiliary constants left out.
Tactic trace: 9 steps
Open to load the checked before-and-after goal states.
lemma f_two_mul_lt (m : ℕ) (hm : 2 ≤ m) : f (2 * m) < (m + 1) * f m := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_pair_stepThe key pairing inequality for the lower bound: the pairsf k + f (2r + 1 - k)are nonincreasing inkfor1 ≤ k ≤ rline 110 sourceSource documentation
The key pairing inequality for the lower bound: the pairs
f k + f (2r + 1 - k)are nonincreasing inkfor1 ≤ k ≤ r.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,LT.lt,HAdd.hAdd, Imo1997P6.f,HSub.hSub,HMul.hMulProof uses:
Even,Odd,Or,Nat.even_or_odd,Eq,Eq.mpr,id,congrArg,Eq.symm,two_mul, Imo1997P6.f_odd,Nat.mul_sub,le_refl, Imo1997P6.f_even,Nat.add_sub_add_right,Nat.sub_add_eq, Imo1997P6.f_even', Imo1997P6.f_mono43 instances, coercions and auxiliary constants left out.
Tactic trace: 10 steps
Open to load the checked before-and-after goal states.
lemma f_pair_step (r k : ℕ) (hk : 1 ≤ k) (hkr : k < r) : f (k + 1) + f (2 * r - k) ≤ f k + f (2 * r + 1 - k) := by …Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_pair_geEvery pair in the sum is at least2 * f rline 121 sourceSource documentation
Every pair in the sum is at least
2 * f r.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,HMul.hMul, Imo1997P6.f,HAdd.hAdd,HSub.hSubProof uses:
Nat.recAux,Eq.mpr,id,Eq,congrArg,Nat.sub_zero,Nat.sub_add_comm,Nat.le_mul_of_pos_left,zero_lt_two,two_mul,Nat.add_sub_self_right,propext,Nat.add_le_add_iff_left, Imo1997P6.f_mono,Nat.le_add_right, Imo1997P6.f_pair_step,Trans.trans,rfl,Nat.le_of_succ_le,Eq.mpand 6 more39 instances, coercions and auxiliary constants left out.
Tactic trace: 17 steps
Open to load the checked before-and-after goal states.
lemma f_pair_ge (r k : ℕ) (hk : 1 ≤ k) (hkr : k ≤ r) : 2 * f r ≤ f k + f (2 * r + 1 - k) := by …Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_sum_pairThe lemma `f 1 + f 2 + line 144 sourceSource documentation
The lemma
f 1 + f 2 + ... + f (2r) ≥ 2r * f rof the official solution.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,HMul.hMul, Imo1997P6.f,Finset.sum,Finset.range,HAdd.hAddProof uses:
Eq,Eq.mpr,id,congrArg,two_mul,Finset.sum_range_add,Eq.refl,HSub.hSub,Eq.rec,Eq.trans,Eq.symm,Finset.sum_range_reflect,Finset.sum_congr,rfl,Finset,Membership.mem,LT.lt,Iff.mp,Finset.mem_range,Finset.sum_add_distriband 26 more56 instances, coercions and auxiliary constants left out.
Tactic trace: 19 steps
Open to load the checked before-and-after goal states.
lemma f_sum_pair (r : ℕ) (hr : 1 ≤ r) : 2 * r * f r ≤ ∑ i ∈ Finset.range (2 * r), f (i + 1) := by …Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_lower_stepThe two-step lower-bound recurrence:f (2^(n+1)) > 2^n * f (2^(n-1))line 166 sourceSource documentation
The two-step lower-bound recurrence:
f (2^(n+1)) > 2^n * f (2^(n-1)).standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,LT.lt,HMul.hMul,HPow.hPow, Imo1997P6.f,HSub.hSub,HAdd.hAddProof uses:
Eq,Finset.sum,Finset.range, Imo1997P6.f_sum,Eq.mp,congrArg,Eq.symm,pow_succ,mul_comm, Imo1997P6.f_sum_pair,Nat.one_le_two_pow,Eq.mpr,id,Eq.rec,Eq.refl,Eq.trans,Nat.sub_add_cancel, Imo1997P6.f_zero,Finset.sum_range_succ'39 instances, coercions and auxiliary constants left out.
Tactic trace: 11 steps
Open to load the checked before-and-after goal states.
lemma f_lower_step (n : ℕ) (hn : 1 ≤ n) : 2 ^ n * f (2 ^ (n - 1)) < f (2 ^ (n + 1)) := by …Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_lower_mainThe lower bound in integer form:(f (2^n))^4 > 2^(n²), proved by two-step induction; note4 * (n + 2) + (n + 1)² = (n + 3)²line 182 sourceSource documentation
The lower bound in integer form:
(f (2^n))^4 > 2^(n²), proved by two-step induction; note4 * (n + 2) + (n + 1)² = (n + 3)².standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,LT.lt,HPow.hPow, Imo1997P6.fProof uses:
Nat.strong_induction_on,Nat.casesAuxOn,HAdd.hAdd,of_eq_true,Eq.trans,True,congr,congrArg,Mathlib.Meta.NormNum.IsNat.to_eq,Mathlib.Meta.NormNum.isNat_pow,Eq.refl,Mathlib.Meta.NormNum.isNat_ofNat,Mathlib.Meta.NormNum.isNat_add,Mathlib.Meta.NormNum.one_natPow,Mathlib.Meta.NormNum.natPow_one,congrFun', Imo1997P6.f_two,eq_true_of_decide,Bool,Bool.trueand 66 more69 instances, coercions and auxiliary constants left out.
Tactic trace: 20 steps
Open to load the checked before-and-after goal states.
lemma f_lower_main (n : ℕ) (hn : 1 ≤ n) : 2 ^ (n ^ 2) < (f (2 ^ n)) ^ 4 := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_sq_stepOne step of the upper-bound induction, in squared form line 201 sourceSource documentation
One step of the upper-bound induction, in squared form.
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,HPow.hPow, Imo1997P6.f,LT.lt,HAdd.hAddProof uses:
Trans.trans,Eq,Mathlib.Meta.NormNum.isNat_eq_true,Mathlib.Meta.NormNum.isNat_ofNat,Eq.refl,Mathlib.Meta.NormNum.isNat_pow,Mathlib.Meta.NormNum.natPow_one,Nat.pow_le_pow_right,Mathlib.Meta.NormNum.isNat_lt_true,Bool,Bool.false,HMul.hMul,Eq.mpr,id,congrArg,pow_succ,mul_comm, Imo1997P6.f_two_mul_lt,Nat.pow_lt_pow_left,Mathlib.Meta.NormNum.isNat_eq_falseand 52 more61 instances, coercions and auxiliary constants left out.
Tactic trace: 32 steps
Open to load the checked before-and-after goal states.
lemma f_sq_step (n : ℕ) (hn : 2 ≤ n) (ih : (f (2 ^ n)) ^ 2 ≤ 2 ^ (n ^ 2)) : (f (2 ^ (n + 1))) ^ 2 < 2 ^ ((n + 1) ^ 2) := by …Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_sq_leThe upper bound in integer form, nonstrict version (for the induction) line 235 sourceSource documentation
The upper bound in integer form, nonstrict version (for the induction).
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,HPow.hPow, Imo1997P6.fProof uses:
Nat.le_induction,of_eq_true,Eq.trans,True,congr,congrArg,congrFun',Mathlib.Meta.NormNum.IsNat.to_eq,Mathlib.Meta.NormNum.isNat_pow,Eq.refl,Mathlib.Meta.NormNum.isNat_ofNat,Mathlib.Meta.NormNum.IsNatPowT.run,Mathlib.Meta.NormNum.IsNatPowT.bit0, Imo1997P6.f_four,Mathlib.Meta.NormNum.IsNatPowT.trans,Eq,Nat.pow,eq_true,True.intro,le_of_ltand 2 more19 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma f_sq_le (n : ℕ) (hn : 2 ≤ n) : (f (2 ^ n)) ^ 2 ≤ 2 ^ (n ^ 2) := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_sq_ltThe upper bound in integer form, strict forn ≥ 3line 241 sourceSource documentation
The upper bound in integer form, strict for
n ≥ 3.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,LT.lt,HPow.hPow, Imo1997P6.fProof uses:
HAdd.hAdd,HSub.hSub, Imo1997P6.f_sq_step,Nat.le_sub_one_of_lt, Imo1997P6.f_sq_le,Eq.mp,congrArg,Nat.sub_add_cancel19 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma f_sq_lt (n : ℕ) (hn : 3 ≤ n) : (f (2 ^ n)) ^ 2 < 2 ^ (n ^ 2) := by …
Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_gt_lowerThe lower bound with real powers:2^(n²/4) < f (2^n)line 246 sourceSource documentation
The lower bound with real powers:
2^(n²/4) < f (2^n).standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,LT.lt,Real,HPow.hPow,HDiv.hDiv, Imo1997P6.fProof uses: Imo1997P6.f_lower_main,
cast,Eq.symm,Eq.trans,congr,congrArg,Eq,Eq.mpr,id,Real.rpow_natCast,HMul.hMul,Real.rpow_mul,Mathlib.Meta.NormNum.isNat_le_true,Mathlib.Meta.NormNum.isNat_ofNat,Nat.cast_zero,Eq.refl,Mathlib.Meta.NormNum.instAtLeastTwo,Bool,Bool.true,HPowand 47 more91 instances, coercions and auxiliary constants left out.
Tactic trace: 16 steps
Open to load the checked before-and-after goal states.
lemma f_gt_lower (n : ℕ) (hn : 3 ≤ n) : (2 : ℝ) ^ ((n : ℝ) ^ 2 / 4) < (f (2 ^ n) : ℝ) := by …Mentions: Imo1997P6.f
- lemma
Imo1997P6.f_lt_upperThe upper bound with real powers:f (2^n) < 2^(n²/2)line 265 sourceSource documentation
The upper bound with real powers:
f (2^n) < 2^(n²/2).standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,LT.lt,Real, Imo1997P6.f,HPow.hPow,HDiv.hDivProof uses: Imo1997P6.f_sq_lt,
cast,Eq.symm,Eq.trans,congr,congrArg,Eq,Eq.mpr,id,Real.rpow_natCast,HMul.hMul,Real.rpow_mul,Mathlib.Meta.NormNum.isNat_le_true,Mathlib.Meta.NormNum.isNat_ofNat,Nat.cast_zero,Eq.refl,Mathlib.Meta.NormNum.instAtLeastTwo,Bool,Bool.true,HPowand 52 more91 instances, coercions and auxiliary constants left out.
Tactic trace: 15 steps
Open to load the checked before-and-after goal states.
lemma f_lt_upper (n : ℕ) (hn : 3 ≤ n) : (f (2 ^ n) : ℝ) < (2 : ℝ) ^ ((n : ℝ) ^ 2 / 2) := by …Mentions: Imo1997P6.f
- problem
Imo1997P6.imo1997_p6line 285 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LE.le,OfNat.ofNat,And,LT.lt,Real,HPow.hPow,HDiv.hDiv, Imo1997P6.fProof uses:
And.intro, Imo1997P6.f_gt_lower, Imo1997P6.f_lt_upper34 instances, coercions and auxiliary constants left out.