data.nat.factorial.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

d012cd09

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

c3291da4

bump to nightly-2024-04-09-08

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

659ec6f7

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
-import Data.Nat.Defs
+import Algebra.Group.Nat
 import Data.Nat.Pow
 
 #align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"c3291da49cfa65f0d43b094750541c0731edc932"

c3291da4

bump to nightly-2024-04-06-08

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

e34029c9

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
-import Data.Nat.Basic
+import Data.Nat.Defs
 import Data.Nat.Pow
 
 #align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"c3291da49cfa65f0d43b094750541c0731edc932"
@@ -117,7 +117,7 @@ theorem factorial_le {m n} (h : m ≤ n) : m ! ≤ n ! :=
 theorem factorial_mul_pow_le_factorial : ∀ {m n : ℕ}, m ! * m.succ ^ n ≤ (m + n)!
   | m, 0 => by simp
   | m, n + 1 => by
-    rw [← add_assoc, Nat.factorial_succ, mul_comm (Nat.succ _), pow_succ', ← mul_assoc] <;>
+    rw [← add_assoc, Nat.factorial_succ, mul_comm (Nat.succ _), pow_succ, ← mul_assoc] <;>
       exact
         mul_le_mul factorial_mul_pow_le_factorial (Nat.succ_le_succ (Nat.le_add_right _ _))
           (Nat.zero_le _) (Nat.zero_le _)
@@ -333,7 +333,7 @@ theorem ascFactorial_of_sub {n k : ℕ} (h : k < n) :
 theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, (n + 1) ^ k ≤ n.ascFactorial k
   | 0 => by rw [asc_factorial_zero, pow_zero]
   | k + 1 => by
-    rw [pow_succ]
+    rw [pow_succ']
     exact Nat.mul_le_mul (Nat.add_le_add_right le_self_add _) (pow_succ_le_asc_factorial k)
 #align nat.pow_succ_le_asc_factorial Nat.pow_succ_le_ascFactorial
 -/
@@ -341,7 +341,7 @@ theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, (n + 1) ^ k ≤ n.ascF
 #print Nat.pow_lt_ascFactorial' /-
 theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < n.ascFactorial (k + 2) :=
   by
-  rw [pow_succ]
+  rw [pow_succ']
   exact
     Nat.mul_lt_mul (Nat.add_lt_add_right (Nat.lt_add_of_pos_right succ_pos') 1)
       (pow_succ_le_asc_factorial n _) (pow_pos succ_pos' _)
@@ -360,7 +360,7 @@ theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k <
 theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, n.ascFactorial k ≤ (n + k) ^ k
   | 0 => by rw [asc_factorial_zero, pow_zero]
   | k + 1 => by
-    rw [asc_factorial_succ, pow_succ]
+    rw [asc_factorial_succ, pow_succ']
     exact
       Nat.mul_le_mul_of_nonneg_left
         ((asc_factorial_le_pow_add k).trans (Nat.pow_le_pow_left (le_succ _) _))
@@ -372,7 +372,7 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFact
   | 0 => by rintro ⟨⟩
   | 1 => by rintro (_ | ⟨⟨⟩⟩)
   | k + 2 => fun _ => by
-    rw [asc_factorial_succ, pow_succ]
+    rw [asc_factorial_succ, pow_succ']
     refine'
       Nat.mul_lt_mul' le_rfl
         ((asc_factorial_le_pow_add n _).trans_lt (pow_lt_pow_left (lt_add_one _) (succ_pos _)))
@@ -505,7 +505,7 @@ theorem descFactorial_eq_div {n k : ℕ} (h : k ≤ n) : n.descFactorial k = n !
 theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.descFactorial k
   | 0 => by rw [desc_factorial_zero, pow_zero]
   | k + 1 => by
-    rw [desc_factorial_succ, pow_succ, succ_sub_succ]
+    rw [desc_factorial_succ, pow_succ', succ_sub_succ]
     exact
       Nat.mul_le_mul_of_nonneg_left
         (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
@@ -517,12 +517,12 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
 theorem pow_sub_lt_descFactorial' {n : ℕ} :
     ∀ {k : ℕ}, k + 2 ≤ n → (n - (k + 1)) ^ (k + 2) < n.descFactorial (k + 2)
   | 0 => fun h => by
-    rw [desc_factorial_succ, pow_succ, pow_one, desc_factorial_one]
+    rw [desc_factorial_succ, pow_succ', pow_one, desc_factorial_one]
     exact
       Nat.mul_lt_mul_of_pos_left (tsub_lt_self (lt_of_lt_of_le zero_lt_two h) zero_lt_one)
         (tsub_pos_of_lt h)
   | k + 1 => fun h => by
-    rw [desc_factorial_succ, pow_succ]
+    rw [desc_factorial_succ, pow_succ']
     refine'
       Nat.mul_lt_mul_of_pos_left
         ((Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _) (tsub_pos_of_lt h)
@@ -544,7 +544,7 @@ theorem pow_sub_lt_descFactorial {n : ℕ} :
 theorem descFactorial_le_pow (n : ℕ) : ∀ k : ℕ, n.descFactorial k ≤ n ^ k
   | 0 => by rw [desc_factorial_zero, pow_zero]
   | k + 1 => by
-    rw [desc_factorial_succ, pow_succ]
+    rw [desc_factorial_succ, pow_succ']
     exact Nat.mul_le_mul (Nat.sub_le _ _) (desc_factorial_le_pow k)
 #align nat.desc_factorial_le_pow Nat.descFactorial_le_pow
 -/
@@ -554,7 +554,7 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
   | 0 => by rintro ⟨⟩
   | 1 => by rintro (_ | ⟨⟨⟩⟩)
   | k + 2 => fun _ => by
-    rw [desc_factorial_succ, pow_succ', mul_comm]
+    rw [desc_factorial_succ, pow_succ, mul_comm]
     exact
       Nat.mul_lt_mul' (desc_factorial_le_pow _ _) (tsub_lt_self hn k.zero_lt_succ) (pow_pos hn _)
 #align nat.desc_factorial_lt_pow Nat.descFactorial_lt_pow

c3291da4

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -163,11 +163,11 @@ theorem factorial_inj (hn : 1 < n !) : n ! = m ! ↔ n = m :=
   by
   refine' ⟨fun h => _, congr_arg _⟩
   obtain hnm | rfl | hnm := lt_trichotomy n m
-  · rw [← factorial_lt <| pos_of_gt <| one_lt_factorial.mp hn, h] at hnm 
+  · rw [← factorial_lt <| pos_of_gt <| one_lt_factorial.mp hn, h] at hnm
     cases lt_irrefl _ hnm
   · rfl
-  rw [h, one_lt_factorial] at hn 
-  rw [← factorial_lt (lt_trans one_pos hn), h] at hnm 
+  rw [h, one_lt_factorial] at hn
+  rw [← factorial_lt (lt_trans one_pos hn), h] at hnm
   cases lt_irrefl _ hnm
 #align nat.factorial_inj Nat.factorial_inj
 -/

c3291da4

bump to nightly-2023-12-20-06

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

058cd493

Diff

@@ -243,7 +243,7 @@ theorem factorial_mul_pow_sub_le_factorial {n m : ℕ} (hnm : n ≤ m) : n ! * n
   suffices n ! * (n + 1) ^ (m - n) ≤ m ! by
     apply trans _ this
     rw [mul_le_mul_left]
-    apply pow_le_pow_of_le_left (zero_le n) (le_succ n)
+    apply pow_le_pow_left (zero_le n) (le_succ n)
     exact factorial_pos n
   convert Nat.factorial_mul_pow_le_factorial
   exact (add_tsub_cancel_of_le hnm).symm
@@ -363,7 +363,7 @@ theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, n.ascFactorial k ≤ (n
     rw [asc_factorial_succ, pow_succ]
     exact
       Nat.mul_le_mul_of_nonneg_left
-        ((asc_factorial_le_pow_add k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
+        ((asc_factorial_le_pow_add k).trans (Nat.pow_le_pow_left (le_succ _) _))
 #align nat.asc_factorial_le_pow_add Nat.ascFactorial_le_pow_add
 -/
 
@@ -375,8 +375,7 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFact
     rw [asc_factorial_succ, pow_succ]
     refine'
       Nat.mul_lt_mul' le_rfl
-        ((asc_factorial_le_pow_add n _).trans_lt
-          (pow_lt_pow_of_lt_left (lt_add_one _) (succ_pos _)))
+        ((asc_factorial_le_pow_add n _).trans_lt (pow_lt_pow_left (lt_add_one _) (succ_pos _)))
         (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
 -/
@@ -509,7 +508,7 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
     rw [desc_factorial_succ, pow_succ, succ_sub_succ]
     exact
       Nat.mul_le_mul_of_nonneg_left
-        (le_trans (Nat.pow_le_pow_of_le_left (tsub_le_tsub_right (le_succ _) _) k)
+        (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
           (pow_sub_le_desc_factorial k))
 #align nat.pow_sub_le_desc_factorial Nat.pow_sub_le_descFactorial
 -/
@@ -526,8 +525,7 @@ theorem pow_sub_lt_descFactorial' {n : ℕ} :
     rw [desc_factorial_succ, pow_succ]
     refine'
       Nat.mul_lt_mul_of_pos_left
-        ((Nat.pow_le_pow_of_le_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _)
-        (tsub_pos_of_lt h)
+        ((Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _) (tsub_pos_of_lt h)
     rw [succ_sub_succ]
     exact pow_sub_lt_desc_factorial' ((le_succ _).trans h)
 #align nat.pow_sub_lt_desc_factorial' Nat.pow_sub_lt_descFactorial'

c3291da4

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
-import Mathbin.Data.Nat.Basic
-import Mathbin.Data.Nat.Pow
+import Data.Nat.Basic
+import Data.Nat.Pow
 
 #align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"c3291da49cfa65f0d43b094750541c0731edc932"

c3291da4

bump to nightly-2023-08-23-23

mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504

f612b9e0

Diff

@@ -467,7 +467,7 @@ theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial
 #align nat.desc_factorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt
 -/
 
-alias desc_factorial_eq_zero_iff_lt ↔ _ desc_factorial_of_lt
+alias ⟨_, desc_factorial_of_lt⟩ := desc_factorial_eq_zero_iff_lt
 #align nat.desc_factorial_of_lt Nat.descFactorial_of_lt
 
 #print Nat.add_descFactorial_eq_ascFactorial /-

c3291da4

bump to nightly-2023-08-17-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504

60285dcc

Diff

@@ -96,7 +96,7 @@ theorem factorial_dvd_factorial {m n} (h : m ≤ n) : m ! ∣ n ! :=
   · simp [Nat.eq_zero_of_le_zero h]
   obtain rfl | hl := h.eq_or_lt
   · simp
-  exact (IH (le_of_lt_succ hl)).mul_left _
+  exact (IH (le_of_lt_succ hl)).hMul_left _
 #align nat.factorial_dvd_factorial Nat.factorial_dvd_factorial
 -/

c3291da4

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
-
-! This file was ported from Lean 3 source module data.nat.factorial.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.Basic
 import Mathbin.Data.Nat.Pow
 
+#align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"c3291da49cfa65f0d43b094750541c0731edc932"
+
 /-!
 # Factorial and variants

c3291da4

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -39,7 +39,6 @@ def factorial : ℕ → ℕ
 #align nat.factorial Nat.factorial
 -/
 
--- mathport name: nat.factorial
 scoped notation:10000 n "!" => Nat.factorial n
 
 section Factorial

c3291da4

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -167,11 +167,11 @@ theorem factorial_inj (hn : 1 < n !) : n ! = m ! ↔ n = m :=
   by
   refine' ⟨fun h => _, congr_arg _⟩
   obtain hnm | rfl | hnm := lt_trichotomy n m
-  · rw [← factorial_lt <| pos_of_gt <| one_lt_factorial.mp hn, h] at hnm
+  · rw [← factorial_lt <| pos_of_gt <| one_lt_factorial.mp hn, h] at hnm 
     cases lt_irrefl _ hnm
   · rfl
-  rw [h, one_lt_factorial] at hn
-  rw [← factorial_lt (lt_trans one_pos hn), h] at hnm
+  rw [h, one_lt_factorial] at hn 
+  rw [← factorial_lt (lt_trans one_pos hn), h] at hnm 
   cases lt_irrefl _ hnm
 #align nat.factorial_inj Nat.factorial_inj
 -/

c3291da4

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -489,9 +489,7 @@ theorem add_descFactorial_eq_ascFactorial (n : ℕ) :
 for the version using ℕ-division. -/
 theorem factorial_mul_descFactorial : ∀ {n k : ℕ}, k ≤ n → (n - k)! * n.descFactorial k = n !
   | n, 0 => fun _ => by rw [desc_factorial_zero, mul_one, tsub_zero]
-  | 0, succ k => fun h => by
-    exfalso
-    exact not_succ_le_zero k h
+  | 0, succ k => fun h => by exfalso; exact not_succ_le_zero k h
   | succ n, succ k => fun h => by
     rw [succ_desc_factorial_succ, succ_sub_succ, ← mul_assoc, mul_comm (n - k)!, mul_assoc,
       factorial_mul_desc_factorial (Nat.succ_le_succ_iff.1 h), factorial_succ]
@@ -544,9 +542,7 @@ theorem pow_sub_lt_descFactorial {n : ℕ} :
     ∀ {k : ℕ}, 2 ≤ k → k ≤ n → (n + 1 - k) ^ k < n.descFactorial k
   | 0 => by rintro ⟨⟩
   | 1 => by rintro (_ | ⟨⟨⟩⟩)
-  | k + 2 => fun _ h => by
-    rw [succ_sub_succ]
-    exact pow_sub_lt_desc_factorial' h
+  | k + 2 => fun _ h => by rw [succ_sub_succ]; exact pow_sub_lt_desc_factorial' h
 #align nat.pow_sub_lt_desc_factorial Nat.pow_sub_lt_descFactorial
 -/

c3291da4

bump to nightly-2023-03-11-16

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

cd44fb92

Diff

@@ -421,7 +421,7 @@ theorem descFactorial_succ (n k : ℕ) : n.descFactorial k.succ = (n - k) * n.de
 
 #print Nat.zero_descFactorial_succ /-
 theorem zero_descFactorial_succ (k : ℕ) : (0 : ℕ).descFactorial k.succ = 0 := by
-  rw [desc_factorial_succ, zero_tsub, zero_mul]
+  rw [desc_factorial_succ, zero_tsub, MulZeroClass.zero_mul]
 #align nat.zero_desc_factorial_succ Nat.zero_descFactorial_succ
 -/

c3291da4

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

d012cd09

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

@@ -3,9 +3,7 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
-import Mathlib.Algebra.Divisibility.Basic
-import Mathlib.Data.Nat.Basic
-import Mathlib.Order.Monotone.Basic
+import Mathlib.Data.Nat.Defs
 import Mathlib.Tactic.GCongr.Core
 import Mathlib.Tactic.Common
 import Mathlib.Tactic.Monotonicity.Attr
@@ -73,15 +71,13 @@ theorem factorial_ne_zero (n : ℕ) : n ! ≠ 0 :=
 #align nat.factorial_ne_zero Nat.factorial_ne_zero
 
 theorem factorial_dvd_factorial {m n} (h : m ≤ n) : m ! ∣ n ! := by
-  induction' n with n IH
-  · simp [Nat.eq_zero_of_le_zero h]
-  obtain rfl | hl := h.eq_or_lt
-  · simp
-  exact (IH (le_of_lt_succ hl)).mul_left _
+  induction' h with n _ ih
+  · exact Nat.dvd_refl _
+  · exact Nat.dvd_trans ih (Nat.dvd_mul_left _ _)
 #align nat.factorial_dvd_factorial Nat.factorial_dvd_factorial
 
 theorem dvd_factorial : ∀ {m n}, 0 < m → m ≤ n → m ∣ n !
-  | succ _, _, _, h => dvd_of_mul_right_dvd (factorial_dvd_factorial h)
+  | succ _, _, _, h => Nat.dvd_trans (Nat.dvd_mul_right _ _) (factorial_dvd_factorial h)
 #align nat.dvd_factorial Nat.dvd_factorial
 
 @[mono, gcongr]
@@ -92,22 +88,19 @@ theorem factorial_le {m n} (h : m ≤ n) : m ! ≤ n ! :=
 theorem factorial_mul_pow_le_factorial : ∀ {m n : ℕ}, m ! * (m + 1) ^ n ≤ (m + n)!
   | m, 0 => by simp
   | m, n + 1 => by
-    rw [← add_assoc, factorial_succ, mul_comm (_ + 1), Nat.pow_succ, ← mul_assoc]
+    rw [← Nat.add_assoc, factorial_succ, Nat.mul_comm (_ + 1), Nat.pow_succ, ← Nat.mul_assoc]
     exact Nat.mul_le_mul factorial_mul_pow_le_factorial (succ_le_succ (le_add_right _ _))
 #align nat.factorial_mul_pow_le_factorial Nat.factorial_mul_pow_le_factorial
 
-theorem monotone_factorial : Monotone factorial := fun _ _ => factorial_le
-#align nat.monotone_factorial Nat.monotone_factorial
-
 theorem factorial_lt (hn : 0 < n) : n ! < m ! ↔ n < m := by
-  refine' ⟨fun h => not_le.mp fun hmn => not_le_of_lt h (factorial_le hmn), fun h => _⟩
+  refine' ⟨fun h => not_le.mp fun hmn => Nat.not_le_of_lt h (factorial_le hmn), fun h => _⟩
   have : ∀ {n}, 0 < n → n ! < (n + 1)! := by
     intro k hk
     rw [factorial_succ, succ_mul, Nat.lt_add_left_iff_pos]
     exact Nat.mul_pos hk k.factorial_pos
   induction' h with k hnk ih generalizing hn
   · exact this hn
-  · exact (ih hn).trans (this <| hn.trans <| lt_of_succ_le hnk)
+  · exact lt_trans (ih hn) $ this <| lt_trans hn <| lt_of_succ_le hnk
 #align nat.factorial_lt Nat.factorial_lt
 
 @[gcongr]
@@ -147,25 +140,19 @@ theorem self_le_factorial : ∀ n : ℕ, n ≤ n !
 #align nat.self_le_factorial Nat.self_le_factorial
 
 theorem lt_factorial_self {n : ℕ} (hi : 3 ≤ n) : n < n ! := by
-  have : 0 < n := Nat.zero_lt_two.trans (succ_le_iff.mp hi)
+  have : 0 < n := by omega
   have hn : 1 < pred n := le_pred_of_lt (succ_le_iff.mp hi)
   rw [← succ_pred_eq_of_pos ‹0 < n›, factorial_succ]
-  exact (Nat.lt_mul_iff_one_lt_right (pred n).succ_pos).2 (hn.trans_le (self_le_factorial _))
+  exact (Nat.lt_mul_iff_one_lt_right (pred n).succ_pos).2
+    ((Nat.lt_of_lt_of_le hn (self_le_factorial _)))
 #align nat.lt_factorial_self Nat.lt_factorial_self
 
 theorem add_factorial_succ_lt_factorial_add_succ {i : ℕ} (n : ℕ) (hi : 2 ≤ i) :
     i + (n + 1)! < (i + n + 1)! := by
-  rw [factorial_succ (i + _), add_mul, one_mul]
-  have : i ≤ i + n := le.intro rfl
-  exact Nat.add_lt_add_of_lt_of_le
-      (this.trans_lt
-        ((Nat.lt_mul_iff_one_lt_right ((by decide : 0 < 2).trans_le (hi.trans this))).mpr
-          (lt_iff_le_and_ne.mpr
-            ⟨(i + n).factorial_pos, fun g =>
-              Nat.not_succ_le_self 1 ((hi.trans this).trans (factorial_eq_one.mp g.symm))⟩)))
-      (factorial_le
-        ((le_of_eq (add_comm n 1)).trans
-        (Nat.add_le_add_iff_right.2 ((by decide : 1 ≤ 2).trans hi))))
+  rw [factorial_succ (i + _), Nat.add_mul, Nat.one_mul]
+  have := (i + n).self_le_factorial
+  refine Nat.add_lt_add_of_lt_of_le (Nat.lt_of_le_of_lt ?_ ((Nat.lt_mul_iff_one_lt_right ?_).2 ?_))
+    (factorial_le ?_) <;> omega
 #align nat.add_factorial_succ_lt_factorial_add_succ Nat.add_factorial_succ_lt_factorial_add_succ
 
 theorem add_factorial_lt_factorial_add {i n : ℕ} (hi : 2 ≤ i) (hn : 1 ≤ n) :
@@ -179,14 +166,14 @@ theorem add_factorial_lt_factorial_add {i n : ℕ} (hi : 2 ≤ i) (hn : 1 ≤ n)
 theorem add_factorial_succ_le_factorial_add_succ (i : ℕ) (n : ℕ) :
     i + (n + 1)! ≤ (i + (n + 1))! := by
   cases (le_or_lt (2 : ℕ) i)
-  · rw [← add_assoc]
+  · rw [← Nat.add_assoc]
     apply Nat.le_of_lt
     apply add_factorial_succ_lt_factorial_add_succ
     assumption
   · match i with
     | 0 => simp
     | 1 =>
-      rw [← add_assoc, factorial_succ (1 + n), add_mul, one_mul, add_comm 1 n,
+      rw [← Nat.add_assoc, factorial_succ (1 + n), Nat.add_mul, Nat.one_mul, Nat.add_comm 1 n,
         Nat.add_le_add_iff_right]
       exact Nat.mul_pos n.succ_pos n.succ.factorial_pos
     | succ (succ n) => contradiction
@@ -205,7 +192,7 @@ theorem factorial_mul_pow_sub_le_factorial {n m : ℕ} (hnm : n ≤ m) : n ! * n
 #align nat.factorial_mul_pow_sub_le_factorial Nat.factorial_mul_pow_sub_le_factorial
 
 lemma factorial_le_pow : ∀ n, n ! ≤ n ^ n
-  | 0 => le_rfl
+  | 0 => le_refl _
   | n + 1 =>
     calc
       _ ≤ (n + 1) * n ^ n := Nat.mul_le_mul_left _ n.factorial_le_pow
@@ -237,31 +224,30 @@ theorem ascFactorial_succ {n k : ℕ} : n.ascFactorial k.succ = (n + k) * n.ascF
 
 theorem zero_ascFactorial : ∀ (k : ℕ), (0 : ℕ).ascFactorial k.succ = 0
   | 0 => by
-    rw [ascFactorial_succ, ascFactorial_zero, zero_add, zero_mul]
+    rw [ascFactorial_succ, ascFactorial_zero, Nat.zero_add, Nat.zero_mul]
   | (k+1) => by
-    rw [ascFactorial_succ, zero_ascFactorial k, mul_zero]
+    rw [ascFactorial_succ, zero_ascFactorial k, Nat.mul_zero]
 
 @[simp]
 theorem one_ascFactorial : ∀ (k : ℕ), (1 : ℕ).ascFactorial k = k.factorial
   | 0 => ascFactorial_zero 1
   | (k+1) => by
-    rw [ascFactorial_succ, one_ascFactorial k, add_comm, factorial_succ]
+    rw [ascFactorial_succ, one_ascFactorial k, Nat.add_comm, factorial_succ]
 
 theorem succ_ascFactorial (n : ℕ) :
     ∀ k, n * n.succ.ascFactorial k = (n + k) * n.ascFactorial k
-  | 0 => by rw [add_zero, ascFactorial_zero, ascFactorial_zero]
-  | k + 1 => by
-    rw [ascFactorial, mul_left_comm, succ_ascFactorial n k, ascFactorial, succ_add, ← add_assoc]
+  | 0 => by rw [Nat.add_zero, ascFactorial_zero, ascFactorial_zero]
+  | k + 1 => by rw [ascFactorial, Nat.mul_left_comm, succ_ascFactorial n k, ascFactorial, succ_add,
+    ← Nat.add_assoc]
 #align nat.succ_asc_factorial Nat.succ_ascFactorial
 
 /-- `(n + 1).ascFactorial k = (n + k) ! / n !` but without ℕ-division. See
 `Nat.ascFactorial_eq_div` for the version with ℕ-division. -/
 theorem factorial_mul_ascFactorial (n : ℕ) : ∀ k, n ! * (n + 1).ascFactorial k = (n + k)!
-  | 0 => by
-    rw [add_zero, ascFactorial_zero, mul_one]
+  | 0 => by rw [ascFactorial_zero, Nat.add_zero, Nat.mul_one]
   | k + 1 => by
-    rw [ascFactorial_succ, ← add_assoc, factorial_succ, mul_comm (n + 1 + k), ← mul_assoc,
-      factorial_mul_ascFactorial n k, mul_comm, add_right_comm]
+    rw [ascFactorial_succ, ← Nat.add_assoc, factorial_succ, Nat.mul_comm (n + 1 + k),
+      ← Nat.mul_assoc, factorial_mul_ascFactorial n k, Nat.mul_comm, Nat.add_right_comm]
 #align nat.factorial_mul_asc_factorial Nat.factorial_mul_ascFactorial
 
 /-- `n.ascFactorial k = (n + k - 1)! / (n - 1)!` for `n > 0` but without ℕ-division. See
@@ -274,18 +260,13 @@ theorem factorial_mul_ascFactorial' (n k : ℕ) (h : 0 < n) :
   rw [Nat.sub_one, factorial_mul_ascFactorial]
 
 /-- Avoid in favor of `Nat.factorial_mul_ascFactorial` if you can. ℕ-division isn't worth it. -/
-theorem ascFactorial_eq_div (n k : ℕ) : (n + 1).ascFactorial k = (n + k)! / n ! := by
-  apply mul_left_cancel₀ n.factorial_ne_zero
-  rw [factorial_mul_ascFactorial]
-  exact (Nat.mul_div_cancel_left' <| factorial_dvd_factorial <| le_add_right n k).symm
+theorem ascFactorial_eq_div (n k : ℕ) : (n + 1).ascFactorial k = (n + k)! / n ! :=
+  Nat.eq_div_of_mul_eq_right n.factorial_ne_zero (factorial_mul_ascFactorial _ _)
 
-/-- Avoid in favor of `Nat.factorial_mul_ascFactorial` if you can. -/
+/-- Avoid in favor of `Nat.factorial_mul_ascFactorial'` if you can. ℕ-division isn't worth it. -/
 theorem ascFactorial_eq_div' (n k : ℕ) (h : 0 < n) :
-    n.ascFactorial k = (n + k - 1)! / (n - 1) ! := by
-  apply mul_left_cancel₀ (n-1).factorial_ne_zero
-  rw [factorial_mul_ascFactorial' _ _ h]
-  exact (Nat.mul_div_cancel_left' <| factorial_dvd_factorial <| Nat.sub_le_sub_right
-    (le_add_right n k) 1).symm
+    n.ascFactorial k = (n + k - 1)! / (n - 1) ! :=
+  Nat.eq_div_of_mul_eq_right (n - 1).factorial_ne_zero (factorial_mul_ascFactorial' _ _ h)
 #align nat.asc_factorial_eq_div Nat.ascFactorial_eq_div
 
 theorem ascFactorial_of_sub {n k : ℕ}:
@@ -294,15 +275,15 @@ theorem ascFactorial_of_sub {n k : ℕ}:
 #align nat.asc_factorial_of_sub Nat.ascFactorial_of_sub
 
 theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, n ^ k ≤ n.ascFactorial k
-  | 0 => by rw [ascFactorial_zero, pow_zero]
+  | 0 => by rw [ascFactorial_zero, Nat.pow_zero]
   | k + 1 => by
-    rw [Nat.pow_succ, mul_comm, ascFactorial_succ, ← succ_ascFactorial]
+    rw [Nat.pow_succ, Nat.mul_comm, ascFactorial_succ, ← succ_ascFactorial]
     exact Nat.mul_le_mul (Nat.le_refl n)
-      ((pow_le_pow_of_le_left (le_succ n) k).trans (pow_succ_le_ascFactorial n.succ k))
+      (Nat.le_trans (Nat.pow_le_pow_left (le_succ n) k) (pow_succ_le_ascFactorial n.succ k))
 #align nat.pow_succ_le_asc_factorial Nat.pow_succ_le_ascFactorial
 
 theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < (n + 1).ascFactorial (k + 2) := by
-  rw [Nat.pow_succ, ascFactorial, mul_comm]
+  rw [Nat.pow_succ, ascFactorial, Nat.mul_comm]
   exact Nat.mul_lt_mul_of_lt_of_le' (Nat.lt_add_of_pos_right k.succ_pos)
     (pow_succ_le_ascFactorial n.succ _) (Nat.pow_pos n.succ_pos)
 #align nat.pow_lt_asc_factorial' Nat.pow_lt_ascFactorial'
@@ -314,24 +295,24 @@ theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k <
 #align nat.pow_lt_asc_factorial Nat.pow_lt_ascFactorial
 
 theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, (n+1).ascFactorial k ≤ (n + k) ^ k
-  | 0 => by rw [ascFactorial_zero, pow_zero]
+  | 0 => by rw [ascFactorial_zero, Nat.pow_zero]
   | k + 1 => by
-    rw [ascFactorial_succ, Nat.pow_succ, mul_comm, ← add_assoc, add_right_comm n 1 k]
+    rw [ascFactorial_succ, Nat.pow_succ, Nat.mul_comm, ← Nat.add_assoc, Nat.add_right_comm n 1 k]
     exact Nat.mul_le_mul_right _
-      ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
+      (Nat.le_trans (ascFactorial_le_pow_add _ k) (Nat.pow_le_pow_left (le_succ _) _))
 #align nat.asc_factorial_le_pow_add Nat.ascFactorial_le_pow_add
 
 theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1).ascFactorial k < (n + k) ^ k
   | 0 => by rintro ⟨⟩
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
-    rw [Nat.pow_succ, mul_comm, ascFactorial_succ, succ_add_eq_add_succ n (k + 1)]
-    exact Nat.mul_lt_mul_of_le_of_lt le_rfl ((ascFactorial_le_pow_add n _).trans_lt
+    rw [Nat.pow_succ, Nat.mul_comm, ascFactorial_succ, succ_add_eq_add_succ n (k + 1)]
+    exact Nat.mul_lt_mul_of_le_of_lt (le_refl _) (Nat.lt_of_le_of_lt (ascFactorial_le_pow_add n _)
       (Nat.pow_lt_pow_left (Nat.lt_succ_self _) k.succ_ne_zero)) (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
 
 theorem ascFactorial_pos (n k : ℕ) : 0 < (n + 1).ascFactorial k :=
-  (Nat.pow_pos n.succ_pos).trans_le (pow_succ_le_ascFactorial (n + 1) k)
+  Nat.lt_of_lt_of_le (Nat.pow_pos n.succ_pos) (pow_succ_le_ascFactorial (n + 1) k)
 #align nat.asc_factorial_pos Nat.ascFactorial_pos
 
 end AscFactorial
@@ -357,7 +338,7 @@ theorem descFactorial_succ (n k : ℕ) : n.descFactorial (k + 1) = (n - k) * n.d
 #align nat.desc_factorial_succ Nat.descFactorial_succ
 
 theorem zero_descFactorial_succ (k : ℕ) : (0 : ℕ).descFactorial (k + 1) = 0 := by
-  rw [descFactorial_succ, Nat.zero_sub, zero_mul]
+  rw [descFactorial_succ, Nat.zero_sub, Nat.zero_mul]
 #align nat.zero_desc_factorial_succ Nat.zero_descFactorial_succ
 
 theorem descFactorial_one (n : ℕ) : n.descFactorial 1 = n := by simp
@@ -365,17 +346,17 @@ theorem descFactorial_one (n : ℕ) : n.descFactorial 1 = n := by simp
 
 theorem succ_descFactorial_succ (n : ℕ) :
     ∀ k : ℕ, (n + 1).descFactorial (k + 1) = (n + 1) * n.descFactorial k
-  | 0 => by rw [descFactorial_zero, descFactorial_one, mul_one]
+  | 0 => by rw [descFactorial_zero, descFactorial_one, Nat.mul_one]
   | succ k => by
     rw [descFactorial_succ, succ_descFactorial_succ _ k, descFactorial_succ, succ_sub_succ,
-      mul_left_comm]
+      Nat.mul_left_comm]
 #align nat.succ_desc_factorial_succ Nat.succ_descFactorial_succ
 
 theorem succ_descFactorial (n : ℕ) :
     ∀ k, (n + 1 - k) * (n + 1).descFactorial k = (n + 1) * n.descFactorial k
   | 0 => by rw [Nat.sub_zero, descFactorial_zero, descFactorial_zero]
   | k + 1 => by
-    rw [descFactorial, succ_descFactorial _ k, descFactorial_succ, succ_sub_succ, mul_left_comm]
+    rw [descFactorial, succ_descFactorial _ k, descFactorial_succ, succ_sub_succ, Nat.mul_left_comm]
 #align nat.succ_desc_factorial Nat.succ_descFactorial
 
 theorem descFactorial_self : ∀ n : ℕ, n.descFactorial n = n !
@@ -388,7 +369,7 @@ theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial
   | 0 => by simp only [descFactorial_zero, Nat.one_ne_zero, Nat.not_lt_zero]
   | succ k => by
     rw [descFactorial_succ, mul_eq_zero, descFactorial_eq_zero_iff_lt, Nat.lt_succ_iff,
-      Nat.sub_eq_zero_iff_le, lt_iff_le_and_ne, or_iff_left_iff_imp, and_imp]
+      Nat.sub_eq_zero_iff_le, Nat.lt_iff_le_and_ne, or_iff_left_iff_imp, and_imp]
     exact fun h _ => h
 #align nat.desc_factorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt
 
@@ -414,26 +395,26 @@ theorem add_descFactorial_eq_ascFactorial' (n : ℕ) :
 /-- `n.descFactorial k = n! / (n - k)!` but without ℕ-division. See `Nat.descFactorial_eq_div`
 for the version using ℕ-division. -/
 theorem factorial_mul_descFactorial : ∀ {n k : ℕ}, k ≤ n → (n - k)! * n.descFactorial k = n !
-  | n, 0 => fun _ => by rw [descFactorial_zero, mul_one, Nat.sub_zero]
+  | n, 0 => fun _ => by rw [descFactorial_zero, Nat.mul_one, Nat.sub_zero]
   | 0, succ k => fun h => by
     exfalso
     exact not_succ_le_zero k h
   | succ n, succ k => fun h => by
-    rw [succ_descFactorial_succ, succ_sub_succ, ← mul_assoc, mul_comm (n - k)!, mul_assoc,
-      factorial_mul_descFactorial (Nat.succ_le_succ_iff.1 h), factorial_succ]
+    rw [succ_descFactorial_succ, succ_sub_succ, ← Nat.mul_assoc, Nat.mul_comm (n - k)!,
+      Nat.mul_assoc, factorial_mul_descFactorial (Nat.succ_le_succ_iff.1 h), factorial_succ]
 #align nat.factorial_mul_desc_factorial Nat.factorial_mul_descFactorial
 
 /-- Avoid in favor of `Nat.factorial_mul_descFactorial` if you can. ℕ-division isn't worth it. -/
 theorem descFactorial_eq_div {n k : ℕ} (h : k ≤ n) : n.descFactorial k = n ! / (n - k)! := by
-  apply mul_left_cancel₀ (factorial_ne_zero (n - k))
+  apply Nat.mul_left_cancel (n - k).factorial_pos
   rw [factorial_mul_descFactorial h]
   exact (Nat.mul_div_cancel' <| factorial_dvd_factorial <| Nat.sub_le n k).symm
 #align nat.desc_factorial_eq_div Nat.descFactorial_eq_div
 
 theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.descFactorial k
-  | 0 => by rw [descFactorial_zero, pow_zero]
+  | 0 => by rw [descFactorial_zero, Nat.pow_zero]
   | k + 1 => by
-    rw [descFactorial_succ, Nat.pow_succ, succ_sub_succ, mul_comm]
+    rw [descFactorial_succ, Nat.pow_succ, succ_sub_succ, Nat.mul_comm]
     apply Nat.mul_le_mul_left
     exact (le_trans (Nat.pow_le_pow_left (Nat.sub_le_sub_right n.le_succ _) k)
       (pow_sub_le_descFactorial n k))
@@ -441,16 +422,15 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
 
 theorem pow_sub_lt_descFactorial' {n : ℕ} :
     ∀ {k : ℕ}, k + 2 ≤ n → (n - (k + 1)) ^ (k + 2) < n.descFactorial (k + 2)
-  | 0 => fun h => by
-    rw [descFactorial_succ, pow_succ, pow_one, descFactorial_one]
-    exact Nat.mul_lt_mul_of_pos_left (Nat.sub_lt_self Nat.zero_lt_one (Nat.zero_lt_two.trans_le h))
-      (Nat.sub_pos_of_lt h)
-  | k + 1 => fun h => by
-    rw [descFactorial_succ, Nat.pow_succ, mul_comm]
+  | 0, h => by
+    rw [descFactorial_succ, Nat.pow_succ, Nat.pow_one, descFactorial_one]
+    exact Nat.mul_lt_mul_of_pos_left (by omega) (Nat.sub_pos_of_lt h)
+  | k + 1, h => by
+    rw [descFactorial_succ, Nat.pow_succ, Nat.mul_comm]
     refine Nat.mul_lt_mul_of_pos_left ?_ (Nat.sub_pos_of_lt h)
-    refine (Nat.pow_le_pow_left (Nat.sub_le_sub_right n.le_succ _) _).trans_lt ?_
+    refine Nat.lt_of_le_of_lt (Nat.pow_le_pow_left (Nat.sub_le_sub_right n.le_succ _) _) ?_
     rw [succ_sub_succ]
-    exact pow_sub_lt_descFactorial' ((le_succ _).trans h)
+    exact pow_sub_lt_descFactorial' (Nat.le_trans (le_succ _) h)
 #align nat.pow_sub_lt_desc_factorial' Nat.pow_sub_lt_descFactorial'
 
 theorem pow_sub_lt_descFactorial {n : ℕ} :
@@ -463,9 +443,9 @@ theorem pow_sub_lt_descFactorial {n : ℕ} :
 #align nat.pow_sub_lt_desc_factorial Nat.pow_sub_lt_descFactorial
 
 theorem descFactorial_le_pow (n : ℕ) : ∀ k : ℕ, n.descFactorial k ≤ n ^ k
-  | 0 => by rw [descFactorial_zero, pow_zero]
+  | 0 => by rw [descFactorial_zero, Nat.pow_zero]
   | k + 1 => by
-    rw [descFactorial_succ, Nat.pow_succ, mul_comm _ n]
+    rw [descFactorial_succ, Nat.pow_succ, Nat.mul_comm _ n]
     exact Nat.mul_le_mul (Nat.sub_le _ _) (descFactorial_le_pow _ k)
 #align nat.desc_factorial_le_pow Nat.descFactorial_le_pow
 
@@ -473,7 +453,7 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
   | 0 => by rintro ⟨⟩
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
-    rw [descFactorial_succ, pow_succ', mul_comm, mul_comm n]
+    rw [descFactorial_succ, pow_succ', Nat.mul_comm, Nat.mul_comm n]
     exact Nat.mul_lt_mul_of_le_of_lt (descFactorial_le_pow _ _) (Nat.sub_lt hn k.zero_lt_succ)
       (Nat.pow_pos (Nat.lt_of_succ_le hn))
 #align nat.desc_factorial_lt_pow Nat.descFactorial_lt_pow
@@ -481,13 +461,13 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
 end DescFactorial
 
 lemma factorial_two_mul_le (n : ℕ) : (2 * n)! ≤ (2 * n) ^ n * n ! := by
-  rw [two_mul, ← factorial_mul_ascFactorial, mul_comm]
+  rw [Nat.two_mul, ← factorial_mul_ascFactorial, Nat.mul_comm]
   exact Nat.mul_le_mul_right _ (ascFactorial_le_pow_add _ _)
 
 lemma two_pow_mul_factorial_le_factorial_two_mul (n : ℕ) : 2 ^ n * n ! ≤ (2 * n) ! := by
   obtain _ | n := n
   · simp
-  rw [mul_comm, two_mul]
+  rw [Nat.mul_comm, Nat.two_mul]
   calc
     _ ≤ (n + 1)! * (n + 2) ^ (n + 1) :=
       Nat.mul_le_mul_left _ (pow_le_pow_of_le_left (le_add_left _ _) _)

d012cd09

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

@@ -3,9 +3,12 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
+import Mathlib.Algebra.Divisibility.Basic
+import Mathlib.Data.Nat.Basic
+import Mathlib.Order.Monotone.Basic
 import Mathlib.Tactic.GCongr.Core
 import Mathlib.Tactic.Common
-import Mathlib.Algebra.GroupPower.Order
+import Mathlib.Tactic.Monotonicity.Attr
 
 #align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"d012cd09a9b256d870751284dd6a29882b0be105"
 
@@ -57,12 +60,12 @@ theorem factorial_succ (n : ℕ) : (n + 1)! = (n + 1) * n ! :=
 #align nat.factorial_two Nat.factorial_two
 
 theorem mul_factorial_pred (hn : 0 < n) : n * (n - 1)! = n ! :=
-  tsub_add_cancel_of_le (Nat.succ_le_of_lt hn) ▸ rfl
+  Nat.sub_add_cancel (Nat.succ_le_of_lt hn) ▸ rfl
 #align nat.mul_factorial_pred Nat.mul_factorial_pred
 
 theorem factorial_pos : ∀ n, 0 < n !
-  | 0 => zero_lt_one
-  | succ n => mul_pos (succ_pos _) (factorial_pos n)
+  | 0 => Nat.zero_lt_one
+  | succ n => Nat.mul_pos (succ_pos _) (factorial_pos n)
 #align nat.factorial_pos Nat.factorial_pos
 
 theorem factorial_ne_zero (n : ℕ) : n ! ≠ 0 :=
@@ -100,8 +103,8 @@ theorem factorial_lt (hn : 0 < n) : n ! < m ! ↔ n < m := by
   refine' ⟨fun h => not_le.mp fun hmn => not_le_of_lt h (factorial_le hmn), fun h => _⟩
   have : ∀ {n}, 0 < n → n ! < (n + 1)! := by
     intro k hk
-    rw [factorial_succ, succ_mul, lt_add_iff_pos_left]
-    exact mul_pos hk k.factorial_pos
+    rw [factorial_succ, succ_mul, Nat.lt_add_left_iff_pos]
+    exact Nat.mul_pos hk k.factorial_pos
   induction' h with k hnk ih generalizing hn
   · exact this hn
   · exact (ih hn).trans (this <| hn.trans <| lt_of_succ_le hnk)
@@ -110,9 +113,7 @@ theorem factorial_lt (hn : 0 < n) : n ! < m ! ↔ n < m := by
 @[gcongr]
 lemma factorial_lt_of_lt {m n : ℕ} (hn : 0 < n) (h : n < m) : n ! < m ! := (factorial_lt hn).mpr h
 
-@[simp]
-theorem one_lt_factorial : 1 < n ! ↔ 1 < n :=
-  factorial_lt one_pos
+@[simp] lemma one_lt_factorial : 1 < n ! ↔ 1 < n := factorial_lt Nat.one_pos
 #align nat.one_lt_factorial Nat.one_lt_factorial
 
 @[simp]
@@ -127,11 +128,11 @@ theorem factorial_eq_one : n ! = 1 ↔ n ≤ 1 := by
 theorem factorial_inj (hn : 1 < n) : n ! = m ! ↔ n = m := by
   refine' ⟨fun h => _, congr_arg _⟩
   obtain hnm | rfl | hnm := lt_trichotomy n m
-  · rw [← factorial_lt <| pos_of_gt hn, h] at hnm
+  · rw [← factorial_lt <| lt_of_succ_lt hn, h] at hnm
     cases lt_irrefl _ hnm
   · rfl
   rw [← one_lt_factorial, h, one_lt_factorial] at hn
-  rw [← factorial_lt <| pos_of_gt hn, h] at hnm
+  rw [← factorial_lt <| lt_of_succ_lt hn, h] at hnm
   cases lt_irrefl _ hnm
 #align nat.factorial_inj Nat.factorial_inj
 
@@ -141,33 +142,30 @@ theorem factorial_inj' (h : 1 < n ∨ 1 < m) : n ! = m ! ↔ n = m := by
   · rw [eq_comm, factorial_inj hm, eq_comm]
 
 theorem self_le_factorial : ∀ n : ℕ, n ≤ n !
-  | 0 => zero_le_one
-  | k + 1 => le_mul_of_one_le_right k.zero_lt_succ.le (Nat.one_le_of_lt <| Nat.factorial_pos _)
+  | 0 => Nat.zero_le _
+  | k + 1 => Nat.le_mul_of_pos_right _ (Nat.one_le_of_lt k.factorial_pos)
 #align nat.self_le_factorial Nat.self_le_factorial
 
 theorem lt_factorial_self {n : ℕ} (hi : 3 ≤ n) : n < n ! := by
-  have : 0 < n := (zero_lt_two (α := ℕ)).trans (succ_le_iff.mp hi)
-  have : 1 < pred n := le_pred_of_lt (succ_le_iff.mp hi)
+  have : 0 < n := Nat.zero_lt_two.trans (succ_le_iff.mp hi)
+  have hn : 1 < pred n := le_pred_of_lt (succ_le_iff.mp hi)
   rw [← succ_pred_eq_of_pos ‹0 < n›, factorial_succ]
-  exact
-    lt_mul_of_one_lt_right (pred n).succ_pos
-      ((‹1 < pred n›).trans_le (self_le_factorial _))
+  exact (Nat.lt_mul_iff_one_lt_right (pred n).succ_pos).2 (hn.trans_le (self_le_factorial _))
 #align nat.lt_factorial_self Nat.lt_factorial_self
 
 theorem add_factorial_succ_lt_factorial_add_succ {i : ℕ} (n : ℕ) (hi : 2 ≤ i) :
     i + (n + 1)! < (i + n + 1)! := by
   rw [factorial_succ (i + _), add_mul, one_mul]
   have : i ≤ i + n := le.intro rfl
-  exact
-    add_lt_add_of_lt_of_le
+  exact Nat.add_lt_add_of_lt_of_le
       (this.trans_lt
-        ((lt_mul_iff_one_lt_right ((by decide : 0 < 2).trans_le (hi.trans this))).mpr
+        ((Nat.lt_mul_iff_one_lt_right ((by decide : 0 < 2).trans_le (hi.trans this))).mpr
           (lt_iff_le_and_ne.mpr
             ⟨(i + n).factorial_pos, fun g =>
               Nat.not_succ_le_self 1 ((hi.trans this).trans (factorial_eq_one.mp g.symm))⟩)))
       (factorial_le
         ((le_of_eq (add_comm n 1)).trans
-        ((add_le_add_iff_right n).mpr ((by decide : 1 ≤ 2).trans hi))))
+        (Nat.add_le_add_iff_right.2 ((by decide : 1 ≤ 2).trans hi))))
 #align nat.add_factorial_succ_lt_factorial_add_succ Nat.add_factorial_succ_lt_factorial_add_succ
 
 theorem add_factorial_lt_factorial_add {i n : ℕ} (hi : 2 ≤ i) (hn : 1 ≤ n) :
@@ -188,10 +186,9 @@ theorem add_factorial_succ_le_factorial_add_succ (i : ℕ) (n : ℕ) :
   · match i with
     | 0 => simp
     | 1 =>
-      rw [← add_assoc, factorial_succ (1 + n), add_mul, one_mul, add_comm 1 n, add_le_add_iff_right]
-      apply one_le_mul
-      · apply Nat.le_add_left
-      · apply factorial_pos
+      rw [← add_assoc, factorial_succ (1 + n), add_mul, one_mul, add_comm 1 n,
+        Nat.add_le_add_iff_right]
+      exact Nat.mul_pos n.succ_pos n.succ.factorial_pos
     | succ (succ n) => contradiction
 #align nat.add_factorial_succ_le_factorial_add_succ Nat.add_factorial_succ_le_factorial_add_succ
 
@@ -203,7 +200,7 @@ theorem add_factorial_le_factorial_add (i : ℕ) {n : ℕ} (n1 : 1 ≤ n) : i +
 
 theorem factorial_mul_pow_sub_le_factorial {n m : ℕ} (hnm : n ≤ m) : n ! * n ^ (m - n) ≤ m ! := by
   calc
-    _ ≤ n ! * (n + 1) ^ (m - n) := mul_le_mul_left' (Nat.pow_le_pow_left n.le_succ _) _
+    _ ≤ n ! * (n + 1) ^ (m - n) := Nat.mul_le_mul_left _ (Nat.pow_le_pow_left n.le_succ _)
     _ ≤ _ := by simpa [hnm] using @Nat.factorial_mul_pow_le_factorial n (m - n)
 #align nat.factorial_mul_pow_sub_le_factorial Nat.factorial_mul_pow_sub_le_factorial
 
@@ -211,8 +208,8 @@ lemma factorial_le_pow : ∀ n, n ! ≤ n ^ n
   | 0 => le_rfl
   | n + 1 =>
     calc
-      _ ≤ (n + 1) * n ^ n := mul_le_mul_left' n.factorial_le_pow _
-      _ ≤ (n + 1) * (n + 1) ^ n := mul_le_mul_left' (Nat.pow_le_pow_left n.le_succ _) _
+      _ ≤ (n + 1) * n ^ n := Nat.mul_le_mul_left _ n.factorial_le_pow
+      _ ≤ (n + 1) * (n + 1) ^ n := Nat.mul_le_mul_left _ (Nat.pow_le_pow_left n.le_succ _)
       _ = _ := by rw [pow_succ']
 
 end Factorial
@@ -306,8 +303,8 @@ theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, n ^ k ≤ n.ascFactori
 
 theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < (n + 1).ascFactorial (k + 2) := by
   rw [Nat.pow_succ, ascFactorial, mul_comm]
-  exact Nat.mul_lt_mul_of_lt_of_le' (lt_add_of_pos_right (n + 1) (succ_pos k))
-    (pow_succ_le_ascFactorial n.succ _) (NeZero.pos ((n + 1) ^ (k + 1)))
+  exact Nat.mul_lt_mul_of_lt_of_le' (Nat.lt_add_of_pos_right k.succ_pos)
+    (pow_succ_le_ascFactorial n.succ _) (Nat.pow_pos n.succ_pos)
 #align nat.pow_lt_asc_factorial' Nat.pow_lt_ascFactorial'
 
 theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k < (n + 1).ascFactorial k
@@ -330,11 +327,11 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1).a
   | k + 2 => fun _ => by
     rw [Nat.pow_succ, mul_comm, ascFactorial_succ, succ_add_eq_add_succ n (k + 1)]
     exact Nat.mul_lt_mul_of_le_of_lt le_rfl ((ascFactorial_le_pow_add n _).trans_lt
-      (pow_lt_pow_left (@lt_add_one ℕ _ _ _ _ _ _ _) (zero_le _) k.succ_ne_zero)) (succ_pos _)
+      (Nat.pow_lt_pow_left (Nat.lt_succ_self _) k.succ_ne_zero)) (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
 
 theorem ascFactorial_pos (n k : ℕ) : 0 < (n + 1).ascFactorial k :=
-  (pow_pos (succ_pos n) k).trans_le (pow_succ_le_ascFactorial (n + 1) k)
+  (Nat.pow_pos n.succ_pos).trans_le (pow_succ_le_ascFactorial (n + 1) k)
 #align nat.asc_factorial_pos Nat.ascFactorial_pos
 
 end AscFactorial
@@ -360,7 +357,7 @@ theorem descFactorial_succ (n k : ℕ) : n.descFactorial (k + 1) = (n - k) * n.d
 #align nat.desc_factorial_succ Nat.descFactorial_succ
 
 theorem zero_descFactorial_succ (k : ℕ) : (0 : ℕ).descFactorial (k + 1) = 0 := by
-  rw [descFactorial_succ, zero_tsub, zero_mul]
+  rw [descFactorial_succ, Nat.zero_sub, zero_mul]
 #align nat.zero_desc_factorial_succ Nat.zero_descFactorial_succ
 
 theorem descFactorial_one (n : ℕ) : n.descFactorial 1 = n := by simp
@@ -376,7 +373,7 @@ theorem succ_descFactorial_succ (n : ℕ) :
 
 theorem succ_descFactorial (n : ℕ) :
     ∀ k, (n + 1 - k) * (n + 1).descFactorial k = (n + 1) * n.descFactorial k
-  | 0 => by rw [tsub_zero, descFactorial_zero, descFactorial_zero]
+  | 0 => by rw [Nat.sub_zero, descFactorial_zero, descFactorial_zero]
   | k + 1 => by
     rw [descFactorial, succ_descFactorial _ k, descFactorial_succ, succ_sub_succ, mul_left_comm]
 #align nat.succ_desc_factorial Nat.succ_descFactorial
@@ -391,7 +388,7 @@ theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial
   | 0 => by simp only [descFactorial_zero, Nat.one_ne_zero, Nat.not_lt_zero]
   | succ k => by
     rw [descFactorial_succ, mul_eq_zero, descFactorial_eq_zero_iff_lt, Nat.lt_succ_iff,
-      tsub_eq_zero_iff_le, lt_iff_le_and_ne, or_iff_left_iff_imp, and_imp]
+      Nat.sub_eq_zero_iff_le, lt_iff_le_and_ne, or_iff_left_iff_imp, and_imp]
     exact fun h _ => h
 #align nat.desc_factorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt
 
@@ -417,7 +414,7 @@ theorem add_descFactorial_eq_ascFactorial' (n : ℕ) :
 /-- `n.descFactorial k = n! / (n - k)!` but without ℕ-division. See `Nat.descFactorial_eq_div`
 for the version using ℕ-division. -/
 theorem factorial_mul_descFactorial : ∀ {n k : ℕ}, k ≤ n → (n - k)! * n.descFactorial k = n !
-  | n, 0 => fun _ => by rw [descFactorial_zero, mul_one, tsub_zero]
+  | n, 0 => fun _ => by rw [descFactorial_zero, mul_one, Nat.sub_zero]
   | 0, succ k => fun h => by
     exfalso
     exact not_succ_le_zero k h
@@ -438,7 +435,7 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
   | k + 1 => by
     rw [descFactorial_succ, Nat.pow_succ, succ_sub_succ, mul_comm]
     apply Nat.mul_le_mul_left
-    exact (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
+    exact (le_trans (Nat.pow_le_pow_left (Nat.sub_le_sub_right n.le_succ _) k)
       (pow_sub_le_descFactorial n k))
 #align nat.pow_sub_le_desc_factorial Nat.pow_sub_le_descFactorial
 
@@ -446,16 +443,14 @@ theorem pow_sub_lt_descFactorial' {n : ℕ} :
     ∀ {k : ℕ}, k + 2 ≤ n → (n - (k + 1)) ^ (k + 2) < n.descFactorial (k + 2)
   | 0 => fun h => by
     rw [descFactorial_succ, pow_succ, pow_one, descFactorial_one]
-    exact
-      Nat.mul_lt_mul_of_pos_left (tsub_lt_self (lt_of_lt_of_le zero_lt_two h) zero_lt_one)
-        (tsub_pos_of_lt h)
+    exact Nat.mul_lt_mul_of_pos_left (Nat.sub_lt_self Nat.zero_lt_one (Nat.zero_lt_two.trans_le h))
+      (Nat.sub_pos_of_lt h)
   | k + 1 => fun h => by
     rw [descFactorial_succ, Nat.pow_succ, mul_comm]
-    apply Nat.mul_lt_mul_of_pos_left
-    · refine' ((Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _)
-      rw [succ_sub_succ]
-      exact pow_sub_lt_descFactorial' ((le_succ _).trans h)
-    · apply tsub_pos_of_lt; apply h
+    refine Nat.mul_lt_mul_of_pos_left ?_ (Nat.sub_pos_of_lt h)
+    refine (Nat.pow_le_pow_left (Nat.sub_le_sub_right n.le_succ _) _).trans_lt ?_
+    rw [succ_sub_succ]
+    exact pow_sub_lt_descFactorial' ((le_succ _).trans h)
 #align nat.pow_sub_lt_desc_factorial' Nat.pow_sub_lt_descFactorial'
 
 theorem pow_sub_lt_descFactorial {n : ℕ} :
@@ -479,22 +474,23 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
     rw [descFactorial_succ, pow_succ', mul_comm, mul_comm n]
-    exact Nat.mul_lt_mul_of_le_of_lt (descFactorial_le_pow _ _) (tsub_lt_self hn k.zero_lt_succ)
-      (pow_pos (Nat.lt_of_succ_le hn) _)
+    exact Nat.mul_lt_mul_of_le_of_lt (descFactorial_le_pow _ _) (Nat.sub_lt hn k.zero_lt_succ)
+      (Nat.pow_pos (Nat.lt_of_succ_le hn))
 #align nat.desc_factorial_lt_pow Nat.descFactorial_lt_pow
 
 end DescFactorial
 
 lemma factorial_two_mul_le (n : ℕ) : (2 * n)! ≤ (2 * n) ^ n * n ! := by
   rw [two_mul, ← factorial_mul_ascFactorial, mul_comm]
-  exact mul_le_mul_right' (ascFactorial_le_pow_add _ _) _
+  exact Nat.mul_le_mul_right _ (ascFactorial_le_pow_add _ _)
 
 lemma two_pow_mul_factorial_le_factorial_two_mul (n : ℕ) : 2 ^ n * n ! ≤ (2 * n) ! := by
   obtain _ | n := n
   · simp
   rw [mul_comm, two_mul]
   calc
-    _ ≤ (n + 1)! * (n + 2) ^ (n + 1) := mul_le_mul_left' (pow_le_pow_of_le_left le_add_self _) _
+    _ ≤ (n + 1)! * (n + 2) ^ (n + 1) :=
+      Nat.mul_le_mul_left _ (pow_le_pow_of_le_left (le_add_left _ _) _)
     _ ≤ _ := Nat.factorial_mul_pow_le_factorial
 
 end Nat

d012cd09

chore: move Mathlib to v4.7.0-rc1 (#11162)

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

fa48894a

Diff

@@ -89,7 +89,7 @@ theorem factorial_le {m n} (h : m ≤ n) : m ! ≤ n ! :=
 theorem factorial_mul_pow_le_factorial : ∀ {m n : ℕ}, m ! * (m + 1) ^ n ≤ (m + n)!
   | m, 0 => by simp
   | m, n + 1 => by
-    rw [← add_assoc, factorial_succ, mul_comm (_ + 1), pow_succ, ← mul_assoc]
+    rw [← add_assoc, factorial_succ, mul_comm (_ + 1), Nat.pow_succ, ← mul_assoc]
     exact Nat.mul_le_mul factorial_mul_pow_le_factorial (succ_le_succ (le_add_right _ _))
 #align nat.factorial_mul_pow_le_factorial Nat.factorial_mul_pow_le_factorial
 
@@ -299,13 +299,13 @@ theorem ascFactorial_of_sub {n k : ℕ}:
 theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, n ^ k ≤ n.ascFactorial k
   | 0 => by rw [ascFactorial_zero, pow_zero]
   | k + 1 => by
-    rw [pow_succ, mul_comm, ascFactorial_succ, ← succ_ascFactorial]
+    rw [Nat.pow_succ, mul_comm, ascFactorial_succ, ← succ_ascFactorial]
     exact Nat.mul_le_mul (Nat.le_refl n)
       ((pow_le_pow_of_le_left (le_succ n) k).trans (pow_succ_le_ascFactorial n.succ k))
 #align nat.pow_succ_le_asc_factorial Nat.pow_succ_le_ascFactorial
 
 theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < (n + 1).ascFactorial (k + 2) := by
-  rw [pow_succ, ascFactorial, mul_comm]
+  rw [Nat.pow_succ, ascFactorial, mul_comm]
   exact Nat.mul_lt_mul_of_lt_of_le' (lt_add_of_pos_right (n + 1) (succ_pos k))
     (pow_succ_le_ascFactorial n.succ _) (NeZero.pos ((n + 1) ^ (k + 1)))
 #align nat.pow_lt_asc_factorial' Nat.pow_lt_ascFactorial'
@@ -319,7 +319,7 @@ theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k <
 theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, (n+1).ascFactorial k ≤ (n + k) ^ k
   | 0 => by rw [ascFactorial_zero, pow_zero]
   | k + 1 => by
-    rw [ascFactorial_succ, pow_succ, mul_comm, ← add_assoc, add_right_comm n 1 k]
+    rw [ascFactorial_succ, Nat.pow_succ, mul_comm, ← add_assoc, add_right_comm n 1 k]
     exact Nat.mul_le_mul_right _
       ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
 #align nat.asc_factorial_le_pow_add Nat.ascFactorial_le_pow_add
@@ -328,7 +328,7 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1).a
   | 0 => by rintro ⟨⟩
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
-    rw [pow_succ, mul_comm, ascFactorial_succ, succ_add_eq_add_succ n (k + 1)]
+    rw [Nat.pow_succ, mul_comm, ascFactorial_succ, succ_add_eq_add_succ n (k + 1)]
     exact Nat.mul_lt_mul_of_le_of_lt le_rfl ((ascFactorial_le_pow_add n _).trans_lt
       (pow_lt_pow_left (@lt_add_one ℕ _ _ _ _ _ _ _) (zero_le _) k.succ_ne_zero)) (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
@@ -436,7 +436,7 @@ theorem descFactorial_eq_div {n k : ℕ} (h : k ≤ n) : n.descFactorial k = n !
 theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.descFactorial k
   | 0 => by rw [descFactorial_zero, pow_zero]
   | k + 1 => by
-    rw [descFactorial_succ, pow_succ, succ_sub_succ, mul_comm]
+    rw [descFactorial_succ, Nat.pow_succ, succ_sub_succ, mul_comm]
     apply Nat.mul_le_mul_left
     exact (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
       (pow_sub_le_descFactorial n k))
@@ -450,7 +450,7 @@ theorem pow_sub_lt_descFactorial' {n : ℕ} :
       Nat.mul_lt_mul_of_pos_left (tsub_lt_self (lt_of_lt_of_le zero_lt_two h) zero_lt_one)
         (tsub_pos_of_lt h)
   | k + 1 => fun h => by
-    rw [descFactorial_succ, pow_succ, mul_comm]
+    rw [descFactorial_succ, Nat.pow_succ, mul_comm]
     apply Nat.mul_lt_mul_of_pos_left
     · refine' ((Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _)
       rw [succ_sub_succ]
@@ -470,7 +470,7 @@ theorem pow_sub_lt_descFactorial {n : ℕ} :
 theorem descFactorial_le_pow (n : ℕ) : ∀ k : ℕ, n.descFactorial k ≤ n ^ k
   | 0 => by rw [descFactorial_zero, pow_zero]
   | k + 1 => by
-    rw [descFactorial_succ, pow_succ, mul_comm _ n]
+    rw [descFactorial_succ, Nat.pow_succ, mul_comm _ n]
     exact Nat.mul_le_mul (Nat.sub_le _ _) (descFactorial_le_pow _ k)
 #align nat.desc_factorial_le_pow Nat.descFactorial_le_pow

d012cd09

chore: bump Std (#10482)

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

9afd0027

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
-import Mathlib.Data.Nat.Pow
 import Mathlib.Tactic.GCongr.Core
 import Mathlib.Tactic.Common
+import Mathlib.Algebra.GroupPower.Order
 
 #align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"d012cd09a9b256d870751284dd6a29882b0be105"

d012cd09

chore: bump dependencies (#10315)

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

ba9f2e5b

Diff

@@ -390,7 +390,7 @@ theorem descFactorial_self : ∀ n : ℕ, n.descFactorial n = n !
 theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial k = 0 ↔ n < k
   | 0 => by simp only [descFactorial_zero, Nat.one_ne_zero, Nat.not_lt_zero]
   | succ k => by
-    rw [descFactorial_succ, mul_eq_zero, descFactorial_eq_zero_iff_lt, lt_succ_iff,
+    rw [descFactorial_succ, mul_eq_zero, descFactorial_eq_zero_iff_lt, Nat.lt_succ_iff,
       tsub_eq_zero_iff_le, lt_iff_le_and_ne, or_iff_left_iff_imp, and_imp]
     exact fun h _ => h
 #align nat.desc_factorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt

d012cd09

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

@@ -438,8 +438,8 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
   | k + 1 => by
     rw [descFactorial_succ, pow_succ, succ_sub_succ, mul_comm]
     apply Nat.mul_le_mul_left
-    exact   (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
-          (pow_sub_le_descFactorial n k))
+    exact (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
+      (pow_sub_le_descFactorial n k))
 #align nat.pow_sub_le_desc_factorial Nat.pow_sub_le_descFactorial
 
 theorem pow_sub_lt_descFactorial' {n : ℕ} :

d012cd09

chore: tidy various files (#9728)

a94a9fd8

Diff

@@ -277,7 +277,7 @@ theorem factorial_mul_ascFactorial' (n k : ℕ) (h : 0 < n) :
   rw [Nat.sub_one, factorial_mul_ascFactorial]
 
 /-- Avoid in favor of `Nat.factorial_mul_ascFactorial` if you can. ℕ-division isn't worth it. -/
-theorem ascFactorial_eq_div (n k : ℕ) :  (n + 1).ascFactorial k = (n + k)! / n ! := by
+theorem ascFactorial_eq_div (n k : ℕ) : (n + 1).ascFactorial k = (n + k)! / n ! := by
   apply mul_left_cancel₀ n.factorial_ne_zero
   rw [factorial_mul_ascFactorial]
   exact (Nat.mul_div_cancel_left' <| factorial_dvd_factorial <| le_add_right n k).symm

d012cd09

fix: patch for std4#198 (more mul lemmas for Nat) (#6204)

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

2f63d25e

Diff

@@ -306,7 +306,7 @@ theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, n ^ k ≤ n.ascFactori
 
 theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < (n + 1).ascFactorial (k + 2) := by
   rw [pow_succ, ascFactorial, mul_comm]
-  exact Nat.mul_lt_mul (lt_add_of_pos_right (n + 1) (succ_pos k))
+  exact Nat.mul_lt_mul_of_lt_of_le' (lt_add_of_pos_right (n + 1) (succ_pos k))
     (pow_succ_le_ascFactorial n.succ _) (NeZero.pos ((n + 1) ^ (k + 1)))
 #align nat.pow_lt_asc_factorial' Nat.pow_lt_ascFactorial'
 
@@ -320,7 +320,7 @@ theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, (n+1).ascFactorial k 
   | 0 => by rw [ascFactorial_zero, pow_zero]
   | k + 1 => by
     rw [ascFactorial_succ, pow_succ, mul_comm, ← add_assoc, add_right_comm n 1 k]
-    exact Nat.mul_le_mul_of_nonneg_right
+    exact Nat.mul_le_mul_right _
       ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
 #align nat.asc_factorial_le_pow_add Nat.ascFactorial_le_pow_add
 
@@ -329,7 +329,7 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1).a
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
     rw [pow_succ, mul_comm, ascFactorial_succ, succ_add_eq_add_succ n (k + 1)]
-    exact Nat.mul_lt_mul' le_rfl ((ascFactorial_le_pow_add n _).trans_lt
+    exact Nat.mul_lt_mul_of_le_of_lt le_rfl ((ascFactorial_le_pow_add n _).trans_lt
       (pow_lt_pow_left (@lt_add_one ℕ _ _ _ _ _ _ _) (zero_le _) k.succ_ne_zero)) (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
 
@@ -437,7 +437,7 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
   | 0 => by rw [descFactorial_zero, pow_zero]
   | k + 1 => by
     rw [descFactorial_succ, pow_succ, succ_sub_succ, mul_comm]
-    apply Nat.mul_le_mul_of_nonneg_left
+    apply Nat.mul_le_mul_left
     exact   (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
           (pow_sub_le_descFactorial n k))
 #align nat.pow_sub_le_desc_factorial Nat.pow_sub_le_descFactorial
@@ -479,7 +479,7 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
     rw [descFactorial_succ, pow_succ', mul_comm, mul_comm n]
-    exact Nat.mul_lt_mul' (descFactorial_le_pow _ _) (tsub_lt_self hn k.zero_lt_succ)
+    exact Nat.mul_lt_mul_of_le_of_lt (descFactorial_le_pow _ _) (tsub_lt_self hn k.zero_lt_succ)
       (pow_pos (Nat.lt_of_succ_le hn) _)
 #align nat.desc_factorial_lt_pow Nat.descFactorial_lt_pow

d012cd09

refactor: Split off basic Nat file (#9551)

Data.Nat.Basic is currently made of two things:

Basic lemmas that continue the theory in Std (and could belong there, really)
Basic algebraic order instances

I need the first ones earlier in the algebraic order hierarchy, hence the split.

Part of #9411. Similar to #9443

497ed074

Diff

@@ -3,7 +3,6 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
-import Mathlib.Data.Nat.Basic
 import Mathlib.Data.Nat.Pow
 import Mathlib.Tactic.GCongr.Core
 import Mathlib.Tactic.Common

d012cd09

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

@@ -18,9 +18,10 @@ This file defines the factorial, along with the ascending and descending variant
 ## Main declarations
 
 * `Nat.factorial`: The factorial.
-* `Nat.ascFactorial`: The ascending factorial. Note that it runs from `n + 1` to `n + k`
-  and *not* from `n` to `n + k - 1`. We might want to change that in the future.
-* `Nat.descFactorial`: The descending factorial. It runs from `n - k` to `n`.
+* `Nat.ascFactorial`: The ascending factorial. It is the product of natural numbers from `n` to
+  `n + k - 1`.
+* `Nat.descFactorial`: The descending factorial. It is the product of natural numbers from
+  `n - k + 1` to `n`.
 -/
 
 
@@ -222,12 +223,11 @@ end Factorial
 
 section AscFactorial
 
-/-- `n.ascFactorial k = (n + k)! / n!` (as seen in `Nat.ascFactorial_eq_div`), but implemented
-recursively to allow for "quick" computation when using `norm_num`. This is closely related to
-`ascPochhammer`, but much less general. -/
+/-- `n.ascFactorial k = n (n + 1) ⋯ (n + k - 1)`. This is closely related to `ascPochhammer`, but
+much less general. -/
 def ascFactorial (n : ℕ) : ℕ → ℕ
   | 0 => 1
-  | k + 1 => (n + k + 1) * ascFactorial n k
+  | k + 1 => (n + k) * ascFactorial n k
 #align nat.asc_factorial Nat.ascFactorial
 
 @[simp]
@@ -235,87 +235,107 @@ theorem ascFactorial_zero (n : ℕ) : n.ascFactorial 0 = 1 :=
   rfl
 #align nat.asc_factorial_zero Nat.ascFactorial_zero
 
-@[simp]
-theorem zero_ascFactorial (k : ℕ) : (0 : ℕ).ascFactorial k = k ! := by
-  induction' k with t ht
-  · rfl
-  rw [ascFactorial, ht, zero_add, Nat.factorial_succ]
-#align nat.zero_asc_factorial Nat.zero_ascFactorial
-
-theorem ascFactorial_succ {n k : ℕ} : n.ascFactorial (k + 1) = (n + k + 1) * n.ascFactorial k :=
+theorem ascFactorial_succ {n k : ℕ} : n.ascFactorial k.succ = (n + k) * n.ascFactorial k :=
   rfl
 #align nat.asc_factorial_succ Nat.ascFactorial_succ
 
+theorem zero_ascFactorial : ∀ (k : ℕ), (0 : ℕ).ascFactorial k.succ = 0
+  | 0 => by
+    rw [ascFactorial_succ, ascFactorial_zero, zero_add, zero_mul]
+  | (k+1) => by
+    rw [ascFactorial_succ, zero_ascFactorial k, mul_zero]
+
+@[simp]
+theorem one_ascFactorial : ∀ (k : ℕ), (1 : ℕ).ascFactorial k = k.factorial
+  | 0 => ascFactorial_zero 1
+  | (k+1) => by
+    rw [ascFactorial_succ, one_ascFactorial k, add_comm, factorial_succ]
+
 theorem succ_ascFactorial (n : ℕ) :
-    ∀ k, (n + 1) * n.succ.ascFactorial k = (n + k + 1) * n.ascFactorial k
+    ∀ k, n * n.succ.ascFactorial k = (n + k) * n.ascFactorial k
   | 0 => by rw [add_zero, ascFactorial_zero, ascFactorial_zero]
   | k + 1 => by
     rw [ascFactorial, mul_left_comm, succ_ascFactorial n k, ascFactorial, succ_add, ← add_assoc]
 #align nat.succ_asc_factorial Nat.succ_ascFactorial
 
-/-- `n.ascFactorial k = (n + k)! / n!` but without ℕ-division. See `Nat.ascFactorial_eq_div` for
-the version with ℕ-division. -/
-theorem factorial_mul_ascFactorial (n : ℕ) : ∀ k, n ! * n.ascFactorial k = (n + k)!
-  | 0 => by simp
+/-- `(n + 1).ascFactorial k = (n + k) ! / n !` but without ℕ-division. See
+`Nat.ascFactorial_eq_div` for the version with ℕ-division. -/
+theorem factorial_mul_ascFactorial (n : ℕ) : ∀ k, n ! * (n + 1).ascFactorial k = (n + k)!
+  | 0 => by
+    rw [add_zero, ascFactorial_zero, mul_one]
   | k + 1 => by
-    rw [ascFactorial_succ, mul_left_comm, factorial_mul_ascFactorial n k, ← add_assoc, factorial]
+    rw [ascFactorial_succ, ← add_assoc, factorial_succ, mul_comm (n + 1 + k), ← mul_assoc,
+      factorial_mul_ascFactorial n k, mul_comm, add_right_comm]
 #align nat.factorial_mul_asc_factorial Nat.factorial_mul_ascFactorial
 
+/-- `n.ascFactorial k = (n + k - 1)! / (n - 1)!` for `n > 0` but without ℕ-division. See
+`Nat.ascFactorial_eq_div` for the version with ℕ-division. Consider using
+`factorial_mul_ascFactorial` to avoid complications of ℕ-subtraction. -/
+theorem factorial_mul_ascFactorial' (n k : ℕ) (h : 0 < n) :
+    (n - 1) ! * n.ascFactorial k = (n + k - 1)! := by
+  rw [Nat.sub_add_comm h, Nat.sub_one]
+  nth_rw 2 [Nat.eq_add_of_sub_eq h rfl]
+  rw [Nat.sub_one, factorial_mul_ascFactorial]
+
 /-- Avoid in favor of `Nat.factorial_mul_ascFactorial` if you can. ℕ-division isn't worth it. -/
-theorem ascFactorial_eq_div (n k : ℕ) : n.ascFactorial k = (n + k)! / n ! := by
+theorem ascFactorial_eq_div (n k : ℕ) :  (n + 1).ascFactorial k = (n + k)! / n ! := by
   apply mul_left_cancel₀ n.factorial_ne_zero
   rw [factorial_mul_ascFactorial]
-  exact (Nat.mul_div_cancel' <| factorial_dvd_factorial <| le.intro rfl).symm
+  exact (Nat.mul_div_cancel_left' <| factorial_dvd_factorial <| le_add_right n k).symm
+
+/-- Avoid in favor of `Nat.factorial_mul_ascFactorial` if you can. -/
+theorem ascFactorial_eq_div' (n k : ℕ) (h : 0 < n) :
+    n.ascFactorial k = (n + k - 1)! / (n - 1) ! := by
+  apply mul_left_cancel₀ (n-1).factorial_ne_zero
+  rw [factorial_mul_ascFactorial' _ _ h]
+  exact (Nat.mul_div_cancel_left' <| factorial_dvd_factorial <| Nat.sub_le_sub_right
+    (le_add_right n k) 1).symm
 #align nat.asc_factorial_eq_div Nat.ascFactorial_eq_div
 
-theorem ascFactorial_of_sub {n k : ℕ} (h : k < n) :
-    (n - k) * (n - k).ascFactorial k = (n - (k + 1)).ascFactorial (k + 1) := by
-  let t := n - (k + 1)
-  suffices h' : n - k = t + 1 by rw [h', succ_ascFactorial, ascFactorial_succ]
-  rw [← tsub_tsub_assoc (succ_le_of_lt h) (succ_pos k), succ_sub_one]
+theorem ascFactorial_of_sub {n k : ℕ}:
+    (n - k) * (n - k + 1).ascFactorial k = (n - k).ascFactorial (k + 1) := by
+  rw [succ_ascFactorial, ascFactorial_succ]
 #align nat.asc_factorial_of_sub Nat.ascFactorial_of_sub
 
-theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, (n + 1) ^ k ≤ n.ascFactorial k
+theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, n ^ k ≤ n.ascFactorial k
   | 0 => by rw [ascFactorial_zero, pow_zero]
   | k + 1 => by
-    rw [pow_succ, mul_comm]
-    exact Nat.mul_le_mul (Nat.add_le_add_right le_self_add _) (pow_succ_le_ascFactorial _ k)
+    rw [pow_succ, mul_comm, ascFactorial_succ, ← succ_ascFactorial]
+    exact Nat.mul_le_mul (Nat.le_refl n)
+      ((pow_le_pow_of_le_left (le_succ n) k).trans (pow_succ_le_ascFactorial n.succ k))
 #align nat.pow_succ_le_asc_factorial Nat.pow_succ_le_ascFactorial
 
-theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < n.ascFactorial (k + 2) := by
+theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < (n + 1).ascFactorial (k + 2) := by
   rw [pow_succ, ascFactorial, mul_comm]
-  exact
-    Nat.mul_lt_mul (Nat.add_lt_add_right (Nat.lt_add_of_pos_right succ_pos') 1)
-      (pow_succ_le_ascFactorial n _) (pow_pos succ_pos' _)
+  exact Nat.mul_lt_mul (lt_add_of_pos_right (n + 1) (succ_pos k))
+    (pow_succ_le_ascFactorial n.succ _) (NeZero.pos ((n + 1) ^ (k + 1)))
 #align nat.pow_lt_asc_factorial' Nat.pow_lt_ascFactorial'
 
-theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k < n.ascFactorial k
+theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k < (n + 1).ascFactorial k
   | 0 => by rintro ⟨⟩
   | 1 => by intro; contradiction
   | k + 2 => fun _ => pow_lt_ascFactorial' n k
 #align nat.pow_lt_asc_factorial Nat.pow_lt_ascFactorial
 
-theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, n.ascFactorial k ≤ (n + k) ^ k
+theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, (n+1).ascFactorial k ≤ (n + k) ^ k
   | 0 => by rw [ascFactorial_zero, pow_zero]
   | k + 1 => by
-    rw [ascFactorial_succ, pow_succ, ← add_assoc, mul_comm _ (succ (n + k))]
-    exact
-      Nat.mul_le_mul_of_nonneg_left
-        ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_left (le_succ _) _))
+    rw [ascFactorial_succ, pow_succ, mul_comm, ← add_assoc, add_right_comm n 1 k]
+    exact Nat.mul_le_mul_of_nonneg_right
+      ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
 #align nat.asc_factorial_le_pow_add Nat.ascFactorial_le_pow_add
 
-theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFactorial k < (n + k) ^ k
+theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1).ascFactorial k < (n + k) ^ k
   | 0 => by rintro ⟨⟩
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
-    rw [ascFactorial_succ, pow_succ]
-    rw [add_assoc n (k + 1) 1, mul_comm <| (n + (k + 2)) ^ (k + 1)]
-    exact mul_lt_mul_of_pos_left ((ascFactorial_le_pow_add n _).trans_lt <|
-      Nat.pow_lt_pow_left (lt_add_one _) k.succ_ne_zero) (succ_pos _)
+    rw [pow_succ, mul_comm, ascFactorial_succ, succ_add_eq_add_succ n (k + 1)]
+    exact Nat.mul_lt_mul' le_rfl ((ascFactorial_le_pow_add n _).trans_lt
+      (pow_lt_pow_left (@lt_add_one ℕ _ _ _ _ _ _ _) (zero_le _) k.succ_ne_zero)) (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
 
-theorem ascFactorial_pos (n k : ℕ) : 0 < n.ascFactorial k :=
-  (pow_pos (succ_pos n) k).trans_le (pow_succ_le_ascFactorial n k)
+theorem ascFactorial_pos (n k : ℕ) : 0 < (n + 1).ascFactorial k :=
+  (pow_pos (succ_pos n) k).trans_le (pow_succ_le_ascFactorial (n + 1) k)
 #align nat.asc_factorial_pos Nat.ascFactorial_pos
 
 end AscFactorial
@@ -379,13 +399,22 @@ theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial
 alias ⟨_, descFactorial_of_lt⟩ := descFactorial_eq_zero_iff_lt
 #align nat.desc_factorial_of_lt Nat.descFactorial_of_lt
 
-theorem add_descFactorial_eq_ascFactorial (n : ℕ) :
-    ∀ k : ℕ, (n + k).descFactorial k = n.ascFactorial k
+theorem add_descFactorial_eq_ascFactorial (n : ℕ) : ∀ k : ℕ,
+    (n + k).descFactorial k = (n + 1).ascFactorial k
   | 0 => by rw [ascFactorial_zero, descFactorial_zero]
-  | succ k => by rw [Nat.add_succ, succ_descFactorial_succ, ascFactorial_succ,
-    add_descFactorial_eq_ascFactorial _ k]
+  | succ k => by
+    rw [Nat.add_succ, succ_descFactorial_succ, ascFactorial_succ,
+      add_descFactorial_eq_ascFactorial _ k, Nat.add_right_comm]
 #align nat.add_desc_factorial_eq_asc_factorial Nat.add_descFactorial_eq_ascFactorial
 
+theorem add_descFactorial_eq_ascFactorial' (n : ℕ) :
+    ∀ k : ℕ, (n + k - 1).descFactorial k = n.ascFactorial k
+  | 0 => by rw [ascFactorial_zero, descFactorial_zero]
+  | succ k => by
+    rw [descFactorial_succ, ascFactorial_succ, ← succ_add_eq_add_succ,
+      add_descFactorial_eq_ascFactorial' _ k, ← succ_ascFactorial, succ_add_sub_one,
+      Nat.add_sub_cancel]
+
 /-- `n.descFactorial k = n! / (n - k)!` but without ℕ-division. See `Nat.descFactorial_eq_div`
 for the version using ℕ-division. -/
 theorem factorial_mul_descFactorial : ∀ {n k : ℕ}, k ≤ n → (n - k)! * n.descFactorial k = n !

d012cd09

chore(Data/Nat/Choose/Multinomial): Golf (#9534)

and n ! ≤ n ^ n

From LeanAPAP

028b9693

Diff

@@ -207,6 +207,14 @@ theorem factorial_mul_pow_sub_le_factorial {n m : ℕ} (hnm : n ≤ m) : n ! * n
     _ ≤ _ := by simpa [hnm] using @Nat.factorial_mul_pow_le_factorial n (m - n)
 #align nat.factorial_mul_pow_sub_le_factorial Nat.factorial_mul_pow_sub_le_factorial
 
+lemma factorial_le_pow : ∀ n, n ! ≤ n ^ n
+  | 0 => le_rfl
+  | n + 1 =>
+    calc
+      _ ≤ (n + 1) * n ^ n := mul_le_mul_left' n.factorial_le_pow _
+      _ ≤ (n + 1) * (n + 1) ^ n := mul_le_mul_left' (Nat.pow_le_pow_left n.le_succ _) _
+      _ = _ := by rw [pow_succ']
+
 end Factorial
 
 /-! ### Ascending and descending factorials -/

d012cd09

chore(*): replace $ with <| (#9319)

See Zulip thread for the discussion.

9f6d3388

Diff

@@ -302,7 +302,7 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFact
   | k + 2 => fun _ => by
     rw [ascFactorial_succ, pow_succ]
     rw [add_assoc n (k + 1) 1, mul_comm <| (n + (k + 2)) ^ (k + 1)]
-    exact mul_lt_mul_of_pos_left ((ascFactorial_le_pow_add n _).trans_lt $
+    exact mul_lt_mul_of_pos_left ((ascFactorial_le_pow_add n _).trans_lt <|
       Nat.pow_lt_pow_left (lt_add_one _) k.succ_ne_zero) (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add

d012cd09

feat: The double factorial is positive (#9102)

and other basic results. Also include a positivity extension to encode that new result.

From LeanAPAP

61efe6de

Diff

@@ -449,4 +449,16 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
 
 end DescFactorial
 
+lemma factorial_two_mul_le (n : ℕ) : (2 * n)! ≤ (2 * n) ^ n * n ! := by
+  rw [two_mul, ← factorial_mul_ascFactorial, mul_comm]
+  exact mul_le_mul_right' (ascFactorial_le_pow_add _ _) _
+
+lemma two_pow_mul_factorial_le_factorial_two_mul (n : ℕ) : 2 ^ n * n ! ≤ (2 * n) ! := by
+  obtain _ | n := n
+  · simp
+  rw [mul_comm, two_mul]
+  calc
+    _ ≤ (n + 1)! * (n + 2) ^ (n + 1) := mul_le_mul_left' (pow_le_pow_of_le_left le_add_self _) _
+    _ ≤ _ := Nat.factorial_mul_pow_le_factorial
+
 end Nat

d012cd09

chore: Rename pow monotonicity lemmas (#9095)

The names for lemmas about monotonicity of (a ^ ·) and (· ^ n) were a mess. This PR tidies up everything related by following the naming convention for (a * ·) and (· * b). Namely, (a ^ ·) is pow_right and (· ^ n) is pow_left in lemma names. All lemma renames follow the corresponding multiplication lemma names closely.

Renames

`Algebra.GroupPower.Order`

pow_mono → pow_right_mono
pow_le_pow → pow_le_pow_right
pow_le_pow_of_le_left → pow_le_pow_left
pow_lt_pow_of_lt_left → pow_lt_pow_left
strictMonoOn_pow → pow_left_strictMonoOn
pow_strictMono_right → pow_right_strictMono
pow_lt_pow → pow_lt_pow_right
pow_lt_pow_iff → pow_lt_pow_iff_right
pow_le_pow_iff → pow_le_pow_iff_right
self_lt_pow → lt_self_pow
strictAnti_pow → pow_right_strictAnti
pow_lt_pow_iff_of_lt_one → pow_lt_pow_iff_right_of_lt_one
pow_lt_pow_of_lt_one → pow_lt_pow_right_of_lt_one
lt_of_pow_lt_pow → lt_of_pow_lt_pow_left
le_of_pow_le_pow → le_of_pow_le_pow_left
pow_lt_pow₀ → pow_lt_pow_right₀

`Algebra.GroupPower.CovariantClass`

pow_le_pow_of_le_left' → pow_le_pow_left'
nsmul_le_nsmul_of_le_right → nsmul_le_nsmul_right
pow_lt_pow' → pow_lt_pow_right'
nsmul_lt_nsmul → nsmul_lt_nsmul_left
pow_strictMono_left → pow_right_strictMono'
nsmul_strictMono_right → nsmul_left_strictMono
StrictMono.pow_right' → StrictMono.pow_const
StrictMono.nsmul_left → StrictMono.const_nsmul
pow_strictMono_right' → pow_left_strictMono
nsmul_strictMono_left → nsmul_right_strictMono
Monotone.pow_right → Monotone.pow_const
Monotone.nsmul_left → Monotone.const_nsmul
lt_of_pow_lt_pow' → lt_of_pow_lt_pow_left'
lt_of_nsmul_lt_nsmul → lt_of_nsmul_lt_nsmul_right
pow_le_pow' → pow_le_pow_right'
nsmul_le_nsmul → nsmul_le_nsmul_left
pow_le_pow_of_le_one' → pow_le_pow_right_of_le_one'
nsmul_le_nsmul_of_nonpos → nsmul_le_nsmul_left_of_nonpos
le_of_pow_le_pow' → le_of_pow_le_pow_left'
le_of_nsmul_le_nsmul' → le_of_nsmul_le_nsmul_right'
pow_le_pow_iff' → pow_le_pow_iff_right'
nsmul_le_nsmul_iff → nsmul_le_nsmul_iff_left
pow_lt_pow_iff' → pow_lt_pow_iff_right'
nsmul_lt_nsmul_iff → nsmul_lt_nsmul_iff_left

`Data.Nat.Pow`

Nat.pow_lt_pow_of_lt_left → Nat.pow_lt_pow_left
Nat.pow_le_iff_le_left → Nat.pow_le_pow_iff_left
Nat.pow_lt_iff_lt_left → Nat.pow_lt_pow_iff_left

Lemmas added

pow_le_pow_iff_left
pow_lt_pow_iff_left
pow_right_injective
pow_right_inj
Nat.pow_le_pow_left to have the correct name since Nat.pow_le_pow_of_le_left is in Std.
Nat.pow_le_pow_right to have the correct name since Nat.pow_le_pow_of_le_right is in Std.

Lemmas removed

self_le_pow was a duplicate of le_self_pow.
Nat.pow_lt_pow_of_lt_right is defeq to pow_lt_pow_right.
Nat.pow_right_strictMono is defeq to pow_right_strictMono.
Nat.pow_le_iff_le_right is defeq to pow_le_pow_iff_right.
Nat.pow_lt_iff_lt_right is defeq to pow_lt_pow_iff_right.

Other changes

A bunch of proofs have been golfed.
Some lemma assumptions have been turned from 0 < n or 1 ≤ n to n ≠ 0.
A few Nat lemmas have been protected.
One docstring has been fixed.

d61c95e1

Diff

@@ -202,13 +202,9 @@ theorem add_factorial_le_factorial_add (i : ℕ) {n : ℕ} (n1 : 1 ≤ n) : i +
 #align nat.add_factorial_le_factorial_add Nat.add_factorial_le_factorial_add
 
 theorem factorial_mul_pow_sub_le_factorial {n m : ℕ} (hnm : n ≤ m) : n ! * n ^ (m - n) ≤ m ! := by
-  suffices n ! * (n + 1) ^ (m - n) ≤ m ! from by
-    apply LE.le.trans _ this
-    apply mul_le_mul_left
-    apply pow_le_pow_of_le_left (le_succ n)
-  have := @Nat.factorial_mul_pow_le_factorial n (m - n)
-  simp? [hnm] at this says simp only [ge_iff_le, hnm, add_tsub_cancel_of_le] at this
-  exact this
+  calc
+    _ ≤ n ! * (n + 1) ^ (m - n) := mul_le_mul_left' (Nat.pow_le_pow_left n.le_succ _) _
+    _ ≤ _ := by simpa [hnm] using @Nat.factorial_mul_pow_le_factorial n (m - n)
 #align nat.factorial_mul_pow_sub_le_factorial Nat.factorial_mul_pow_sub_le_factorial
 
 end Factorial
@@ -297,7 +293,7 @@ theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, n.ascFactorial k ≤ (n
     rw [ascFactorial_succ, pow_succ, ← add_assoc, mul_comm _ (succ (n + k))]
     exact
       Nat.mul_le_mul_of_nonneg_left
-        ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
+        ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_left (le_succ _) _))
 #align nat.asc_factorial_le_pow_add Nat.ascFactorial_le_pow_add
 
 theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFactorial k < (n + k) ^ k
@@ -306,11 +302,8 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFact
   | k + 2 => fun _ => by
     rw [ascFactorial_succ, pow_succ]
     rw [add_assoc n (k + 1) 1, mul_comm <| (n + (k + 2)) ^ (k + 1)]
-    refine'
-      Nat.mul_lt_mul' le_rfl
-        ((ascFactorial_le_pow_add n _).trans_lt
-          (pow_lt_pow_of_lt_left (lt_add_one _) (succ_pos _)))
-        (succ_pos _)
+    exact mul_lt_mul_of_pos_left ((ascFactorial_le_pow_add n _).trans_lt $
+      Nat.pow_lt_pow_left (lt_add_one _) k.succ_ne_zero) (succ_pos _)
 #align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
 
 theorem ascFactorial_pos (n k : ℕ) : 0 < n.ascFactorial k :=
@@ -409,7 +402,7 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
   | k + 1 => by
     rw [descFactorial_succ, pow_succ, succ_sub_succ, mul_comm]
     apply Nat.mul_le_mul_of_nonneg_left
-    exact   (le_trans (Nat.pow_le_pow_of_le_left (tsub_le_tsub_right (le_succ _) _) k)
+    exact   (le_trans (Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ _) _) k)
           (pow_sub_le_descFactorial n k))
 #align nat.pow_sub_le_desc_factorial Nat.pow_sub_le_descFactorial
 
@@ -423,7 +416,7 @@ theorem pow_sub_lt_descFactorial' {n : ℕ} :
   | k + 1 => fun h => by
     rw [descFactorial_succ, pow_succ, mul_comm]
     apply Nat.mul_lt_mul_of_pos_left
-    · refine' ((Nat.pow_le_pow_of_le_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _)
+    · refine' ((Nat.pow_le_pow_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _)
       rw [succ_sub_succ]
       exact pow_sub_lt_descFactorial' ((le_succ _).trans h)
     · apply tsub_pos_of_lt; apply h

d012cd09

chore: Remove nonterminal simp at (#7795)

Removes nonterminal uses of simp at. Replaces most of these with instances of simp? ... says.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

4160b2aa

Diff

@@ -207,7 +207,7 @@ theorem factorial_mul_pow_sub_le_factorial {n m : ℕ} (hnm : n ≤ m) : n ! * n
     apply mul_le_mul_left
     apply pow_le_pow_of_le_left (le_succ n)
   have := @Nat.factorial_mul_pow_le_factorial n (m - n)
-  simp [hnm] at this
+  simp? [hnm] at this says simp only [ge_iff_le, hnm, add_tsub_cancel_of_le] at this
   exact this
 #align nat.factorial_mul_pow_sub_le_factorial Nat.factorial_mul_pow_sub_le_factorial

d012cd09

fix: some cleanup in Nat.Factorial.Basic (#8422)

Also remove some unimportant porting notes in Order.Concept.

e7f5d814

Diff

@@ -39,23 +39,20 @@ section Factorial
 
 variable {m n : ℕ}
 
-@[simp]
-theorem factorial_zero : 0! = 1 :=
+@[simp] theorem factorial_zero : 0! = 1 :=
   rfl
 #align nat.factorial_zero Nat.factorial_zero
 
-theorem factorial_succ (n : ℕ) : n.succ ! = (n + 1) * n ! :=
+theorem factorial_succ (n : ℕ) : (n + 1)! = (n + 1) * n ! :=
   rfl
 #align nat.factorial_succ Nat.factorial_succ
 
 
--- Porting note: can be proved by simp, @[simp] removed
-theorem factorial_one : 1! = 1 :=
+@[simp] theorem factorial_one : 1! = 1 :=
   rfl
 #align nat.factorial_one Nat.factorial_one
 
--- Porting note: can be proved by simp, @[simp] removed
-theorem factorial_two : 2! = 2 :=
+@[simp] theorem factorial_two : 2! = 2 :=
   rfl
 #align nat.factorial_two Nat.factorial_two
 
@@ -84,31 +81,24 @@ theorem dvd_factorial : ∀ {m n}, 0 < m → m ≤ n → m ∣ n !
   | succ _, _, _, h => dvd_of_mul_right_dvd (factorial_dvd_factorial h)
 #align nat.dvd_factorial Nat.dvd_factorial
 
-@[mono]
+@[mono, gcongr]
 theorem factorial_le {m n} (h : m ≤ n) : m ! ≤ n ! :=
   le_of_dvd (factorial_pos _) (factorial_dvd_factorial h)
 #align nat.factorial_le Nat.factorial_le
 
--- Porting note: Interconversion between `succ` and `· + 1` has to be done manually
-theorem factorial_mul_pow_le_factorial : ∀ {m n : ℕ}, m ! * m.succ ^ n ≤ (m + n)!
+theorem factorial_mul_pow_le_factorial : ∀ {m n : ℕ}, m ! * (m + 1) ^ n ≤ (m + n)!
   | m, 0 => by simp
   | m, n + 1 => by
-    rw [← add_assoc, ← Nat.succ_eq_add_one (m + n), Nat.factorial_succ, pow_succ',
-        mul_comm (_ + 1), mul_comm (succ m), ← mul_assoc]
-    exact
-      mul_le_mul factorial_mul_pow_le_factorial (Nat.succ_le_succ (Nat.le_add_right _ _))
-        (Nat.zero_le _) (Nat.zero_le _)
+    rw [← add_assoc, factorial_succ, mul_comm (_ + 1), pow_succ, ← mul_assoc]
+    exact Nat.mul_le_mul factorial_mul_pow_le_factorial (succ_le_succ (le_add_right _ _))
 #align nat.factorial_mul_pow_le_factorial Nat.factorial_mul_pow_le_factorial
 
 theorem monotone_factorial : Monotone factorial := fun _ _ => factorial_le
 #align nat.monotone_factorial Nat.monotone_factorial
 
-@[gcongr]
-lemma factorial_le_of_le {m n : ℕ} (h : n ≤ m) : n ! ≤ m ! := monotone_factorial h
-
 theorem factorial_lt (hn : 0 < n) : n ! < m ! ↔ n < m := by
   refine' ⟨fun h => not_le.mp fun hmn => not_le_of_lt h (factorial_le hmn), fun h => _⟩
-  have : ∀ {n}, 0 < n → n ! < n.succ ! := by
+  have : ∀ {n}, 0 < n → n ! < (n + 1)! := by
     intro k hk
     rw [factorial_succ, succ_mul, lt_add_iff_pos_left]
     exact mul_pos hk k.factorial_pos
@@ -120,40 +110,43 @@ theorem factorial_lt (hn : 0 < n) : n ! < m ! ↔ n < m := by
 @[gcongr]
 lemma factorial_lt_of_lt {m n : ℕ} (hn : 0 < n) (h : n < m) : n ! < m ! := (factorial_lt hn).mpr h
 
+@[simp]
 theorem one_lt_factorial : 1 < n ! ↔ 1 < n :=
   factorial_lt one_pos
 #align nat.one_lt_factorial Nat.one_lt_factorial
 
--- Porting note: `(_ | _)` notation for introduction with cases does not appear to be supported
+@[simp]
 theorem factorial_eq_one : n ! = 1 ↔ n ≤ 1 := by
-  apply Iff.intro <;> intro
-  · rw [← not_lt, ← one_lt_factorial, ‹n ! = 1›]
+  constructor
+  · intro h
+    rw [← not_lt, ← one_lt_factorial, h]
     apply lt_irrefl
-  · cases ‹n ≤ 1›
-    · rfl
-    · cases ‹n ≤ 0›; rfl
+  · rintro (_|_|_) <;> rfl
 #align nat.factorial_eq_one Nat.factorial_eq_one
 
-theorem factorial_inj (hn : 1 < n !) : n ! = m ! ↔ n = m := by
+theorem factorial_inj (hn : 1 < n) : n ! = m ! ↔ n = m := by
   refine' ⟨fun h => _, congr_arg _⟩
   obtain hnm | rfl | hnm := lt_trichotomy n m
-  · rw [← factorial_lt <| pos_of_gt <| one_lt_factorial.mp hn, h] at hnm
+  · rw [← factorial_lt <| pos_of_gt hn, h] at hnm
     cases lt_irrefl _ hnm
   · rfl
-  rw [h, one_lt_factorial] at hn
-  rw [← factorial_lt (lt_trans one_pos hn), h] at hnm
+  rw [← one_lt_factorial, h, one_lt_factorial] at hn
+  rw [← factorial_lt <| pos_of_gt hn, h] at hnm
   cases lt_irrefl _ hnm
 #align nat.factorial_inj Nat.factorial_inj
 
+theorem factorial_inj' (h : 1 < n ∨ 1 < m) : n ! = m ! ↔ n = m := by
+  obtain hn|hm := h
+  · exact factorial_inj hn
+  · rw [eq_comm, factorial_inj hm, eq_comm]
+
 theorem self_le_factorial : ∀ n : ℕ, n ≤ n !
   | 0 => zero_le_one
   | k + 1 => le_mul_of_one_le_right k.zero_lt_succ.le (Nat.one_le_of_lt <| Nat.factorial_pos _)
 #align nat.self_le_factorial Nat.self_le_factorial
 
--- Porting note: `zero_lt_two` does not work since `ZeroLEOneClass` fails to be synthesised.
--- Porting note: `0 < 2` is proved `by decide` instead
 theorem lt_factorial_self {n : ℕ} (hi : 3 ≤ n) : n < n ! := by
-  have : 0 < n := (by decide : 0 < 2).trans (succ_le_iff.mp hi)
+  have : 0 < n := (zero_lt_two (α := ℕ)).trans (succ_le_iff.mp hi)
   have : 1 < pred n := le_pred_of_lt (succ_le_iff.mp hi)
   rw [← succ_pred_eq_of_pos ‹0 < n›, factorial_succ]
   exact
@@ -163,7 +156,7 @@ theorem lt_factorial_self {n : ℕ} (hi : 3 ≤ n) : n < n ! := by
 
 theorem add_factorial_succ_lt_factorial_add_succ {i : ℕ} (n : ℕ) (hi : 2 ≤ i) :
     i + (n + 1)! < (i + n + 1)! := by
-  rw [← Nat.succ_eq_add_one (i + _), factorial_succ (i + _), add_mul, one_mul]
+  rw [factorial_succ (i + _), add_mul, one_mul]
   have : i ≤ i + n := le.intro rfl
   exact
     add_lt_add_of_lt_of_le
@@ -195,8 +188,7 @@ theorem add_factorial_succ_le_factorial_add_succ (i : ℕ) (n : ℕ) :
   · match i with
     | 0 => simp
     | 1 =>
-      rw [← add_assoc, ← Nat.succ_eq_add_one (1 + n), factorial_succ (1 + n),
-        add_mul, one_mul, add_comm 1 n, add_le_add_iff_right]
+      rw [← add_assoc, factorial_succ (1 + n), add_mul, one_mul, add_comm 1 n, add_le_add_iff_right]
       apply one_le_mul
       · apply Nat.le_add_left
       · apply factorial_pos
@@ -246,28 +238,23 @@ theorem zero_ascFactorial (k : ℕ) : (0 : ℕ).ascFactorial k = k ! := by
   rw [ascFactorial, ht, zero_add, Nat.factorial_succ]
 #align nat.zero_asc_factorial Nat.zero_ascFactorial
 
-theorem ascFactorial_succ {n k : ℕ} : n.ascFactorial k.succ = (n + k + 1) * n.ascFactorial k :=
+theorem ascFactorial_succ {n k : ℕ} : n.ascFactorial (k + 1) = (n + k + 1) * n.ascFactorial k :=
   rfl
 #align nat.asc_factorial_succ Nat.ascFactorial_succ
 
--- Porting note: Explicit arguments are required to show that the recursion terminates
 theorem succ_ascFactorial (n : ℕ) :
     ∀ k, (n + 1) * n.succ.ascFactorial k = (n + k + 1) * n.ascFactorial k
   | 0 => by rw [add_zero, ascFactorial_zero, ascFactorial_zero]
   | k + 1 => by
-    rw [ascFactorial, mul_left_comm, succ_ascFactorial n k, ascFactorial,
-      succ_add, ← add_assoc, succ_eq_add_one]
+    rw [ascFactorial, mul_left_comm, succ_ascFactorial n k, ascFactorial, succ_add, ← add_assoc]
 #align nat.succ_asc_factorial Nat.succ_ascFactorial
 
 /-- `n.ascFactorial k = (n + k)! / n!` but without ℕ-division. See `Nat.ascFactorial_eq_div` for
 the version with ℕ-division. -/
--- Porting note: Explicit arguments are required to show that the recursion terminates
--- Porting note: Interconversion between `succ` and `· + 1` has to be done manually
 theorem factorial_mul_ascFactorial (n : ℕ) : ∀ k, n ! * n.ascFactorial k = (n + k)!
-  | 0 => by rw [ascFactorial, add_zero, mul_one]
+  | 0 => by simp
   | k + 1 => by
-    rw [ascFactorial_succ, mul_left_comm, factorial_mul_ascFactorial n k,
-      ← add_assoc, ← Nat.succ_eq_add_one (n + k), factorial]
+    rw [ascFactorial_succ, mul_left_comm, factorial_mul_ascFactorial n k, ← add_assoc, factorial]
 #align nat.factorial_mul_asc_factorial Nat.factorial_mul_ascFactorial
 
 /-- Avoid in favor of `Nat.factorial_mul_ascFactorial` if you can. ℕ-division isn't worth it. -/
@@ -279,10 +266,9 @@ theorem ascFactorial_eq_div (n k : ℕ) : n.ascFactorial k = (n + k)! / n ! := b
 
 theorem ascFactorial_of_sub {n k : ℕ} (h : k < n) :
     (n - k) * (n - k).ascFactorial k = (n - (k + 1)).ascFactorial (k + 1) := by
-  let t := n - k.succ
-  let ht : t = n - k.succ := rfl
-  suffices h' : n - k = t.succ by rw [← ht, h', succ_ascFactorial, ascFactorial_succ]
-  rw [ht, succ_eq_add_one, ← tsub_tsub_assoc (succ_le_of_lt h) (succ_pos _), succ_sub_one]
+  let t := n - (k + 1)
+  suffices h' : n - k = t + 1 by rw [h', succ_ascFactorial, ascFactorial_succ]
+  rw [← tsub_tsub_assoc (succ_le_of_lt h) (succ_pos k), succ_sub_one]
 #align nat.asc_factorial_of_sub Nat.ascFactorial_of_sub
 
 theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, (n + 1) ^ k ≤ n.ascFactorial k
@@ -308,8 +294,7 @@ theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k <
 theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, n.ascFactorial k ≤ (n + k) ^ k
   | 0 => by rw [ascFactorial_zero, pow_zero]
   | k + 1 => by
-    rw [ascFactorial_succ, pow_succ, ← add_assoc,
-    ← Nat.succ_eq_add_one (n + k), mul_comm _ (succ (n + k))]
+    rw [ascFactorial_succ, pow_succ, ← add_assoc, mul_comm _ (succ (n + k))]
     exact
       Nat.mul_le_mul_of_nonneg_left
         ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
@@ -350,32 +335,17 @@ theorem descFactorial_zero (n : ℕ) : n.descFactorial 0 = 1 :=
 #align nat.desc_factorial_zero Nat.descFactorial_zero
 
 @[simp]
-theorem descFactorial_succ (n k : ℕ) : n.descFactorial k.succ = (n - k) * n.descFactorial k :=
+theorem descFactorial_succ (n k : ℕ) : n.descFactorial (k + 1) = (n - k) * n.descFactorial k :=
   rfl
 #align nat.desc_factorial_succ Nat.descFactorial_succ
 
-theorem zero_descFactorial_succ (k : ℕ) : (0 : ℕ).descFactorial k.succ = 0 := by
+theorem zero_descFactorial_succ (k : ℕ) : (0 : ℕ).descFactorial (k + 1) = 0 := by
   rw [descFactorial_succ, zero_tsub, zero_mul]
 #align nat.zero_desc_factorial_succ Nat.zero_descFactorial_succ
 
-/- Porting note: simp removed because this can be proved by
-simp only [Nat.descFactorial_succ, nonpos_iff_eq_zero, tsub_zero, Nat.descFactorial_zero, mul_one]
--/
--- @[simp]
-theorem descFactorial_one (n : ℕ) : n.descFactorial 1 = n := by
-  rw [descFactorial_succ, descFactorial_zero, mul_one, tsub_zero]
+theorem descFactorial_one (n : ℕ) : n.descFactorial 1 = n := by simp
 #align nat.desc_factorial_one Nat.descFactorial_one
 
-/- Porting note: simp removed because the lhs simplifies,
-according to the linter:
-Left-hand side simplifies from
-  Nat.descFactorial (n + 1) (k + 1)
-to
-  (n + 1 - k) * Nat.descFactorial (n + 1) k
-using
-  simp only [Nat.descFactorial_succ]
--/
--- @[simp]
 theorem succ_descFactorial_succ (n : ℕ) :
     ∀ k : ℕ, (n + 1).descFactorial (k + 1) = (n + 1) * n.descFactorial k
   | 0 => by rw [descFactorial_zero, descFactorial_one, mul_one]
@@ -411,9 +381,8 @@ alias ⟨_, descFactorial_of_lt⟩ := descFactorial_eq_zero_iff_lt
 theorem add_descFactorial_eq_ascFactorial (n : ℕ) :
     ∀ k : ℕ, (n + k).descFactorial k = n.ascFactorial k
   | 0 => by rw [ascFactorial_zero, descFactorial_zero]
-  | succ k => by
-    rw [Nat.add_succ, Nat.succ_eq_add_one, Nat.succ_eq_add_one,
-        succ_descFactorial_succ, ascFactorial_succ, add_descFactorial_eq_ascFactorial _ k]
+  | succ k => by rw [Nat.add_succ, succ_descFactorial_succ, ascFactorial_succ,
+    add_descFactorial_eq_ascFactorial _ k]
 #align nat.add_desc_factorial_eq_asc_factorial Nat.add_descFactorial_eq_ascFactorial
 
 /-- `n.descFactorial k = n! / (n - k)!` but without ℕ-division. See `Nat.descFactorial_eq_div`

d012cd09

chore: typo ascPochhammer (#8391)

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

b460f535

Diff

@@ -338,7 +338,7 @@ section DescFactorial
 
 /-- `n.descFactorial k = n! / (n - k)!` (as seen in `Nat.descFactorial_eq_div`), but
 implemented recursively to allow for "quick" computation when using `norm_num`. This is closely
-related to `ascPochhammer`, but much less general. -/
+related to `descPochhammer`, but much less general. -/
 def descFactorial (n : ℕ) : ℕ → ℕ
   | 0 => 1
   | k + 1 => (n - k) * descFactorial n k

d012cd09

chore: rm [@simp](https://github.com/simp) from factorial (#7078)

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

fe39449a

Diff

@@ -27,7 +27,6 @@ This file defines the factorial, along with the ascending and descending variant
 namespace Nat
 
 /-- `Nat.factorial n` is the factorial of `n`. -/
-@[simp]
 def factorial : ℕ → ℕ
   | 0 => 1
   | succ n => succ n * factorial n

d012cd09

chore: rename pochhammer (#6917)

We rename pochhammer to ascPochhammer to prepare adding descPochhammer.

Co-authored-by: Moritz Firsching <firsching@google.com> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>

ae1eb5e7

Diff

@@ -229,7 +229,7 @@ section AscFactorial
 
 /-- `n.ascFactorial k = (n + k)! / n!` (as seen in `Nat.ascFactorial_eq_div`), but implemented
 recursively to allow for "quick" computation when using `norm_num`. This is closely related to
-`pochhammer`, but much less general. -/
+`ascPochhammer`, but much less general. -/
 def ascFactorial (n : ℕ) : ℕ → ℕ
   | 0 => 1
   | k + 1 => (n + k + 1) * ascFactorial n k
@@ -339,7 +339,7 @@ section DescFactorial
 
 /-- `n.descFactorial k = n! / (n - k)!` (as seen in `Nat.descFactorial_eq_div`), but
 implemented recursively to allow for "quick" computation when using `norm_num`. This is closely
-related to `pochhammer`, but much less general. -/
+related to `ascPochhammer`, but much less general. -/
 def descFactorial (n : ℕ) : ℕ → ℕ
   | 0 => 1
   | k + 1 => (n - k) * descFactorial n k

d012cd09

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

@@ -282,7 +282,7 @@ theorem ascFactorial_of_sub {n k : ℕ} (h : k < n) :
     (n - k) * (n - k).ascFactorial k = (n - (k + 1)).ascFactorial (k + 1) := by
   let t := n - k.succ
   let ht : t = n - k.succ := rfl
-  suffices h' : n - k = t.succ; · rw [← ht, h', succ_ascFactorial, ascFactorial_succ]
+  suffices h' : n - k = t.succ by rw [← ht, h', succ_ascFactorial, ascFactorial_succ]
   rw [ht, succ_eq_add_one, ← tsub_tsub_assoc (succ_le_of_lt h) (succ_pos _), succ_sub_one]
 #align nat.asc_factorial_of_sub Nat.ascFactorial_of_sub

d012cd09

chore: delay import of Tactic.Common (#7000)

I know that this is contrary to what we've done previously, but:

I'm trying to upstream a great many tactics from Mathlib to Std (essentially, everything that non-mathematicians want too).
This makes it much easier for me to see what is going on, and understand the import requirements (particularly for the "big" tactics norm_num / ring / linarith)
It's actually not as bad as it looks here, because as these tactics move up to Std they will start disappearing again from explicit imports, but Mathlib can happily import all of Std.

(Oh

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

4f3418a7

Diff

@@ -6,6 +6,7 @@ Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 import Mathlib.Data.Nat.Basic
 import Mathlib.Data.Nat.Pow
 import Mathlib.Tactic.GCongr.Core
+import Mathlib.Tactic.Common
 
 #align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"d012cd09a9b256d870751284dd6a29882b0be105"

d012cd09

chore: rm @[simp] from factorial_succ (#6840)

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

e8477a93

Diff

@@ -44,7 +44,6 @@ theorem factorial_zero : 0! = 1 :=
   rfl
 #align nat.factorial_zero Nat.factorial_zero
 
-@[simp]
 theorem factorial_succ (n : ℕ) : n.succ ! = (n + 1) * n ! :=
   rfl
 #align nat.factorial_succ Nat.factorial_succ

d012cd09

feat: patch for new alias command (#6172)

19e0ba92

Diff

@@ -406,7 +406,7 @@ theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial
     exact fun h _ => h
 #align nat.desc_factorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt
 
-alias descFactorial_eq_zero_iff_lt ↔ _ descFactorial_of_lt
+alias ⟨_, descFactorial_of_lt⟩ := descFactorial_eq_zero_iff_lt
 #align nat.desc_factorial_of_lt Nat.descFactorial_of_lt
 
 theorem add_descFactorial_eq_ascFactorial (n : ℕ) :

d012cd09

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,16 +2,13 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
-
-! This file was ported from Lean 3 source module data.nat.factorial.basic
-! leanprover-community/mathlib commit d012cd09a9b256d870751284dd6a29882b0be105
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Nat.Basic
 import Mathlib.Data.Nat.Pow
 import Mathlib.Tactic.GCongr.Core
 
+#align_import data.nat.factorial.basic from "leanprover-community/mathlib"@"d012cd09a9b256d870751284dd6a29882b0be105"
+
 /-!
 # Factorial and variants

d012cd09

feat: golf IMO 2019 q4 (#5310)

Rewrite the IMO 2019 q4 solution to make the "implicit" calc blocks (lots of lt_of_le_of_lt) explicit, then automate some proofs.

This is not a golf in the sense of decreasing the number of lines (maybe it is if you take into account the number of lines like

intros; rw [sub_nonneg]; apply pow_le_pow; norm_num; apply le_of_lt; rwa [← mem_range]

in the original). So, if desired, I can make this an additional proof rather than a replacement to the existing proof.

9dd09eb1

Diff

@@ -10,6 +10,7 @@ Authors: Mario Carneiro, Chris Hughes, Floris van Doorn, Yaël Dillies
 -/
 import Mathlib.Data.Nat.Basic
 import Mathlib.Data.Nat.Pow
+import Mathlib.Tactic.GCongr.Core
 
 /-!
 # Factorial and variants
@@ -106,6 +107,9 @@ theorem factorial_mul_pow_le_factorial : ∀ {m n : ℕ}, m ! * m.succ ^ n ≤ (
 theorem monotone_factorial : Monotone factorial := fun _ _ => factorial_le
 #align nat.monotone_factorial Nat.monotone_factorial
 
+@[gcongr]
+lemma factorial_le_of_le {m n : ℕ} (h : n ≤ m) : n ! ≤ m ! := monotone_factorial h
+
 theorem factorial_lt (hn : 0 < n) : n ! < m ! ↔ n < m := by
   refine' ⟨fun h => not_le.mp fun hmn => not_le_of_lt h (factorial_le hmn), fun h => _⟩
   have : ∀ {n}, 0 < n → n ! < n.succ ! := by
@@ -117,6 +121,9 @@ theorem factorial_lt (hn : 0 < n) : n ! < m ! ↔ n < m := by
   · exact (ih hn).trans (this <| hn.trans <| lt_of_succ_le hnk)
 #align nat.factorial_lt Nat.factorial_lt
 
+@[gcongr]
+lemma factorial_lt_of_lt {m n : ℕ} (hn : 0 < n) (h : n < m) : n ! < m ! := (factorial_lt hn).mpr h
+
 theorem one_lt_factorial : 1 < n ! ↔ 1 < n :=
   factorial_lt one_pos
 #align nat.one_lt_factorial Nat.one_lt_factorial

d012cd09

feat: quick version of mono tactic (#1740)

This is an extremely partial port of the mono* tactic from Lean 3, implemented as a macro on top of solve_by_elim. The original mono had many configuration options and no documentation, so quite a bit is missing (and almost all the Lean 3 tests fail). Nonetheless I think it's worth merging this, because

it will get rid of errors in mathport output which come from lemmas being tagged with a nonexistent attribute @[mono]
in most mathlib3 uses of mono, only the basic version was used, not the various configuration options; thus I would guess that this version of mono will succeed fairly often in the port even though it fails nearly all the tests

Co-authored-by: thorimur <68410468+thorimur@users.noreply.github.com>

cdd6d9c6

Diff

@@ -87,7 +87,7 @@ theorem dvd_factorial : ∀ {m n}, 0 < m → m ≤ n → m ∣ n !
   | succ _, _, _, h => dvd_of_mul_right_dvd (factorial_dvd_factorial h)
 #align nat.dvd_factorial Nat.dvd_factorial
 
--- Porting note: `mono` not yet implemented @[mono]
+@[mono]
 theorem factorial_le {m n} (h : m ≤ n) : m ! ≤ n ! :=
   le_of_dvd (factorial_pos _) (factorial_dvd_factorial h)
 #align nat.factorial_le Nat.factorial_le

d012cd09

chore: add missing #align statements (#1902)

This PR is the result of a slight variant on the following "algorithm"

take all mathlib 3 names, remove _ and make all uppercase letters into lowercase
take all mathlib 4 names, remove _ and make all uppercase letters into lowercase
look for matches, and create pairs (original_lean3_name, OriginalLean4Name)
for pairs that do not have an align statement:
- use Lean 4 to lookup the file + position of the Lean 4 name
- add an #align statement just before the next empty line
manually fix some tiny mistakes (e.g., empty lines in proofs might cause the #align statement to have been inserted too early)

b72bb858

Diff

@@ -403,6 +403,7 @@ theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial
 #align nat.desc_factorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt
 
 alias descFactorial_eq_zero_iff_lt ↔ _ descFactorial_of_lt
+#align nat.desc_factorial_of_lt Nat.descFactorial_of_lt
 
 theorem add_descFactorial_eq_ascFactorial (n : ℕ) :
     ∀ k : ℕ, (n + k).descFactorial k = n.ascFactorial k

d012cd09

feat: add uppercase lean 3 linter (#1796)

depends on: #1794

Implements a linter for lean 3 declarations containing capital letters (as suggested on Zulip).

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

702d8f3d

Diff

@@ -410,7 +410,7 @@ theorem add_descFactorial_eq_ascFactorial (n : ℕ) :
   | succ k => by
     rw [Nat.add_succ, Nat.succ_eq_add_one, Nat.succ_eq_add_one,
         succ_descFactorial_succ, ascFactorial_succ, add_descFactorial_eq_ascFactorial _ k]
-#align nat.add_descFactorial_eq_asc_factorial Nat.add_descFactorial_eq_ascFactorial
+#align nat.add_desc_factorial_eq_asc_factorial Nat.add_descFactorial_eq_ascFactorial
 
 /-- `n.descFactorial k = n! / (n - k)!` but without ℕ-division. See `Nat.descFactorial_eq_div`
 for the version using ℕ-division. -/

d012cd09

chore: fix most phantom #aligns (#1794)

3d3fb046

Diff

@@ -229,23 +229,23 @@ recursively to allow for "quick" computation when using `norm_num`. This is clos
 def ascFactorial (n : ℕ) : ℕ → ℕ
   | 0 => 1
   | k + 1 => (n + k + 1) * ascFactorial n k
-#align nat.ascFactorial Nat.ascFactorial
+#align nat.asc_factorial Nat.ascFactorial
 
 @[simp]
 theorem ascFactorial_zero (n : ℕ) : n.ascFactorial 0 = 1 :=
   rfl
-#align nat.ascFactorial_zero Nat.ascFactorial_zero
+#align nat.asc_factorial_zero Nat.ascFactorial_zero
 
 @[simp]
 theorem zero_ascFactorial (k : ℕ) : (0 : ℕ).ascFactorial k = k ! := by
   induction' k with t ht
   · rfl
   rw [ascFactorial, ht, zero_add, Nat.factorial_succ]
-#align nat.zero_ascFactorial Nat.zero_ascFactorial
+#align nat.zero_asc_factorial Nat.zero_ascFactorial
 
 theorem ascFactorial_succ {n k : ℕ} : n.ascFactorial k.succ = (n + k + 1) * n.ascFactorial k :=
   rfl
-#align nat.ascFactorial_succ Nat.ascFactorial_succ
+#align nat.asc_factorial_succ Nat.ascFactorial_succ
 
 -- Porting note: Explicit arguments are required to show that the recursion terminates
 theorem succ_ascFactorial (n : ℕ) :
@@ -254,7 +254,7 @@ theorem succ_ascFactorial (n : ℕ) :
   | k + 1 => by
     rw [ascFactorial, mul_left_comm, succ_ascFactorial n k, ascFactorial,
       succ_add, ← add_assoc, succ_eq_add_one]
-#align nat.succ_ascFactorial Nat.succ_ascFactorial
+#align nat.succ_asc_factorial Nat.succ_ascFactorial
 
 /-- `n.ascFactorial k = (n + k)! / n!` but without ℕ-division. See `Nat.ascFactorial_eq_div` for
 the version with ℕ-division. -/
@@ -265,14 +265,14 @@ theorem factorial_mul_ascFactorial (n : ℕ) : ∀ k, n ! * n.ascFactorial k = (
   | k + 1 => by
     rw [ascFactorial_succ, mul_left_comm, factorial_mul_ascFactorial n k,
       ← add_assoc, ← Nat.succ_eq_add_one (n + k), factorial]
-#align nat.factorial_mul_ascFactorial Nat.factorial_mul_ascFactorial
+#align nat.factorial_mul_asc_factorial Nat.factorial_mul_ascFactorial
 
 /-- Avoid in favor of `Nat.factorial_mul_ascFactorial` if you can. ℕ-division isn't worth it. -/
 theorem ascFactorial_eq_div (n k : ℕ) : n.ascFactorial k = (n + k)! / n ! := by
   apply mul_left_cancel₀ n.factorial_ne_zero
   rw [factorial_mul_ascFactorial]
   exact (Nat.mul_div_cancel' <| factorial_dvd_factorial <| le.intro rfl).symm
-#align nat.ascFactorial_eq_div Nat.ascFactorial_eq_div
+#align nat.asc_factorial_eq_div Nat.ascFactorial_eq_div
 
 theorem ascFactorial_of_sub {n k : ℕ} (h : k < n) :
     (n - k) * (n - k).ascFactorial k = (n - (k + 1)).ascFactorial (k + 1) := by
@@ -280,27 +280,27 @@ theorem ascFactorial_of_sub {n k : ℕ} (h : k < n) :
   let ht : t = n - k.succ := rfl
   suffices h' : n - k = t.succ; · rw [← ht, h', succ_ascFactorial, ascFactorial_succ]
   rw [ht, succ_eq_add_one, ← tsub_tsub_assoc (succ_le_of_lt h) (succ_pos _), succ_sub_one]
-#align nat.ascFactorial_of_sub Nat.ascFactorial_of_sub
+#align nat.asc_factorial_of_sub Nat.ascFactorial_of_sub
 
 theorem pow_succ_le_ascFactorial (n : ℕ) : ∀ k : ℕ, (n + 1) ^ k ≤ n.ascFactorial k
   | 0 => by rw [ascFactorial_zero, pow_zero]
   | k + 1 => by
     rw [pow_succ, mul_comm]
     exact Nat.mul_le_mul (Nat.add_le_add_right le_self_add _) (pow_succ_le_ascFactorial _ k)
-#align nat.pow_succ_le_ascFactorial Nat.pow_succ_le_ascFactorial
+#align nat.pow_succ_le_asc_factorial Nat.pow_succ_le_ascFactorial
 
 theorem pow_lt_ascFactorial' (n k : ℕ) : (n + 1) ^ (k + 2) < n.ascFactorial (k + 2) := by
   rw [pow_succ, ascFactorial, mul_comm]
   exact
     Nat.mul_lt_mul (Nat.add_lt_add_right (Nat.lt_add_of_pos_right succ_pos') 1)
       (pow_succ_le_ascFactorial n _) (pow_pos succ_pos' _)
-#align nat.pow_lt_ascFactorial' Nat.pow_lt_ascFactorial'
+#align nat.pow_lt_asc_factorial' Nat.pow_lt_ascFactorial'
 
 theorem pow_lt_ascFactorial (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → (n + 1) ^ k < n.ascFactorial k
   | 0 => by rintro ⟨⟩
   | 1 => by intro; contradiction
   | k + 2 => fun _ => pow_lt_ascFactorial' n k
-#align nat.pow_lt_ascFactorial Nat.pow_lt_ascFactorial
+#align nat.pow_lt_asc_factorial Nat.pow_lt_ascFactorial
 
 theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, n.ascFactorial k ≤ (n + k) ^ k
   | 0 => by rw [ascFactorial_zero, pow_zero]
@@ -310,7 +310,7 @@ theorem ascFactorial_le_pow_add (n : ℕ) : ∀ k : ℕ, n.ascFactorial k ≤ (n
     exact
       Nat.mul_le_mul_of_nonneg_left
         ((ascFactorial_le_pow_add _ k).trans (Nat.pow_le_pow_of_le_left (le_succ _) _))
-#align nat.ascFactorial_le_pow_add Nat.ascFactorial_le_pow_add
+#align nat.asc_factorial_le_pow_add Nat.ascFactorial_le_pow_add
 
 theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFactorial k < (n + k) ^ k
   | 0 => by rintro ⟨⟩
@@ -323,11 +323,11 @@ theorem ascFactorial_lt_pow_add (n : ℕ) : ∀ {k : ℕ}, 2 ≤ k → n.ascFact
         ((ascFactorial_le_pow_add n _).trans_lt
           (pow_lt_pow_of_lt_left (lt_add_one _) (succ_pos _)))
         (succ_pos _)
-#align nat.ascFactorial_lt_pow_add Nat.ascFactorial_lt_pow_add
+#align nat.asc_factorial_lt_pow_add Nat.ascFactorial_lt_pow_add
 
 theorem ascFactorial_pos (n k : ℕ) : 0 < n.ascFactorial k :=
   (pow_pos (succ_pos n) k).trans_le (pow_succ_le_ascFactorial n k)
-#align nat.ascFactorial_pos Nat.ascFactorial_pos
+#align nat.asc_factorial_pos Nat.ascFactorial_pos
 
 end AscFactorial
 
@@ -339,21 +339,21 @@ related to `pochhammer`, but much less general. -/
 def descFactorial (n : ℕ) : ℕ → ℕ
   | 0 => 1
   | k + 1 => (n - k) * descFactorial n k
-#align nat.descFactorial Nat.descFactorial
+#align nat.desc_factorial Nat.descFactorial
 
 @[simp]
 theorem descFactorial_zero (n : ℕ) : n.descFactorial 0 = 1 :=
   rfl
-#align nat.descFactorial_zero Nat.descFactorial_zero
+#align nat.desc_factorial_zero Nat.descFactorial_zero
 
 @[simp]
 theorem descFactorial_succ (n k : ℕ) : n.descFactorial k.succ = (n - k) * n.descFactorial k :=
   rfl
-#align nat.descFactorial_succ Nat.descFactorial_succ
+#align nat.desc_factorial_succ Nat.descFactorial_succ
 
 theorem zero_descFactorial_succ (k : ℕ) : (0 : ℕ).descFactorial k.succ = 0 := by
   rw [descFactorial_succ, zero_tsub, zero_mul]
-#align nat.zero_descFactorial_succ Nat.zero_descFactorial_succ
+#align nat.zero_desc_factorial_succ Nat.zero_descFactorial_succ
 
 /- Porting note: simp removed because this can be proved by
 simp only [Nat.descFactorial_succ, nonpos_iff_eq_zero, tsub_zero, Nat.descFactorial_zero, mul_one]
@@ -361,7 +361,7 @@ simp only [Nat.descFactorial_succ, nonpos_iff_eq_zero, tsub_zero, Nat.descFactor
 -- @[simp]
 theorem descFactorial_one (n : ℕ) : n.descFactorial 1 = n := by
   rw [descFactorial_succ, descFactorial_zero, mul_one, tsub_zero]
-#align nat.descFactorial_one Nat.descFactorial_one
+#align nat.desc_factorial_one Nat.descFactorial_one
 
 /- Porting note: simp removed because the lhs simplifies,
 according to the linter:
@@ -379,19 +379,19 @@ theorem succ_descFactorial_succ (n : ℕ) :
   | succ k => by
     rw [descFactorial_succ, succ_descFactorial_succ _ k, descFactorial_succ, succ_sub_succ,
       mul_left_comm]
-#align nat.succ_descFactorial_succ Nat.succ_descFactorial_succ
+#align nat.succ_desc_factorial_succ Nat.succ_descFactorial_succ
 
 theorem succ_descFactorial (n : ℕ) :
     ∀ k, (n + 1 - k) * (n + 1).descFactorial k = (n + 1) * n.descFactorial k
   | 0 => by rw [tsub_zero, descFactorial_zero, descFactorial_zero]
   | k + 1 => by
     rw [descFactorial, succ_descFactorial _ k, descFactorial_succ, succ_sub_succ, mul_left_comm]
-#align nat.succ_descFactorial Nat.succ_descFactorial
+#align nat.succ_desc_factorial Nat.succ_descFactorial
 
 theorem descFactorial_self : ∀ n : ℕ, n.descFactorial n = n !
   | 0 => by rw [descFactorial_zero, factorial_zero]
   | succ n => by rw [succ_descFactorial_succ, descFactorial_self n, factorial_succ]
-#align nat.descFactorial_self Nat.descFactorial_self
+#align nat.desc_factorial_self Nat.descFactorial_self
 
 @[simp]
 theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial k = 0 ↔ n < k
@@ -400,7 +400,7 @@ theorem descFactorial_eq_zero_iff_lt {n : ℕ} : ∀ {k : ℕ}, n.descFactorial
     rw [descFactorial_succ, mul_eq_zero, descFactorial_eq_zero_iff_lt, lt_succ_iff,
       tsub_eq_zero_iff_le, lt_iff_le_and_ne, or_iff_left_iff_imp, and_imp]
     exact fun h _ => h
-#align nat.descFactorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt
+#align nat.desc_factorial_eq_zero_iff_lt Nat.descFactorial_eq_zero_iff_lt
 
 alias descFactorial_eq_zero_iff_lt ↔ _ descFactorial_of_lt
 
@@ -410,7 +410,7 @@ theorem add_descFactorial_eq_ascFactorial (n : ℕ) :
   | succ k => by
     rw [Nat.add_succ, Nat.succ_eq_add_one, Nat.succ_eq_add_one,
         succ_descFactorial_succ, ascFactorial_succ, add_descFactorial_eq_ascFactorial _ k]
-#align nat.add_descFactorial_eq_ascFactorial Nat.add_descFactorial_eq_ascFactorial
+#align nat.add_descFactorial_eq_asc_factorial Nat.add_descFactorial_eq_ascFactorial
 
 /-- `n.descFactorial k = n! / (n - k)!` but without ℕ-division. See `Nat.descFactorial_eq_div`
 for the version using ℕ-division. -/
@@ -422,14 +422,14 @@ theorem factorial_mul_descFactorial : ∀ {n k : ℕ}, k ≤ n → (n - k)! * n.
   | succ n, succ k => fun h => by
     rw [succ_descFactorial_succ, succ_sub_succ, ← mul_assoc, mul_comm (n - k)!, mul_assoc,
       factorial_mul_descFactorial (Nat.succ_le_succ_iff.1 h), factorial_succ]
-#align nat.factorial_mul_descFactorial Nat.factorial_mul_descFactorial
+#align nat.factorial_mul_desc_factorial Nat.factorial_mul_descFactorial
 
 /-- Avoid in favor of `Nat.factorial_mul_descFactorial` if you can. ℕ-division isn't worth it. -/
 theorem descFactorial_eq_div {n k : ℕ} (h : k ≤ n) : n.descFactorial k = n ! / (n - k)! := by
   apply mul_left_cancel₀ (factorial_ne_zero (n - k))
   rw [factorial_mul_descFactorial h]
   exact (Nat.mul_div_cancel' <| factorial_dvd_factorial <| Nat.sub_le n k).symm
-#align nat.descFactorial_eq_div Nat.descFactorial_eq_div
+#align nat.desc_factorial_eq_div Nat.descFactorial_eq_div
 
 theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.descFactorial k
   | 0 => by rw [descFactorial_zero, pow_zero]
@@ -438,7 +438,7 @@ theorem pow_sub_le_descFactorial (n : ℕ) : ∀ k : ℕ, (n + 1 - k) ^ k ≤ n.
     apply Nat.mul_le_mul_of_nonneg_left
     exact   (le_trans (Nat.pow_le_pow_of_le_left (tsub_le_tsub_right (le_succ _) _) k)
           (pow_sub_le_descFactorial n k))
-#align nat.pow_sub_le_descFactorial Nat.pow_sub_le_descFactorial
+#align nat.pow_sub_le_desc_factorial Nat.pow_sub_le_descFactorial
 
 theorem pow_sub_lt_descFactorial' {n : ℕ} :
     ∀ {k : ℕ}, k + 2 ≤ n → (n - (k + 1)) ^ (k + 2) < n.descFactorial (k + 2)
@@ -454,7 +454,7 @@ theorem pow_sub_lt_descFactorial' {n : ℕ} :
       rw [succ_sub_succ]
       exact pow_sub_lt_descFactorial' ((le_succ _).trans h)
     · apply tsub_pos_of_lt; apply h
-#align nat.pow_sub_lt_descFactorial' Nat.pow_sub_lt_descFactorial'
+#align nat.pow_sub_lt_desc_factorial' Nat.pow_sub_lt_descFactorial'
 
 theorem pow_sub_lt_descFactorial {n : ℕ} :
     ∀ {k : ℕ}, 2 ≤ k → k ≤ n → (n + 1 - k) ^ k < n.descFactorial k
@@ -463,14 +463,14 @@ theorem pow_sub_lt_descFactorial {n : ℕ} :
   | k + 2 => fun _ h => by
     rw [succ_sub_succ]
     exact pow_sub_lt_descFactorial' h
-#align nat.pow_sub_lt_descFactorial Nat.pow_sub_lt_descFactorial
+#align nat.pow_sub_lt_desc_factorial Nat.pow_sub_lt_descFactorial
 
 theorem descFactorial_le_pow (n : ℕ) : ∀ k : ℕ, n.descFactorial k ≤ n ^ k
   | 0 => by rw [descFactorial_zero, pow_zero]
   | k + 1 => by
     rw [descFactorial_succ, pow_succ, mul_comm _ n]
     exact Nat.mul_le_mul (Nat.sub_le _ _) (descFactorial_le_pow _ k)
-#align nat.descFactorial_le_pow Nat.descFactorial_le_pow
+#align nat.desc_factorial_le_pow Nat.descFactorial_le_pow
 
 theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k → n.descFactorial k < n ^ k
   | 0 => by rintro ⟨⟩
@@ -479,7 +479,7 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
     rw [descFactorial_succ, pow_succ', mul_comm, mul_comm n]
     exact Nat.mul_lt_mul' (descFactorial_le_pow _ _) (tsub_lt_self hn k.zero_lt_succ)
       (pow_pos (Nat.lt_of_succ_le hn) _)
-#align nat.descFactorial_lt_pow Nat.descFactorial_lt_pow
+#align nat.desc_factorial_lt_pow Nat.descFactorial_lt_pow
 
 end DescFactorial

d012cd09

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

@@ -174,16 +174,16 @@ theorem add_factorial_succ_lt_factorial_add_succ {i : ℕ} (n : ℕ) (hi : 2 ≤
         ((add_le_add_iff_right n).mpr ((by decide : 1 ≤ 2).trans hi))))
 #align nat.add_factorial_succ_lt_factorial_add_succ Nat.add_factorial_succ_lt_factorial_add_succ
 
-theorem add_factorial_lt_factorial_add {i n : ℕ} (hi : 2 ≤ i) (hn : 1 ≤ n) : i + n ! < (i + n)! :=
-  by
+theorem add_factorial_lt_factorial_add {i n : ℕ} (hi : 2 ≤ i) (hn : 1 ≤ n) :
+    i + n ! < (i + n)! := by
   cases hn
   · rw [factorial_one]
     exact lt_factorial_self (succ_le_succ hi)
   exact add_factorial_succ_lt_factorial_add_succ _ hi
 #align nat.add_factorial_lt_factorial_add Nat.add_factorial_lt_factorial_add
 
-theorem add_factorial_succ_le_factorial_add_succ (i : ℕ) (n : ℕ) : i + (n + 1)! ≤ (i + (n + 1))! :=
-  by
+theorem add_factorial_succ_le_factorial_add_succ (i : ℕ) (n : ℕ) :
+    i + (n + 1)! ≤ (i + (n + 1))! := by
   cases (le_or_lt (2 : ℕ) i)
   · rw [← add_assoc]
     apply Nat.le_of_lt

d012cd09

chore: bump to 2022-12-22 (#1157)

4b0358a2

Diff

@@ -453,7 +453,7 @@ theorem pow_sub_lt_descFactorial' {n : ℕ} :
     · refine' ((Nat.pow_le_pow_of_le_left (tsub_le_tsub_right (le_succ n) _) _).trans_lt _)
       rw [succ_sub_succ]
       exact pow_sub_lt_descFactorial' ((le_succ _).trans h)
-    · apply tsub_pos_of_lt h
+    · apply tsub_pos_of_lt; apply h
 #align nat.pow_sub_lt_descFactorial' Nat.pow_sub_lt_descFactorial'
 
 theorem pow_sub_lt_descFactorial {n : ℕ} :
@@ -477,8 +477,8 @@ theorem descFactorial_lt_pow {n : ℕ} (hn : 1 ≤ n) : ∀ {k : ℕ}, 2 ≤ k 
   | 1 => by intro; contradiction
   | k + 2 => fun _ => by
     rw [descFactorial_succ, pow_succ', mul_comm, mul_comm n]
-    exact
-      Nat.mul_lt_mul' (descFactorial_le_pow _ _) (tsub_lt_self hn k.zero_lt_succ) (pow_pos hn _)
+    exact Nat.mul_lt_mul' (descFactorial_le_pow _ _) (tsub_lt_self hn k.zero_lt_succ)
+      (pow_pos (Nat.lt_of_succ_le hn) _)
 #align nat.descFactorial_lt_pow Nat.descFactorial_lt_pow
 
 end DescFactorial

d012cd09

chore: tidy various files (#1086)

4e2a7237

Diff

@@ -18,8 +18,8 @@ This file defines the factorial, along with the ascending and descending variant
 
 ## Main declarations
 
-* `nNat.factorial`: The factorial.
-* `at.ascFactorial`: The ascending factorial. Note that it runs from `n + 1` to `n + k`
+* `Nat.factorial`: The factorial.
+* `Nat.ascFactorial`: The ascending factorial. Note that it runs from `n + 1` to `n + k`
   and *not* from `n` to `n + k - 1`. We might want to change that in the future.
 * `Nat.descFactorial`: The descending factorial. It runs from `n - k` to `n`.
 -/
@@ -248,13 +248,12 @@ theorem ascFactorial_succ {n k : ℕ} : n.ascFactorial k.succ = (n + k + 1) * n.
 #align nat.ascFactorial_succ Nat.ascFactorial_succ
 
 -- Porting note: Explicit arguments are required to show that the recursion terminates
--- Porting note: `rw` does not automatically try to apply `rfl` at the end
 theorem succ_ascFactorial (n : ℕ) :
     ∀ k, (n + 1) * n.succ.ascFactorial k = (n + k + 1) * n.ascFactorial k
   | 0 => by rw [add_zero, ascFactorial_zero, ascFactorial_zero]
   | k + 1 => by
     rw [ascFactorial, mul_left_comm, succ_ascFactorial n k, ascFactorial,
-      succ_add, ← add_assoc]; rfl
+      succ_add, ← add_assoc, succ_eq_add_one]
 #align nat.succ_ascFactorial Nat.succ_ascFactorial
 
 /-- `n.ascFactorial k = (n + k)! / n!` but without ℕ-division. See `Nat.ascFactorial_eq_div` for

d012cd09

feat: Port Data.Nat.Factorial.Basic (#1066)

d012cd09

Co-authored-by: ART0 <18333981+0Art0@users.noreply.github.com> Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com>

740c2555

`data.nat.factorial.basic` ⟷ `Mathlib.Data.Nat.Factorial.Basic`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Other changes

Renames

`Algebra.GroupPower.Order`

`Algebra.GroupPower.CovariantClass`

`Data.Nat.Pow`

Lemmas added

Lemmas removed

Other changes

Dependencies 2 + 114

data.nat.factorial.basic ⟷ Mathlib.Data.Nat.Factorial.Basic

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Other changes

Renames

Algebra.GroupPower.Order

Algebra.GroupPower.CovariantClass

Data.Nat.Pow

Lemmas added

Lemmas removed

Other changes

Dependencies 2 + 114

`data.nat.factorial.basic` ⟷ `Mathlib.Data.Nat.Factorial.Basic`

`Algebra.GroupPower.Order`

`Algebra.GroupPower.CovariantClass`

`Data.Nat.Pow`