data.nat.choose.basic | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

2f3994e1

(last sync)

a47cda96

refactor(algebra/group_with_zero/defs): use is_*cancel_mul_zero (#17963)

Diff

@@ -124,9 +124,8 @@ end
 lemma choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
   n.choose k * k.choose s = n.choose s * (n - s).choose (k - s) :=
 begin
-  have h : 0 < (n - k)! * (k - s)! * s! :=
-    mul_pos (mul_pos (factorial_pos _) (factorial_pos _)) (factorial_pos _),
-  refine eq_of_mul_eq_mul_right h _,
+  have h : (n - k)! * (k - s)! * s! ≠ 0, by apply_rules [mul_ne_zero, factorial_ne_zero],
+  refine mul_right_cancel₀ h _,
   calc
     n.choose k * k.choose s * ((n - k)! * (k - s)! * s!)
         = n.choose k * (k.choose s * s! * (k - s)!) * (n - k)!

d012cd09

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

c3291da4

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -377,7 +377,7 @@ theorem choose_le_middle (r n : ℕ) : choose n r ≤ choose n (n / 2) :=
     · apply choose_le_middle_of_le_half_left a
     · rw [← choose_symm b]
       apply choose_le_middle_of_le_half_left
-      rw [div_lt_iff_lt_mul' zero_lt_two] at h 
+      rw [div_lt_iff_lt_mul' zero_lt_two] at h
       rw [le_div_iff_mul_le' zero_lt_two, tsub_mul, tsub_le_iff_tsub_le, mul_two,
         add_tsub_cancel_right]
       exact le_of_lt h

c3291da4

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2018 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Bhavik Mehta, Stuart Presnell
 -/
-import Mathbin.Data.Nat.Factorial.Basic
+import Data.Nat.Factorial.Basic
 
 #align_import data.nat.choose.basic from "leanprover-community/mathlib"@"c3291da49cfa65f0d43b094750541c0731edc932"

c3291da4

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2018 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Bhavik Mehta, Stuart Presnell
-
-! This file was ported from Lean 3 source module data.nat.choose.basic
-! leanprover-community/mathlib commit c3291da49cfa65f0d43b094750541c0731edc932
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Nat.Factorial.Basic
 
+#align_import data.nat.choose.basic from "leanprover-community/mathlib"@"c3291da49cfa65f0d43b094750541c0731edc932"
+
 /-!
 # Binomial coefficients

c3291da4

bump to nightly-2023-06-09-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

16afdc39

Diff

@@ -195,7 +195,6 @@ theorem choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
     _ = n.choose s * (n - s).choose (k - s) * ((n - k)! * (k - s)! * s !) := by
       rw [tsub_tsub_tsub_cancel_right hsk, mul_assoc, mul_left_comm s !, mul_assoc,
         mul_comm (k - s)!, mul_comm s !, mul_right_comm, ← mul_assoc]
-    
 #align nat.choose_mul Nat.choose_mul
 -/

c3291da4

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -381,7 +381,7 @@ theorem choose_le_middle (r n : ℕ) : choose n r ≤ choose n (n / 2) :=
     · apply choose_le_middle_of_le_half_left a
     · rw [← choose_symm b]
       apply choose_le_middle_of_le_half_left
-      rw [div_lt_iff_lt_mul' zero_lt_two] at h
+      rw [div_lt_iff_lt_mul' zero_lt_two] at h 
       rw [le_div_iff_mul_le' zero_lt_two, tsub_mul, tsub_le_iff_tsub_le, mul_two,
         add_tsub_cancel_right]
       exact le_of_lt h

c3291da4

bump to nightly-2023-05-28-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

8d353152

Diff

@@ -43,7 +43,7 @@ binomial coefficient, combination, multicombination, stars and bars
 -/
 
 
-open Nat
+open scoped Nat
 
 namespace Nat

c3291da4

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -122,9 +122,7 @@ theorem choose_two_right (n : ℕ) : choose n 2 = n * (n - 1) / 2 :=
   by
   induction' n with n ih
   simp
-  · rw [triangle_succ n]
-    simp [choose, ih]
-    rw [add_comm]
+  · rw [triangle_succ n]; simp [choose, ih]; rw [add_comm]
 #align nat.choose_two_right Nat.choose_two_right
 -/
 
@@ -247,10 +245,8 @@ theorem choose_symm {n k : ℕ} (hk : k ≤ n) : choose n (n - k) = choose n k :
 -/
 
 #print Nat.choose_symm_of_eq_add /-
-theorem choose_symm_of_eq_add {n a b : ℕ} (h : n = a + b) : Nat.choose n a = Nat.choose n b :=
-  by
-  convert Nat.choose_symm (Nat.le_add_left _ _)
-  rw [add_tsub_cancel_right]
+theorem choose_symm_of_eq_add {n a b : ℕ} (h : n = a + b) : Nat.choose n a = Nat.choose n b := by
+  convert Nat.choose_symm (Nat.le_add_left _ _); rw [add_tsub_cancel_right]
 #align nat.choose_symm_of_eq_add Nat.choose_symm_of_eq_add
 -/

c3291da4

bump to nightly-2023-05-28-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6c6011cf

Diff

@@ -375,7 +375,6 @@ private theorem choose_le_middle_of_le_half_left {n r : ℕ} (hr : r ≤ n / 2)
       (eq_or_lt_of_le a).elim (fun t => t.symm ▸ le_rfl) fun h =>
         (choose_le_succ_of_lt_half_left h).trans (k h))
     hr (fun _ => le_rfl) hr
-#align nat.choose_le_middle_of_le_half_left nat.choose_le_middle_of_le_half_left
 
 #print Nat.choose_le_middle /-
 /-- `choose n r` is maximised when `r` is `n/2`. -/

c3291da4

bump to nightly-2023-03-11-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212

cd44fb92

Diff

@@ -293,7 +293,8 @@ theorem choose_mul_succ_eq (n k : ℕ) : n.choose k * (n + 1) = (n + 1).choose k
   ·
     rw [choose_succ_succ, add_mul, succ_sub_succ, ← choose_succ_right_eq, ← succ_sub_succ, mul_tsub,
       add_tsub_cancel_of_le (Nat.mul_le_mul_left _ hk)]
-  rw [choose_eq_zero_of_lt hk, choose_eq_zero_of_lt (n.lt_succ_self.trans hk), zero_mul, zero_mul]
+  rw [choose_eq_zero_of_lt hk, choose_eq_zero_of_lt (n.lt_succ_self.trans hk),
+    MulZeroClass.zero_mul, MulZeroClass.zero_mul]
 #align nat.choose_mul_succ_eq Nat.choose_mul_succ_eq
 -/
 
@@ -329,7 +330,7 @@ theorem choose_eq_asc_factorial_div_factorial (n k : ℕ) :
 theorem descFactorial_eq_factorial_mul_choose (n k : ℕ) : n.descFactorial k = k ! * n.choose k :=
   by
   obtain h | h := Nat.lt_or_ge n k
-  · rw [desc_factorial_eq_zero_iff_lt.2 h, choose_eq_zero_of_lt h, mul_zero]
+  · rw [desc_factorial_eq_zero_iff_lt.2 h, choose_eq_zero_of_lt h, MulZeroClass.mul_zero]
   rw [mul_comm]
   apply mul_right_cancel₀ (factorial_ne_zero (n - k))
   rw [choose_mul_factorial_mul_factorial h, ← factorial_mul_desc_factorial h, mul_comm]

c3291da4

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

2f3994e1

chore(Data/Nat/Factorial): Use Std lemmas (#11715)

Make use of Nat-specific lemmas from Std rather than the general ones provided by mathlib.

The ultimate goal here is to carve out Data, Algebra and Order sublibraries.

48efc23f

Diff

@@ -4,8 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Bhavik Mehta, Stuart Presnell
 -/
 import Mathlib.Data.Nat.Factorial.Basic
-import Mathlib.Algebra.Divisibility.Basic
-import Mathlib.Algebra.GroupWithZero.Basic
+import Mathlib.Order.Monotone.Basic
 
 #align_import data.nat.choose.basic from "leanprover-community/mathlib"@"2f3994e1b117b1e1da49bcfb67334f33460c3ce4"
 
@@ -87,12 +86,12 @@ theorem choose_succ_self (n : ℕ) : choose n (succ n) = 0 :=
 #align nat.choose_succ_self Nat.choose_succ_self
 
 @[simp]
-theorem choose_one_right (n : ℕ) : choose n 1 = n := by induction n <;> simp [*, choose, add_comm]
+lemma choose_one_right (n : ℕ) : choose n 1 = n := by induction n <;> simp [*, choose, Nat.add_comm]
 #align nat.choose_one_right Nat.choose_one_right
 
 -- The `n+1`-st triangle number is `n` more than the `n`-th triangle number
 theorem triangle_succ (n : ℕ) : (n + 1) * (n + 1 - 1) / 2 = n * (n - 1) / 2 + n := by
-  rw [← add_mul_div_left, mul_comm 2 n, ← mul_add, Nat.add_sub_cancel, mul_comm]
+  rw [← add_mul_div_left, Nat.mul_comm 2 n, ← Nat.mul_add, Nat.add_sub_cancel, Nat.mul_comm]
   cases n <;> rfl; apply zero_lt_succ
 #align nat.triangle_succ Nat.triangle_succ
 
@@ -101,7 +100,7 @@ theorem choose_two_right (n : ℕ) : choose n 2 = n * (n - 1) / 2 := by
   induction' n with n ih
   · simp
   · rw [triangle_succ n, choose, ih]
-    simp [add_comm]
+    simp [Nat.add_comm]
 #align nat.choose_two_right Nat.choose_two_right
 
 theorem choose_pos : ∀ {n k}, k ≤ n → 0 < choose n k
@@ -117,10 +116,10 @@ theorem choose_eq_zero_iff {n k : ℕ} : n.choose k = 0 ↔ n < k :=
 theorem succ_mul_choose_eq : ∀ n k, succ n * choose n k = choose (succ n) (succ k) * succ k
   | 0, 0 => by decide
   | 0, k + 1 => by simp [choose]
-  | n + 1, 0 => by simp [choose, mul_succ, succ_eq_add_one, add_comm]
+  | n + 1, 0 => by simp [choose, mul_succ, succ_eq_add_one, Nat.add_comm]
   | n + 1, k + 1 => by
-    rw [choose_succ_succ (succ n) (succ k), add_mul, ← succ_mul_choose_eq n, mul_succ, ←
-      succ_mul_choose_eq n, add_right_comm, ← mul_add, ← choose_succ_succ, ← succ_mul]
+    rw [choose_succ_succ (succ n) (succ k), Nat.add_mul, ← succ_mul_choose_eq n, mul_succ, ←
+      succ_mul_choose_eq n, Nat.add_right_comm, ← Nat.mul_add, ← choose_succ_succ, ← succ_mul]
 #align nat.succ_mul_choose_eq Nat.succ_mul_choose_eq
 
 theorem choose_mul_factorial_mul_factorial : ∀ {n k}, k ≤ n → choose n k * k ! * (n - k)! = n !
@@ -130,56 +129,57 @@ theorem choose_mul_factorial_mul_factorial : ∀ {n k}, k ≤ n → choose n k *
     rcases lt_or_eq_of_le hk with hk₁ | hk₁
     · have h : choose n k * k.succ ! * (n - k)! = (k + 1) * n ! := by
         rw [← choose_mul_factorial_mul_factorial (le_of_succ_le_succ hk)]
-        simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
+        simp [factorial_succ, Nat.mul_comm, Nat.mul_left_comm, Nat.mul_assoc]
       have h₁ : (n - k)! = (n - k) * (n - k.succ)! := by
         rw [← succ_sub_succ, succ_sub (le_of_lt_succ hk₁), factorial_succ]
       have h₂ : choose n (succ k) * k.succ ! * ((n - k) * (n - k.succ)!) = (n - k) * n ! := by
         rw [← choose_mul_factorial_mul_factorial (le_of_lt_succ hk₁)]
-        simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
+        simp [factorial_succ, Nat.mul_comm, Nat.mul_left_comm, Nat.mul_assoc]
       have h₃ : k * n ! ≤ n * n ! := Nat.mul_le_mul_right _ (le_of_succ_le_succ hk)
-      rw [choose_succ_succ, add_mul, add_mul, succ_sub_succ, h, h₁, h₂, add_mul,
-        Nat.mul_sub_right_distrib, factorial_succ, ← Nat.add_sub_assoc h₃, add_assoc, ← add_mul,
-        Nat.add_sub_cancel_left, add_comm]
-    · rw [hk₁]; simp [hk₁, mul_comm, choose, Nat.sub_self]
+      rw [choose_succ_succ, Nat.add_mul, Nat.add_mul, succ_sub_succ, h, h₁, h₂, Nat.add_mul,
+        Nat.mul_sub_right_distrib, factorial_succ, ← Nat.add_sub_assoc h₃, Nat.add_assoc,
+        ← Nat.add_mul, Nat.add_sub_cancel_left, Nat.add_comm]
+    · rw [hk₁]; simp [hk₁, Nat.mul_comm, choose, Nat.sub_self]
 #align nat.choose_mul_factorial_mul_factorial Nat.choose_mul_factorial_mul_factorial
 
 theorem choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
     n.choose k * k.choose s = n.choose s * (n - s).choose (k - s) :=
-  have h : (n - k)! * (k - s)! * s ! ≠ 0 := by apply_rules [factorial_ne_zero, mul_ne_zero]
-  mul_right_cancel₀ h <|
+  have h : 0 < (n - k)! * (k - s)! * s ! := by apply_rules [factorial_pos, Nat.mul_pos]
+  Nat.mul_right_cancel h <|
   calc
     n.choose k * k.choose s * ((n - k)! * (k - s)! * s !) =
         n.choose k * (k.choose s * s ! * (k - s)!) * (n - k)! :=
-      by rw [mul_assoc, mul_assoc, mul_assoc, mul_assoc _ s !, mul_assoc, mul_comm (n - k)!,
-        mul_comm s !]
+      by rw [Nat.mul_assoc, Nat.mul_assoc, Nat.mul_assoc, Nat.mul_assoc _ s !, Nat.mul_assoc,
+        Nat.mul_comm (n - k)!, Nat.mul_comm s !]
     _ = n ! :=
       by rw [choose_mul_factorial_mul_factorial hsk, choose_mul_factorial_mul_factorial hkn]
     _ = n.choose s * s ! * ((n - s).choose (k - s) * (k - s)! * (n - s - (k - s))!) :=
       by rw [choose_mul_factorial_mul_factorial (Nat.sub_le_sub_right hkn _),
         choose_mul_factorial_mul_factorial (hsk.trans hkn)]
     _ = n.choose s * (n - s).choose (k - s) * ((n - k)! * (k - s)! * s !) := by
-      rw [Nat.sub_sub_sub_cancel_right hsk, mul_assoc, mul_left_comm s !, mul_assoc,
-        mul_comm (k - s)!, mul_comm s !, mul_right_comm, ← mul_assoc]
+      rw [Nat.sub_sub_sub_cancel_right hsk, Nat.mul_assoc, Nat.mul_left_comm s !, Nat.mul_assoc,
+        Nat.mul_comm (k - s)!, Nat.mul_comm s !, Nat.mul_right_comm, ← Nat.mul_assoc]
 #align nat.choose_mul Nat.choose_mul
 
 theorem choose_eq_factorial_div_factorial {n k : ℕ} (hk : k ≤ n) :
     choose n k = n ! / (k ! * (n - k)!) := by
-  rw [← choose_mul_factorial_mul_factorial hk, mul_assoc]
+  rw [← choose_mul_factorial_mul_factorial hk, Nat.mul_assoc]
   exact (mul_div_left _ (Nat.mul_pos (factorial_pos _) (factorial_pos _))).symm
 #align nat.choose_eq_factorial_div_factorial Nat.choose_eq_factorial_div_factorial
 
 theorem add_choose (i j : ℕ) : (i + j).choose j = (i + j)! / (i ! * j !) := by
-  rw [choose_eq_factorial_div_factorial (Nat.le_add_left j i), Nat.add_sub_cancel_right, mul_comm]
+  rw [choose_eq_factorial_div_factorial (Nat.le_add_left j i), Nat.add_sub_cancel_right,
+    Nat.mul_comm]
 #align nat.add_choose Nat.add_choose
 
 theorem add_choose_mul_factorial_mul_factorial (i j : ℕ) :
     (i + j).choose j * i ! * j ! = (i + j)! := by
   rw [← choose_mul_factorial_mul_factorial (Nat.le_add_left _ _), Nat.add_sub_cancel_right,
-    mul_right_comm]
+    Nat.mul_right_comm]
 #align nat.add_choose_mul_factorial_mul_factorial Nat.add_choose_mul_factorial_mul_factorial
 
 theorem factorial_mul_factorial_dvd_factorial {n k : ℕ} (hk : k ≤ n) : k ! * (n - k)! ∣ n ! := by
-  rw [← choose_mul_factorial_mul_factorial hk, mul_assoc]; exact dvd_mul_left _ _
+  rw [← choose_mul_factorial_mul_factorial hk, Nat.mul_assoc]; exact Nat.dvd_mul_left _ _
 #align nat.factorial_mul_factorial_dvd_factorial Nat.factorial_mul_factorial_dvd_factorial
 
 theorem factorial_mul_factorial_dvd_factorial_add (i j : ℕ) : i ! * j ! ∣ (i + j)! := by
@@ -191,7 +191,7 @@ theorem factorial_mul_factorial_dvd_factorial_add (i j : ℕ) : i ! * j ! ∣ (i
 @[simp]
 theorem choose_symm {n k : ℕ} (hk : k ≤ n) : choose n (n - k) = choose n k := by
   rw [choose_eq_factorial_div_factorial hk, choose_eq_factorial_div_factorial (Nat.sub_le _ _),
-    Nat.sub_sub_self hk, mul_comm]
+    Nat.sub_sub_self hk, Nat.mul_comm]
 #align nat.choose_symm Nat.choose_symm
 
 theorem choose_symm_of_eq_add {n a b : ℕ} (h : n = a + b) : Nat.choose n a = Nat.choose n b := by
@@ -206,13 +206,13 @@ theorem choose_symm_add {a b : ℕ} : choose (a + b) a = choose (a + b) b :=
 
 theorem choose_symm_half (m : ℕ) : choose (2 * m + 1) (m + 1) = choose (2 * m + 1) m := by
   apply choose_symm_of_eq_add
-  rw [add_comm m 1, add_assoc 1 m m, add_comm (2 * m) 1, two_mul m]
+  rw [Nat.add_comm m 1, Nat.add_assoc 1 m m, Nat.add_comm (2 * m) 1, Nat.two_mul m]
 #align nat.choose_symm_half Nat.choose_symm_half
 
 theorem choose_succ_right_eq (n k : ℕ) : choose n (k + 1) * (k + 1) = choose n k * (n - k) := by
   have e : (n + 1) * choose n k = choose n (k + 1) * (k + 1) + choose n k * (k + 1) := by
-    rw [← right_distrib, add_comm (choose _ _), ← choose_succ_succ, succ_mul_choose_eq]
-  rw [← Nat.sub_eq_of_eq_add e, mul_comm, ← Nat.mul_sub_left_distrib, Nat.add_sub_add_right]
+    rw [← Nat.add_mul, Nat.add_comm (choose _ _), ← choose_succ_succ, succ_mul_choose_eq]
+  rw [← Nat.sub_eq_of_eq_add e, Nat.mul_comm, ← Nat.mul_sub_left_distrib, Nat.add_sub_add_right]
 #align nat.choose_succ_right_eq Nat.choose_succ_right_eq
 
 @[simp]
@@ -226,29 +226,29 @@ theorem choose_mul_succ_eq (n k : ℕ) : n.choose k * (n + 1) = (n + 1).choose k
   | zero => simp
   | succ k =>
     obtain hk | hk := le_or_lt (k + 1) (n + 1)
-    · rw [choose_succ_succ, add_mul, succ_sub_succ, ← choose_succ_right_eq, ← succ_sub_succ,
+    · rw [choose_succ_succ, Nat.add_mul, succ_sub_succ, ← choose_succ_right_eq, ← succ_sub_succ,
         Nat.mul_sub_left_distrib, Nat.add_sub_cancel' (Nat.mul_le_mul_left _ hk)]
-    · rw [choose_eq_zero_of_lt hk, choose_eq_zero_of_lt (n.lt_succ_self.trans hk), zero_mul,
-        zero_mul]
+    · rw [choose_eq_zero_of_lt hk, choose_eq_zero_of_lt (n.lt_succ_self.trans hk), Nat.zero_mul,
+        Nat.zero_mul]
 #align nat.choose_mul_succ_eq Nat.choose_mul_succ_eq
 
 theorem ascFactorial_eq_factorial_mul_choose (n k : ℕ) :
     (n + 1).ascFactorial k = k ! * (n + k).choose k := by
-  rw [mul_comm]
-  apply mul_right_cancel₀ (factorial_ne_zero (n + k - k))
+  rw [Nat.mul_comm]
+  apply Nat.mul_right_cancel (n + k - k).factorial_pos
   rw [choose_mul_factorial_mul_factorial <| Nat.le_add_left k n, Nat.add_sub_cancel_right,
-    ← factorial_mul_ascFactorial, mul_comm]
+    ← factorial_mul_ascFactorial, Nat.mul_comm]
 #align nat.asc_factorial_eq_factorial_mul_choose Nat.ascFactorial_eq_factorial_mul_choose
 
 theorem ascFactorial_eq_factorial_mul_choose' (n k : ℕ) :
     n.ascFactorial k = k ! * (n + k - 1).choose k := by
   cases n
   · cases k
-    · rw [ascFactorial_zero, choose_zero_right, factorial_zero, mul_one]
-    · simp only [zero_ascFactorial, zero_eq, zero_add, ge_iff_le, succ_sub_succ_eq_sub,
-        Nat.le_zero_eq, Nat.sub_zero, choose_succ_self, mul_zero]
+    · rw [ascFactorial_zero, choose_zero_right, factorial_zero, Nat.mul_one]
+    · simp only [zero_ascFactorial, zero_eq, Nat.zero_add, succ_sub_succ_eq_sub,
+        Nat.le_zero_eq, Nat.sub_zero, choose_succ_self, Nat.mul_zero]
   rw [ascFactorial_eq_factorial_mul_choose]
-  simp only [ge_iff_le, succ_add_sub_one]
+  simp only [succ_add_sub_one]
 
 theorem factorial_dvd_ascFactorial (n k : ℕ) : k ! ∣ n.ascFactorial k :=
   ⟨(n + k - 1).choose k, ascFactorial_eq_factorial_mul_choose' _ _⟩
@@ -256,33 +256,29 @@ theorem factorial_dvd_ascFactorial (n k : ℕ) : k ! ∣ n.ascFactorial k :=
 
 theorem choose_eq_asc_factorial_div_factorial (n k : ℕ) :
     (n + k).choose k = (n + 1).ascFactorial k / k ! := by
-  apply mul_left_cancel₀ (factorial_ne_zero k)
+  apply Nat.mul_left_cancel k.factorial_pos
   rw [← ascFactorial_eq_factorial_mul_choose]
   exact (Nat.mul_div_cancel' <| factorial_dvd_ascFactorial _ _).symm
 #align nat.choose_eq_asc_factorial_div_factorial Nat.choose_eq_asc_factorial_div_factorial
 
 theorem choose_eq_asc_factorial_div_factorial' (n k : ℕ) :
-    (n + k - 1).choose k = n.ascFactorial k / k ! := by
-  apply mul_left_cancel₀ (factorial_ne_zero k)
-  rw [← ascFactorial_eq_factorial_mul_choose']
-  exact (Nat.mul_div_cancel' <| factorial_dvd_ascFactorial _ _).symm
+    (n + k - 1).choose k = n.ascFactorial k / k ! :=
+  Nat.eq_div_of_mul_eq_right k.factorial_ne_zero (ascFactorial_eq_factorial_mul_choose' _ _).symm
 
 theorem descFactorial_eq_factorial_mul_choose (n k : ℕ) : n.descFactorial k = k ! * n.choose k := by
   obtain h | h := Nat.lt_or_ge n k
-  · rw [descFactorial_eq_zero_iff_lt.2 h, choose_eq_zero_of_lt h, mul_zero]
-  rw [mul_comm]
-  apply mul_right_cancel₀ (factorial_ne_zero (n - k))
-  rw [choose_mul_factorial_mul_factorial h, ← factorial_mul_descFactorial h, mul_comm]
+  · rw [descFactorial_eq_zero_iff_lt.2 h, choose_eq_zero_of_lt h, Nat.mul_zero]
+  rw [Nat.mul_comm]
+  apply Nat.mul_right_cancel (n - k).factorial_pos
+  rw [choose_mul_factorial_mul_factorial h, ← factorial_mul_descFactorial h, Nat.mul_comm]
 #align nat.desc_factorial_eq_factorial_mul_choose Nat.descFactorial_eq_factorial_mul_choose
 
 theorem factorial_dvd_descFactorial (n k : ℕ) : k ! ∣ n.descFactorial k :=
   ⟨n.choose k, descFactorial_eq_factorial_mul_choose _ _⟩
 #align nat.factorial_dvd_desc_factorial Nat.factorial_dvd_descFactorial
 
-theorem choose_eq_descFactorial_div_factorial (n k : ℕ) : n.choose k = n.descFactorial k / k ! := by
-  apply mul_left_cancel₀ (factorial_ne_zero k)
-  rw [← descFactorial_eq_factorial_mul_choose]
-  exact (Nat.mul_div_cancel' <| factorial_dvd_descFactorial _ _).symm
+theorem choose_eq_descFactorial_div_factorial (n k : ℕ) : n.choose k = n.descFactorial k / k ! :=
+  Nat.eq_div_of_mul_eq_right k.factorial_ne_zero (descFactorial_eq_factorial_mul_choose _ _).symm
 #align nat.choose_eq_desc_factorial_div_factorial Nat.choose_eq_descFactorial_div_factorial
 
 /-- A faster implementation of `choose`, to be used during bytecode evaluation
@@ -302,7 +298,7 @@ theorem choose_le_succ_of_lt_half_left {r n : ℕ} (h : r < n / 2) :
   refine Nat.le_of_mul_le_mul_right ?_ (Nat.sub_pos_of_lt (h.trans_le (n.div_le_self 2)))
   rw [← choose_succ_right_eq]
   apply Nat.mul_le_mul_left
-  rw [← Nat.lt_iff_add_one_le, Nat.lt_sub_iff_add_lt, ← mul_two]
+  rw [← Nat.lt_iff_add_one_le, Nat.lt_sub_iff_add_lt, ← Nat.mul_two]
   exact lt_of_lt_of_le (Nat.mul_lt_mul_of_pos_right h Nat.zero_lt_two) (n.div_mul_le_self 2)
 #align nat.choose_le_succ_of_lt_half_left Nat.choose_le_succ_of_lt_half_left
 
@@ -324,7 +320,7 @@ theorem choose_le_middle (r n : ℕ) : choose n r ≤ choose n (n / 2) := by
       apply choose_le_middle_of_le_half_left
       rw [div_lt_iff_lt_mul' Nat.zero_lt_two] at h
       rw [le_div_iff_mul_le' Nat.zero_lt_two, Nat.mul_sub_right_distrib, Nat.sub_le_iff_le_add,
-        ← Nat.sub_le_iff_le_add', mul_two, Nat.add_sub_cancel]
+        ← Nat.sub_le_iff_le_add', Nat.mul_two, Nat.add_sub_cancel]
       exact le_of_lt h
   · rw [choose_eq_zero_of_lt b]
     apply zero_le
@@ -401,7 +397,7 @@ theorem multichoose_one (k : ℕ) : multichoose 1 k = 1 := by
 theorem multichoose_two (k : ℕ) : multichoose 2 k = k + 1 := by
   induction' k with k IH; · simp
   rw [multichoose, IH]
-  simp [add_comm, succ_eq_add_one]
+  simp [Nat.add_comm, succ_eq_add_one]
 #align nat.multichoose_two Nat.multichoose_two
 
 @[simp]
@@ -416,7 +412,8 @@ theorem multichoose_eq : ∀ n k : ℕ, multichoose n k = (n + k - 1).choose k
   | n + 1, k + 1 => by
     have : n + (k + 1) < (n + 1) + (k + 1) := Nat.add_lt_add_right (Nat.lt_succ_self _) _
     have : (n + 1) + k < (n + 1) + (k + 1) := Nat.add_lt_add_left (Nat.lt_succ_self _) _
-    erw [multichoose_succ_succ, add_comm, Nat.succ_add_sub_one, ← add_assoc, Nat.choose_succ_succ]
+    erw [multichoose_succ_succ, Nat.add_comm, Nat.succ_add_sub_one, ← Nat.add_assoc,
+      Nat.choose_succ_succ]
     simp [multichoose_eq n (k+1), multichoose_eq (n+1) k]
   termination_by a b => a + b
   decreasing_by all_goals assumption

2f3994e1

chore(Data/Nat): Use Std lemmas (#11661)

Move basic Nat lemmas from Data.Nat.Order.Basic and Data.Nat.Pow to Data.Nat.Defs. Most proofs need adapting, but that's easily solved by replacing the general mathlib lemmas by the new Std Nat-specific lemmas and using omega.

Other changes

Move the last few lemmas left in Data.Nat.Pow to Algebra.GroupPower.Order
Move the deprecated aliases from Data.Nat.Pow to Algebra.GroupPower.Order
Move the bit/bit0/bit1 lemmas from Data.Nat.Order.Basic to Data.Nat.Bits
Fix some fallout from not importing Data.Nat.Order.Basic anymore
Add a few Nat-specific lemmas to help fix the fallout (look for nolint simpNF)
Turn Nat.mul_self_le_mul_self_iff and Nat.mul_self_lt_mul_self_iff around (they were misnamed)
Make more arguments to Nat.one_lt_pow implicit

5bc68d9f

Diff

@@ -6,7 +6,6 @@ Authors: Chris Hughes, Bhavik Mehta, Stuart Presnell
 import Mathlib.Data.Nat.Factorial.Basic
 import Mathlib.Algebra.Divisibility.Basic
 import Mathlib.Algebra.GroupWithZero.Basic
-import Mathlib.Data.Nat.Order.Basic
 
 #align_import data.nat.choose.basic from "leanprover-community/mathlib"@"2f3994e1b117b1e1da49bcfb67334f33460c3ce4"
 
@@ -93,7 +92,7 @@ theorem choose_one_right (n : ℕ) : choose n 1 = n := by induction n <;> simp [
 
 -- The `n+1`-st triangle number is `n` more than the `n`-th triangle number
 theorem triangle_succ (n : ℕ) : (n + 1) * (n + 1 - 1) / 2 = n * (n - 1) / 2 + n := by
-  rw [← add_mul_div_left, mul_comm 2 n, ← mul_add, add_tsub_cancel_right, mul_comm]
+  rw [← add_mul_div_left, mul_comm 2 n, ← mul_add, Nat.add_sub_cancel, mul_comm]
   cases n <;> rfl; apply zero_lt_succ
 #align nat.triangle_succ Nat.triangle_succ
 
@@ -108,9 +107,7 @@ theorem choose_two_right (n : ℕ) : choose n 2 = n * (n - 1) / 2 := by
 theorem choose_pos : ∀ {n k}, k ≤ n → 0 < choose n k
   | 0, _, hk => by rw [Nat.eq_zero_of_le_zero hk]; decide
   | n + 1, 0, _ => by simp
-  | n + 1, k + 1, hk => by
-    rw [choose_succ_succ]
-    exact add_pos_of_pos_of_nonneg (choose_pos (le_of_succ_le_succ hk)) (Nat.zero_le _)
+  | n + 1, k + 1, hk => Nat.add_pos_left (choose_pos (le_of_succ_le_succ hk)) _
 #align nat.choose_pos Nat.choose_pos
 
 theorem choose_eq_zero_iff {n k : ℕ} : n.choose k = 0 ↔ n < k :=
@@ -140,10 +137,10 @@ theorem choose_mul_factorial_mul_factorial : ∀ {n k}, k ≤ n → choose n k *
         rw [← choose_mul_factorial_mul_factorial (le_of_lt_succ hk₁)]
         simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
       have h₃ : k * n ! ≤ n * n ! := Nat.mul_le_mul_right _ (le_of_succ_le_succ hk)
-      rw [choose_succ_succ, add_mul, add_mul, succ_sub_succ, h, h₁, h₂, add_mul, tsub_mul,
-        factorial_succ, ← add_tsub_assoc_of_le h₃, add_assoc, ← add_mul, add_tsub_cancel_left,
-        add_comm]
-    · rw [hk₁]; simp [hk₁, mul_comm, choose, tsub_self]
+      rw [choose_succ_succ, add_mul, add_mul, succ_sub_succ, h, h₁, h₂, add_mul,
+        Nat.mul_sub_right_distrib, factorial_succ, ← Nat.add_sub_assoc h₃, add_assoc, ← add_mul,
+        Nat.add_sub_cancel_left, add_comm]
+    · rw [hk₁]; simp [hk₁, mul_comm, choose, Nat.sub_self]
 #align nat.choose_mul_factorial_mul_factorial Nat.choose_mul_factorial_mul_factorial
 
 theorem choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
@@ -158,26 +155,26 @@ theorem choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
     _ = n ! :=
       by rw [choose_mul_factorial_mul_factorial hsk, choose_mul_factorial_mul_factorial hkn]
     _ = n.choose s * s ! * ((n - s).choose (k - s) * (k - s)! * (n - s - (k - s))!) :=
-      by rw [choose_mul_factorial_mul_factorial (tsub_le_tsub_right hkn _),
+      by rw [choose_mul_factorial_mul_factorial (Nat.sub_le_sub_right hkn _),
         choose_mul_factorial_mul_factorial (hsk.trans hkn)]
-    _ = n.choose s * (n - s).choose (k - s) * ((n - k)! * (k - s)! * s !) :=
-      by rw [tsub_tsub_tsub_cancel_right hsk, mul_assoc, mul_left_comm s !, mul_assoc,
+    _ = n.choose s * (n - s).choose (k - s) * ((n - k)! * (k - s)! * s !) := by
+      rw [Nat.sub_sub_sub_cancel_right hsk, mul_assoc, mul_left_comm s !, mul_assoc,
         mul_comm (k - s)!, mul_comm s !, mul_right_comm, ← mul_assoc]
 #align nat.choose_mul Nat.choose_mul
 
 theorem choose_eq_factorial_div_factorial {n k : ℕ} (hk : k ≤ n) :
     choose n k = n ! / (k ! * (n - k)!) := by
   rw [← choose_mul_factorial_mul_factorial hk, mul_assoc]
-  exact (mul_div_left _ (mul_pos (factorial_pos _) (factorial_pos _))).symm
+  exact (mul_div_left _ (Nat.mul_pos (factorial_pos _) (factorial_pos _))).symm
 #align nat.choose_eq_factorial_div_factorial Nat.choose_eq_factorial_div_factorial
 
 theorem add_choose (i j : ℕ) : (i + j).choose j = (i + j)! / (i ! * j !) := by
-  rw [choose_eq_factorial_div_factorial (Nat.le_add_left j i), add_tsub_cancel_right, mul_comm]
+  rw [choose_eq_factorial_div_factorial (Nat.le_add_left j i), Nat.add_sub_cancel_right, mul_comm]
 #align nat.add_choose Nat.add_choose
 
 theorem add_choose_mul_factorial_mul_factorial (i j : ℕ) :
     (i + j).choose j * i ! * j ! = (i + j)! := by
-  rw [← choose_mul_factorial_mul_factorial (Nat.le_add_left _ _), add_tsub_cancel_right,
+  rw [← choose_mul_factorial_mul_factorial (Nat.le_add_left _ _), Nat.add_sub_cancel_right,
     mul_right_comm]
 #align nat.add_choose_mul_factorial_mul_factorial Nat.add_choose_mul_factorial_mul_factorial
 
@@ -187,19 +184,19 @@ theorem factorial_mul_factorial_dvd_factorial {n k : ℕ} (hk : k ≤ n) : k ! *
 
 theorem factorial_mul_factorial_dvd_factorial_add (i j : ℕ) : i ! * j ! ∣ (i + j)! := by
   suffices i ! * (i + j - i) ! ∣ (i + j)! by
-    rwa [add_tsub_cancel_left i j] at this
+    rwa [Nat.add_sub_cancel_left i j] at this
   exact factorial_mul_factorial_dvd_factorial (Nat.le_add_right _ _)
 #align nat.factorial_mul_factorial_dvd_factorial_add Nat.factorial_mul_factorial_dvd_factorial_add
 
 @[simp]
 theorem choose_symm {n k : ℕ} (hk : k ≤ n) : choose n (n - k) = choose n k := by
   rw [choose_eq_factorial_div_factorial hk, choose_eq_factorial_div_factorial (Nat.sub_le _ _),
-    tsub_tsub_cancel_of_le hk, mul_comm]
+    Nat.sub_sub_self hk, mul_comm]
 #align nat.choose_symm Nat.choose_symm
 
 theorem choose_symm_of_eq_add {n a b : ℕ} (h : n = a + b) : Nat.choose n a = Nat.choose n b := by
   suffices choose n (n - b) = choose n b by
-    rw [h, add_tsub_cancel_right] at this; rwa [h]
+    rw [h, Nat.add_sub_cancel_right] at this; rwa [h]
   exact choose_symm (h ▸ le_add_left _ _)
 #align nat.choose_symm_of_eq_add Nat.choose_symm_of_eq_add
 
@@ -213,9 +210,9 @@ theorem choose_symm_half (m : ℕ) : choose (2 * m + 1) (m + 1) = choose (2 * m
 #align nat.choose_symm_half Nat.choose_symm_half
 
 theorem choose_succ_right_eq (n k : ℕ) : choose n (k + 1) * (k + 1) = choose n k * (n - k) := by
-  have e : (n + 1) * choose n k = choose n k * (k + 1) + choose n (k + 1) * (k + 1) := by
-    rw [← right_distrib, ← choose_succ_succ, succ_mul_choose_eq]
-  rw [← tsub_eq_of_eq_add_rev e, mul_comm, ← mul_tsub, add_tsub_add_eq_tsub_right]
+  have e : (n + 1) * choose n k = choose n (k + 1) * (k + 1) + choose n k * (k + 1) := by
+    rw [← right_distrib, add_comm (choose _ _), ← choose_succ_succ, succ_mul_choose_eq]
+  rw [← Nat.sub_eq_of_eq_add e, mul_comm, ← Nat.mul_sub_left_distrib, Nat.add_sub_add_right]
 #align nat.choose_succ_right_eq Nat.choose_succ_right_eq
 
 @[simp]
@@ -230,7 +227,7 @@ theorem choose_mul_succ_eq (n k : ℕ) : n.choose k * (n + 1) = (n + 1).choose k
   | succ k =>
     obtain hk | hk := le_or_lt (k + 1) (n + 1)
     · rw [choose_succ_succ, add_mul, succ_sub_succ, ← choose_succ_right_eq, ← succ_sub_succ,
-        mul_tsub, add_tsub_cancel_of_le (Nat.mul_le_mul_left _ hk)]
+        Nat.mul_sub_left_distrib, Nat.add_sub_cancel' (Nat.mul_le_mul_left _ hk)]
     · rw [choose_eq_zero_of_lt hk, choose_eq_zero_of_lt (n.lt_succ_self.trans hk), zero_mul,
         zero_mul]
 #align nat.choose_mul_succ_eq Nat.choose_mul_succ_eq
@@ -239,7 +236,7 @@ theorem ascFactorial_eq_factorial_mul_choose (n k : ℕ) :
     (n + 1).ascFactorial k = k ! * (n + k).choose k := by
   rw [mul_comm]
   apply mul_right_cancel₀ (factorial_ne_zero (n + k - k))
-  rw [choose_mul_factorial_mul_factorial <| Nat.le_add_left k n, add_tsub_cancel_right,
+  rw [choose_mul_factorial_mul_factorial <| Nat.le_add_left k n, Nat.add_sub_cancel_right,
     ← factorial_mul_ascFactorial, mul_comm]
 #align nat.asc_factorial_eq_factorial_mul_choose Nat.ascFactorial_eq_factorial_mul_choose
 
@@ -249,7 +246,7 @@ theorem ascFactorial_eq_factorial_mul_choose' (n k : ℕ) :
   · cases k
     · rw [ascFactorial_zero, choose_zero_right, factorial_zero, mul_one]
     · simp only [zero_ascFactorial, zero_eq, zero_add, ge_iff_le, succ_sub_succ_eq_sub,
-        nonpos_iff_eq_zero, tsub_zero, choose_succ_self, mul_zero]
+        Nat.le_zero_eq, Nat.sub_zero, choose_succ_self, mul_zero]
   rw [ascFactorial_eq_factorial_mul_choose]
   simp only [ge_iff_le, succ_add_sub_one]
 
@@ -302,11 +299,11 @@ def fast_choose n k := Nat.descFactorial n k / Nat.factorial k
 /-- Show that `Nat.choose` is increasing for small values of the right argument. -/
 theorem choose_le_succ_of_lt_half_left {r n : ℕ} (h : r < n / 2) :
     choose n r ≤ choose n (r + 1) := by
-  refine' le_of_mul_le_mul_right _ (lt_tsub_iff_left.mpr (lt_of_lt_of_le h (n.div_le_self 2)))
+  refine Nat.le_of_mul_le_mul_right ?_ (Nat.sub_pos_of_lt (h.trans_le (n.div_le_self 2)))
   rw [← choose_succ_right_eq]
   apply Nat.mul_le_mul_left
-  rw [← Nat.lt_iff_add_one_le, lt_tsub_iff_left, ← mul_two]
-  exact lt_of_lt_of_le (mul_lt_mul_of_pos_right h zero_lt_two) (n.div_mul_le_self 2)
+  rw [← Nat.lt_iff_add_one_le, Nat.lt_sub_iff_add_lt, ← mul_two]
+  exact lt_of_lt_of_le (Nat.mul_lt_mul_of_pos_right h Nat.zero_lt_two) (n.div_mul_le_self 2)
 #align nat.choose_le_succ_of_lt_half_left Nat.choose_le_succ_of_lt_half_left
 
 /-- Show that for small values of the right argument, the middle value is largest. -/
@@ -325,9 +322,9 @@ theorem choose_le_middle (r n : ℕ) : choose n r ≤ choose n (n / 2) := by
     · apply choose_le_middle_of_le_half_left a
     · rw [← choose_symm b]
       apply choose_le_middle_of_le_half_left
-      rw [div_lt_iff_lt_mul' zero_lt_two] at h
-      rw [le_div_iff_mul_le' zero_lt_two, tsub_mul, tsub_le_iff_tsub_le, mul_two,
-        add_tsub_cancel_right]
+      rw [div_lt_iff_lt_mul' Nat.zero_lt_two] at h
+      rw [le_div_iff_mul_le' Nat.zero_lt_two, Nat.mul_sub_right_distrib, Nat.sub_le_iff_le_add,
+        ← Nat.sub_le_iff_le_add', mul_two, Nat.add_sub_cancel]
       exact le_of_lt h
   · rw [choose_eq_zero_of_lt b]
     apply zero_le
@@ -347,7 +344,7 @@ theorem choose_le_add (a b c : ℕ) : choose a c ≤ choose (a + b) c := by
 #align nat.choose_le_add Nat.choose_le_add
 
 theorem choose_le_choose {a b : ℕ} (c : ℕ) (h : a ≤ b) : choose a c ≤ choose b c :=
-  add_tsub_cancel_of_le h ▸ choose_le_add a (b - a) c
+  Nat.add_sub_cancel' h ▸ choose_le_add a (b - a) c
 #align nat.choose_le_choose Nat.choose_le_choose
 
 theorem choose_mono (b : ℕ) : Monotone fun a => choose a b := fun _ _ => choose_le_choose b
@@ -417,8 +414,8 @@ theorem multichoose_eq : ∀ n k : ℕ, multichoose n k = (n + k - 1).choose k
   | _, 0 => by simp
   | 0, k + 1 => by simp
   | n + 1, k + 1 => by
-    have : n + (k + 1) < (n + 1) + (k + 1) := add_lt_add_right (Nat.lt_succ_self _) _
-    have : (n + 1) + k < (n + 1) + (k + 1) := add_lt_add_left (Nat.lt_succ_self _) _
+    have : n + (k + 1) < (n + 1) + (k + 1) := Nat.add_lt_add_right (Nat.lt_succ_self _) _
+    have : (n + 1) + k < (n + 1) + (k + 1) := Nat.add_lt_add_left (Nat.lt_succ_self _) _
     erw [multichoose_succ_succ, add_comm, Nat.succ_add_sub_one, ← add_assoc, Nat.choose_succ_succ]
     simp [multichoose_eq n (k+1), multichoose_eq (n+1) k]
   termination_by a b => a + b

2f3994e1

chore: resolve a few porting notes of "original proof fails". (#11388)

cef4a374

Diff

@@ -372,7 +372,6 @@ where `choose` is the generalized binomial coefficient.
 
 -/
 
--- Porting note: `termination_by` required here where it wasn't before
 /--
 `multichoose n k` is the number of multisets of cardinality `k` from a type of cardinality `n`. -/
 def multichoose : ℕ → ℕ → ℕ
@@ -380,7 +379,6 @@ def multichoose : ℕ → ℕ → ℕ
   | 0, _ + 1 => 0
   | n + 1, k + 1 =>
     multichoose n (k + 1) + multichoose (n + 1) k
-  termination_by a b => (a, b)
 #align nat.multichoose Nat.multichoose
 
 @[simp]

2f3994e1

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -372,7 +372,7 @@ where `choose` is the generalized binomial coefficient.
 
 -/
 
---Porting note: `termination_by` required here where it wasn't before
+-- Porting note: `termination_by` required here where it wasn't before
 /--
 `multichoose n k` is the number of multisets of cardinality `k` from a type of cardinality `n`. -/
 def multichoose : ℕ → ℕ → ℕ

2f3994e1

chore: bump Std (#10482)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

9afd0027

Diff

@@ -4,6 +4,9 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Bhavik Mehta, Stuart Presnell
 -/
 import Mathlib.Data.Nat.Factorial.Basic
+import Mathlib.Algebra.Divisibility.Basic
+import Mathlib.Algebra.GroupWithZero.Basic
+import Mathlib.Data.Nat.Order.Basic
 
 #align_import data.nat.choose.basic from "leanprover-community/mathlib"@"2f3994e1b117b1e1da49bcfb67334f33460c3ce4"

2f3994e1

chore: move to v4.6.0-rc1, merging adaptations from bump/v4.6.0 (#10176)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Joachim Breitner <mail@joachim-breitner.de>

490d2d48

Diff

@@ -377,7 +377,7 @@ def multichoose : ℕ → ℕ → ℕ
   | 0, _ + 1 => 0
   | n + 1, k + 1 =>
     multichoose n (k + 1) + multichoose (n + 1) k
-  termination_by multichoose a b => (a, b)
+  termination_by a b => (a, b)
 #align nat.multichoose Nat.multichoose
 
 @[simp]
@@ -420,8 +420,8 @@ theorem multichoose_eq : ∀ n k : ℕ, multichoose n k = (n + k - 1).choose k
     have : (n + 1) + k < (n + 1) + (k + 1) := add_lt_add_left (Nat.lt_succ_self _) _
     erw [multichoose_succ_succ, add_comm, Nat.succ_add_sub_one, ← add_assoc, Nat.choose_succ_succ]
     simp [multichoose_eq n (k+1), multichoose_eq (n+1) k]
-  termination_by multichoose_eq a b => a + b
-  decreasing_by { assumption }
+  termination_by a b => a + b
+  decreasing_by all_goals assumption
 #align nat.multichoose_eq Nat.multichoose_eq
 
 end Nat

2f3994e1

chore: tidy various files (#9728)

a94a9fd8

Diff

@@ -242,11 +242,11 @@ theorem ascFactorial_eq_factorial_mul_choose (n k : ℕ) :
 
 theorem ascFactorial_eq_factorial_mul_choose' (n k : ℕ) :
     n.ascFactorial k = k ! * (n + k - 1).choose k := by
-  cases hn : n
-  cases hk : k
-  rw [ascFactorial_zero, choose_zero_right, factorial_zero, mul_one]
-  simp only [zero_ascFactorial, zero_eq, zero_add, ge_iff_le, succ_sub_succ_eq_sub,
-    nonpos_iff_eq_zero, tsub_zero, choose_succ_self, mul_zero]
+  cases n
+  · cases k
+    · rw [ascFactorial_zero, choose_zero_right, factorial_zero, mul_one]
+    · simp only [zero_ascFactorial, zero_eq, zero_add, ge_iff_le, succ_sub_succ_eq_sub,
+        nonpos_iff_eq_zero, tsub_zero, choose_succ_self, mul_zero]
   rw [ascFactorial_eq_factorial_mul_choose]
   simp only [ge_iff_le, succ_add_sub_one]

2f3994e1

chore: shift Nat.ascFactorial down by one (#7965)

change ascending factorial function Nat.ascFactorial to agree with mathematical literature. This means Nat.ascFactorial n k becomes n (n + 1) ⋯ (n + k - 1) instead of (n + 1) ⋯ (n + k)

Co-authored-by: Johan Commelin <johan@commelin.net>

0c15e423

Diff

@@ -233,25 +233,40 @@ theorem choose_mul_succ_eq (n k : ℕ) : n.choose k * (n + 1) = (n + 1).choose k
 #align nat.choose_mul_succ_eq Nat.choose_mul_succ_eq
 
 theorem ascFactorial_eq_factorial_mul_choose (n k : ℕ) :
-    n.ascFactorial k = k ! * (n + k).choose k := by
+    (n + 1).ascFactorial k = k ! * (n + k).choose k := by
   rw [mul_comm]
   apply mul_right_cancel₀ (factorial_ne_zero (n + k - k))
-  rw [choose_mul_factorial_mul_factorial, add_tsub_cancel_right, ← factorial_mul_ascFactorial,
-    mul_comm]
-  exact Nat.le_add_left k n
+  rw [choose_mul_factorial_mul_factorial <| Nat.le_add_left k n, add_tsub_cancel_right,
+    ← factorial_mul_ascFactorial, mul_comm]
 #align nat.asc_factorial_eq_factorial_mul_choose Nat.ascFactorial_eq_factorial_mul_choose
 
+theorem ascFactorial_eq_factorial_mul_choose' (n k : ℕ) :
+    n.ascFactorial k = k ! * (n + k - 1).choose k := by
+  cases hn : n
+  cases hk : k
+  rw [ascFactorial_zero, choose_zero_right, factorial_zero, mul_one]
+  simp only [zero_ascFactorial, zero_eq, zero_add, ge_iff_le, succ_sub_succ_eq_sub,
+    nonpos_iff_eq_zero, tsub_zero, choose_succ_self, mul_zero]
+  rw [ascFactorial_eq_factorial_mul_choose]
+  simp only [ge_iff_le, succ_add_sub_one]
+
 theorem factorial_dvd_ascFactorial (n k : ℕ) : k ! ∣ n.ascFactorial k :=
-  ⟨(n + k).choose k, ascFactorial_eq_factorial_mul_choose _ _⟩
+  ⟨(n + k - 1).choose k, ascFactorial_eq_factorial_mul_choose' _ _⟩
 #align nat.factorial_dvd_asc_factorial Nat.factorial_dvd_ascFactorial
 
 theorem choose_eq_asc_factorial_div_factorial (n k : ℕ) :
-    (n + k).choose k = n.ascFactorial k / k ! := by
+    (n + k).choose k = (n + 1).ascFactorial k / k ! := by
   apply mul_left_cancel₀ (factorial_ne_zero k)
   rw [← ascFactorial_eq_factorial_mul_choose]
   exact (Nat.mul_div_cancel' <| factorial_dvd_ascFactorial _ _).symm
 #align nat.choose_eq_asc_factorial_div_factorial Nat.choose_eq_asc_factorial_div_factorial
 
+theorem choose_eq_asc_factorial_div_factorial' (n k : ℕ) :
+    (n + k - 1).choose k = n.ascFactorial k / k ! := by
+  apply mul_left_cancel₀ (factorial_ne_zero k)
+  rw [← ascFactorial_eq_factorial_mul_choose']
+  exact (Nat.mul_div_cancel' <| factorial_dvd_ascFactorial _ _).symm
+
 theorem descFactorial_eq_factorial_mul_choose (n k : ℕ) : n.descFactorial k = k ! * n.choose k := by
   obtain h | h := Nat.lt_or_ge n k
   · rw [descFactorial_eq_zero_iff_lt.2 h, choose_eq_zero_of_lt h, mul_zero]

2f3994e1

chore: remove uses of cases' (#9171)

I literally went through and regex'd some uses of cases', replacing them with rcases; this is meant to be a low effort PR as I hope that tools can do this in the future.

rcases is an easier replacement than cases, though with better tools we could in future do a second pass converting simple rcases added here (and existing ones) to cases.

3fca282c

Diff

@@ -127,7 +127,7 @@ theorem choose_mul_factorial_mul_factorial : ∀ {n k}, k ≤ n → choose n k *
   | 0, _, hk => by simp [Nat.eq_zero_of_le_zero hk]
   | n + 1, 0, _ => by simp
   | n + 1, succ k, hk => by
-    cases' lt_or_eq_of_le hk with hk₁ hk₁
+    rcases lt_or_eq_of_le hk with hk₁ | hk₁
     · have h : choose n k * k.succ ! * (n - k)! = (k + 1) * n ! := by
         rw [← choose_mul_factorial_mul_factorial (le_of_succ_le_succ hk)]
         simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
@@ -303,7 +303,7 @@ private theorem choose_le_middle_of_le_half_left {n r : ℕ} (hr : r ≤ n / 2)
 /-- `choose n r` is maximised when `r` is `n/2`. -/
 theorem choose_le_middle (r n : ℕ) : choose n r ≤ choose n (n / 2) := by
   cases' le_or_gt r n with b b
-  · cases' le_or_lt r (n / 2) with a h
+  · rcases le_or_lt r (n / 2) with a | h
     · apply choose_le_middle_of_le_half_left a
     · rw [← choose_symm b]
       apply choose_le_middle_of_le_half_left

2f3994e1

chore: avoid lean3 style have/suffices (#6964)

Many proofs use the "stream of consciousness" style from Lean 3, rather than have ... := or suffices ... from/by.

This PR updates a fraction of these to the preferred Lean 4 style.

I think a good goal would be to delete the "deferred" versions of have, suffices, and let at the bottom of Mathlib.Tactic.Have

(Anyone who would like to contribute more cleanup is welcome to push directly to this branch.)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

bdc47f68

Diff

@@ -183,8 +183,8 @@ theorem factorial_mul_factorial_dvd_factorial {n k : ℕ} (hk : k ≤ n) : k ! *
 #align nat.factorial_mul_factorial_dvd_factorial Nat.factorial_mul_factorial_dvd_factorial
 
 theorem factorial_mul_factorial_dvd_factorial_add (i j : ℕ) : i ! * j ! ∣ (i + j)! := by
-  suffices : i ! * (i + j - i) ! ∣ (i + j)!
-  · rwa [add_tsub_cancel_left i j] at this
+  suffices i ! * (i + j - i) ! ∣ (i + j)! by
+    rwa [add_tsub_cancel_left i j] at this
   exact factorial_mul_factorial_dvd_factorial (Nat.le_add_right _ _)
 #align nat.factorial_mul_factorial_dvd_factorial_add Nat.factorial_mul_factorial_dvd_factorial_add
 
@@ -195,8 +195,8 @@ theorem choose_symm {n k : ℕ} (hk : k ≤ n) : choose n (n - k) = choose n k :
 #align nat.choose_symm Nat.choose_symm
 
 theorem choose_symm_of_eq_add {n a b : ℕ} (h : n = a + b) : Nat.choose n a = Nat.choose n b := by
-  suffices : choose n (n - b) = choose n b
-  · rw [h, add_tsub_cancel_right] at this; rwa [h]
+  suffices choose n (n - b) = choose n b by
+    rw [h, add_tsub_cancel_right] at this; rwa [h]
   exact choose_symm (h ▸ le_add_left _ _)
 #align nat.choose_symm_of_eq_add Nat.choose_symm_of_eq_add
 
@@ -210,8 +210,8 @@ theorem choose_symm_half (m : ℕ) : choose (2 * m + 1) (m + 1) = choose (2 * m
 #align nat.choose_symm_half Nat.choose_symm_half
 
 theorem choose_succ_right_eq (n k : ℕ) : choose n (k + 1) * (k + 1) = choose n k * (n - k) := by
-  have e : (n + 1) * choose n k = choose n k * (k + 1) + choose n (k + 1) * (k + 1)
-  rw [← right_distrib, ← choose_succ_succ, succ_mul_choose_eq]
+  have e : (n + 1) * choose n k = choose n k * (k + 1) + choose n (k + 1) * (k + 1) := by
+    rw [← right_distrib, ← choose_succ_succ, succ_mul_choose_eq]
   rw [← tsub_eq_of_eq_add_rev e, mul_comm, ← mul_tsub, add_tsub_add_eq_tsub_right]
 #align nat.choose_succ_right_eq Nat.choose_succ_right_eq

2f3994e1

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2018 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Bhavik Mehta, Stuart Presnell
-
-! This file was ported from Lean 3 source module data.nat.choose.basic
-! leanprover-community/mathlib commit 2f3994e1b117b1e1da49bcfb67334f33460c3ce4
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Nat.Factorial.Basic
 
+#align_import data.nat.choose.basic from "leanprover-community/mathlib"@"2f3994e1b117b1e1da49bcfb67334f33460c3ce4"
+
 /-!
 # Binomial coefficients

2f3994e1

chore: remove a few superfluous semicolons (#5880)

Alongside any necessary spacing/flow changes to accommodate their removal.

870068af

Diff

@@ -109,8 +109,8 @@ theorem choose_pos : ∀ {n k}, k ≤ n → 0 < choose n k
   | 0, _, hk => by rw [Nat.eq_zero_of_le_zero hk]; decide
   | n + 1, 0, _ => by simp
   | n + 1, k + 1, hk => by
-    rw [choose_succ_succ];
-      exact add_pos_of_pos_of_nonneg (choose_pos (le_of_succ_le_succ hk)) (Nat.zero_le _)
+    rw [choose_succ_succ]
+    exact add_pos_of_pos_of_nonneg (choose_pos (le_of_succ_le_succ hk)) (Nat.zero_le _)
 #align nat.choose_pos Nat.choose_pos
 
 theorem choose_eq_zero_iff {n k : ℕ} : n.choose k = 0 ↔ n < k :=
@@ -132,13 +132,13 @@ theorem choose_mul_factorial_mul_factorial : ∀ {n k}, k ≤ n → choose n k *
   | n + 1, succ k, hk => by
     cases' lt_or_eq_of_le hk with hk₁ hk₁
     · have h : choose n k * k.succ ! * (n - k)! = (k + 1) * n ! := by
-        rw [← choose_mul_factorial_mul_factorial (le_of_succ_le_succ hk)];
-          simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
+        rw [← choose_mul_factorial_mul_factorial (le_of_succ_le_succ hk)]
+        simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
       have h₁ : (n - k)! = (n - k) * (n - k.succ)! := by
         rw [← succ_sub_succ, succ_sub (le_of_lt_succ hk₁), factorial_succ]
       have h₂ : choose n (succ k) * k.succ ! * ((n - k) * (n - k.succ)!) = (n - k) * n ! := by
-        rw [← choose_mul_factorial_mul_factorial (le_of_lt_succ hk₁)];
-          simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
+        rw [← choose_mul_factorial_mul_factorial (le_of_lt_succ hk₁)]
+        simp [factorial_succ, mul_comm, mul_left_comm, mul_assoc]
       have h₃ : k * n ! ≤ n * n ! := Nat.mul_le_mul_right _ (le_of_succ_le_succ hk)
       rw [choose_succ_succ, add_mul, add_mul, succ_sub_succ, h, h₁, h₂, add_mul, tsub_mul,
         factorial_succ, ← add_tsub_assoc_of_le h₃, add_assoc, ← add_mul, add_tsub_cancel_left,

2f3994e1

chore: fix focusing dots (#5708)

This PR is the result of running

find . -type f -name "*.lean" -exec sed -i -E 's/^( +)\. /\1· /' {} \;
find . -type f -name "*.lean" -exec sed -i -E 'N;s/^( +·)\n +(.*)$/\1 \2/;P;D' {} \;

which firstly replaces . focusing dots with · and secondly removes isolated instances of such dots, unifying them with the following line. A new rule is placed in the style linter to verify this.

cb02d09e

Diff

@@ -100,7 +100,7 @@ theorem triangle_succ (n : ℕ) : (n + 1) * (n + 1 - 1) / 2 = n * (n - 1) / 2 +
 /-- `choose n 2` is the `n`-th triangle number. -/
 theorem choose_two_right (n : ℕ) : choose n 2 = n * (n - 1) / 2 := by
   induction' n with n ih
-  . simp
+  · simp
   · rw [triangle_succ n, choose, ih]
     simp [add_comm]
 #align nat.choose_two_right Nat.choose_two_right
@@ -187,7 +187,7 @@ theorem factorial_mul_factorial_dvd_factorial {n k : ℕ} (hk : k ≤ n) : k ! *
 
 theorem factorial_mul_factorial_dvd_factorial_add (i j : ℕ) : i ! * j ! ∣ (i + j)! := by
   suffices : i ! * (i + j - i) ! ∣ (i + j)!
-  . rwa [add_tsub_cancel_left i j] at this
+  · rwa [add_tsub_cancel_left i j] at this
   exact factorial_mul_factorial_dvd_factorial (Nat.le_add_right _ _)
 #align nat.factorial_mul_factorial_dvd_factorial_add Nat.factorial_mul_factorial_dvd_factorial_add
 
@@ -199,7 +199,7 @@ theorem choose_symm {n k : ℕ} (hk : k ≤ n) : choose n (n - k) = choose n k :
 
 theorem choose_symm_of_eq_add {n a b : ℕ} (h : n = a + b) : Nat.choose n a = Nat.choose n b := by
   suffices : choose n (n - b) = choose n b
-  . rw [h, add_tsub_cancel_right] at this; rwa [h]
+  · rw [h, add_tsub_cancel_right] at this; rwa [h]
   exact choose_symm (h ▸ le_add_left _ _)
 #align nat.choose_symm_of_eq_add Nat.choose_symm_of_eq_add

2f3994e1

Data.Nat.Choose.Basic: Register a faster implementation (#3915)

Co-authored-by: Kyle Miller <kmill31415@gmail.com>

3b028f2d

Diff

@@ -273,6 +273,14 @@ theorem choose_eq_descFactorial_div_factorial (n k : ℕ) : n.choose k = n.descF
   exact (Nat.mul_div_cancel' <| factorial_dvd_descFactorial _ _).symm
 #align nat.choose_eq_desc_factorial_div_factorial Nat.choose_eq_descFactorial_div_factorial
 
+/-- A faster implementation of `choose`, to be used during bytecode evaluation
+and in compiled code. -/
+def fast_choose n k := Nat.descFactorial n k / Nat.factorial k
+
+@[csimp] lemma choose_eq_fast_choose : Nat.choose = fast_choose :=
+  funext (fun _ => funext (Nat.choose_eq_descFactorial_div_factorial _))
+
+
 /-! ### Inequalities -/

2f3994e1

chore: fix #align lines (#3640)

This PR fixes two things:

Most align statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align). This is often seen in the mathport output after ending calc blocks.
All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)

2b42dc7c

Diff

@@ -163,7 +163,6 @@ theorem choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
     _ = n.choose s * (n - s).choose (k - s) * ((n - k)! * (k - s)! * s !) :=
       by rw [tsub_tsub_tsub_cancel_right hsk, mul_assoc, mul_left_comm s !, mul_assoc,
         mul_comm (k - s)!, mul_comm s !, mul_right_comm, ← mul_assoc]
-
 #align nat.choose_mul Nat.choose_mul
 
 theorem choose_eq_factorial_div_factorial {n k : ℕ} (hk : k ≤ n) :

2f3994e1

feat: Port Data.Nat.Choose.Central (#2140)

Co-authored-by: Frédéric Dupuis <dupuisf@iro.umontreal.ca>

8c618051

Diff

@@ -65,6 +65,9 @@ theorem choose_succ_succ (n k : ℕ) : choose (succ n) (succ k) = choose n k + c
   rfl
 #align nat.choose_succ_succ Nat.choose_succ_succ
 
+theorem choose_succ_succ' (n k : ℕ) : choose (n + 1) (k + 1) = choose n k + choose n (k + 1) :=
+  rfl
+
 theorem choose_eq_zero_of_lt : ∀ {n k}, n < k → choose n k = 0
   | _, 0, hk => absurd hk (Nat.not_lt_zero _)
   | 0, k + 1, _ => choose_zero_succ _

2f3994e1

chore: format by line breaks with long lines (#1529)

This was done semi-automatically with some regular expressions in vim in contrast to the fully automatic https://github.com/leanprover-community/mathlib4/pull/1523.

Co-authored-by: Moritz Firsching <firsching@google.com>

1050066f

Diff

@@ -275,8 +275,8 @@ theorem choose_eq_descFactorial_div_factorial (n k : ℕ) : n.choose k = n.descF
 
 
 /-- Show that `Nat.choose` is increasing for small values of the right argument. -/
-theorem choose_le_succ_of_lt_half_left {r n : ℕ} (h : r < n / 2) : choose n r ≤ choose n (r + 1) :=
-  by
+theorem choose_le_succ_of_lt_half_left {r n : ℕ} (h : r < n / 2) :
+    choose n r ≤ choose n (r + 1) := by
   refine' le_of_mul_le_mul_right _ (lt_tsub_iff_left.mpr (lt_of_lt_of_le h (n.div_le_self 2)))
   rw [← choose_succ_right_eq]
   apply Nat.mul_le_mul_left

2f3994e1

chore: format by line breaks (#1523)

During porting, I usually fix the desired format we seem to want for the line breaks around by with

awk '{do {{if (match($0, "^  by$") && length(p) < 98) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}' Mathlib/File/Im/Working/On.lean

I noticed there are some more files that slipped through.

This pull request is the result of running this command:

grep -lr "^  by\$" Mathlib | xargs -n 1 awk -i inplace '{do {{if (match($0, "^  by$") && length(p) < 98 && not (match(p, "^[ \t]*--"))) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}'

Co-authored-by: Moritz Firsching <firsching@google.com>

d6d859a7

Diff

@@ -253,8 +253,7 @@ theorem choose_eq_asc_factorial_div_factorial (n k : ℕ) :
   exact (Nat.mul_div_cancel' <| factorial_dvd_ascFactorial _ _).symm
 #align nat.choose_eq_asc_factorial_div_factorial Nat.choose_eq_asc_factorial_div_factorial
 
-theorem descFactorial_eq_factorial_mul_choose (n k : ℕ) : n.descFactorial k = k ! * n.choose k :=
-  by
+theorem descFactorial_eq_factorial_mul_choose (n k : ℕ) : n.descFactorial k = k ! * n.choose k := by
   obtain h | h := Nat.lt_or_ge n k
   · rw [descFactorial_eq_zero_iff_lt.2 h, choose_eq_zero_of_lt h, mul_zero]
   rw [mul_comm]
@@ -266,8 +265,7 @@ theorem factorial_dvd_descFactorial (n k : ℕ) : k ! ∣ n.descFactorial k :=
   ⟨n.choose k, descFactorial_eq_factorial_mul_choose _ _⟩
 #align nat.factorial_dvd_desc_factorial Nat.factorial_dvd_descFactorial
 
-theorem choose_eq_descFactorial_div_factorial (n k : ℕ) : n.choose k = n.descFactorial k / k ! :=
-  by
+theorem choose_eq_descFactorial_div_factorial (n k : ℕ) : n.choose k = n.descFactorial k / k ! := by
   apply mul_left_cancel₀ (factorial_ne_zero k)
   rw [← descFactorial_eq_factorial_mul_choose]
   exact (Nat.mul_div_cancel' <| factorial_dvd_descFactorial _ _).symm

2f3994e1

feat: refactor of solve_by_elim (#856)

This is a thorough refactor of solve_by_elim.

Bug fixes and additional tests.
Support for removing local hypotheses using solve_by_elim [-h].
Use symm on hypotheses and exfalso on the goal, as needed.
To support that, MetaM level tooling for the symm tactic. (rfl and trans deserve the same treatment at some point.)
Additional hooks for flow control in solve_by_elim (suspending goals to return to the user, rejecting branches, running arbitrary procedures on the goals).
Using those hooks, reimplement apply_assumption and apply_rules as thin wrappers around solve_by_elim, allowing access to new features (removing hypotheses, symm and exfalso) for free.
Using those hooks, fix library_search using so example (P Q : List ℕ) (h : ℕ) : List ℕ := by library_search using P, Q -- exact P ∩ Q

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

a445a5e1

Diff

@@ -145,7 +145,7 @@ theorem choose_mul_factorial_mul_factorial : ∀ {n k}, k ≤ n → choose n k *
 
 theorem choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
     n.choose k * k.choose s = n.choose s * (n - s).choose (k - s) :=
-  have h : (n - k)! * (k - s)! * s ! ≠ 0:= by apply_rules [factorial_ne_zero, mul_ne_zero]
+  have h : (n - k)! * (k - s)! * s ! ≠ 0 := by apply_rules [factorial_ne_zero, mul_ne_zero]
   mul_right_cancel₀ h <|
   calc
     n.choose k * k.choose s * ((n - k)! * (k - s)! * s !) =

2f3994e1

chore: tidy various files (#1311)

489ab6d0

Diff

@@ -223,12 +223,14 @@ theorem choose_succ_self_right : ∀ n : ℕ, (n + 1).choose n = n + 1
 #align nat.choose_succ_self_right Nat.choose_succ_self_right
 
 theorem choose_mul_succ_eq (n k : ℕ) : n.choose k * (n + 1) = (n + 1).choose k * (n + 1 - k) := by
-  induction' k with k _; · simp
-  obtain hk | hk := le_or_lt (k + 1) (n + 1)
-  ·
-    rw [choose_succ_succ, add_mul, succ_sub_succ, ← choose_succ_right_eq, ← succ_sub_succ, mul_tsub,
-      add_tsub_cancel_of_le (Nat.mul_le_mul_left _ hk)]
-  rw [choose_eq_zero_of_lt hk, choose_eq_zero_of_lt (n.lt_succ_self.trans hk), zero_mul, zero_mul]
+  cases k with
+  | zero => simp
+  | succ k =>
+    obtain hk | hk := le_or_lt (k + 1) (n + 1)
+    · rw [choose_succ_succ, add_mul, succ_sub_succ, ← choose_succ_right_eq, ← succ_sub_succ,
+        mul_tsub, add_tsub_cancel_of_le (Nat.mul_le_mul_left _ hk)]
+    · rw [choose_eq_zero_of_lt hk, choose_eq_zero_of_lt (n.lt_succ_self.trans hk), zero_mul,
+        zero_mul]
 #align nat.choose_mul_succ_eq Nat.choose_mul_succ_eq
 
 theorem ascFactorial_eq_factorial_mul_choose (n k : ℕ) :

2f3994e1

refactor: use Is*CancelMulZero (#1137)

This is a Lean 4 version of leanprover-community/mathlib#17963

3bc62129

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Bhavik Mehta, Stuart Presnell
 
 ! This file was ported from Lean 3 source module data.nat.choose.basic
-! leanprover-community/mathlib commit d012cd09a9b256d870751284dd6a29882b0be105
+! leanprover-community/mathlib commit 2f3994e1b117b1e1da49bcfb67334f33460c3ce4
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -144,10 +144,9 @@ theorem choose_mul_factorial_mul_factorial : ∀ {n k}, k ≤ n → choose n k *
 #align nat.choose_mul_factorial_mul_factorial Nat.choose_mul_factorial_mul_factorial
 
 theorem choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :
-    n.choose k * k.choose s = n.choose s * (n - s).choose (k - s) := by
-  have h : 0 < (n - k)! * (k - s)! * s ! :=
-    mul_pos (mul_pos (factorial_pos _) (factorial_pos _)) (factorial_pos _)
-  refine' eq_of_mul_eq_mul_right h _
+    n.choose k * k.choose s = n.choose s * (n - s).choose (k - s) :=
+  have h : (n - k)! * (k - s)! * s ! ≠ 0:= by apply_rules [factorial_ne_zero, mul_ne_zero]
+  mul_right_cancel₀ h <|
   calc
     n.choose k * k.choose s * ((n - k)! * (k - s)! * s !) =
         n.choose k * (k.choose s * s ! * (k - s)!) * (n - k)! :=

d012cd09

feat port: Data.Nat.Choose.Basic (#1073)

d012cd09

4a230a9b

`data.nat.choose.basic` ⟷ `Mathlib.Data.Nat.Choose.Basic`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Other changes

Dependencies 2 + 115

data.nat.choose.basic ⟷ Mathlib.Data.Nat.Choose.Basic

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Other changes

Dependencies 2 + 115

`data.nat.choose.basic` ⟷ `Mathlib.Data.Nat.Choose.Basic`