Documentation

Mathlib.Data.Nat.Factorial.Basic

Factorial and variants #

This file defines the factorial, along with the ascending and descending variants.

Main declarations #

Nat.factorial n is the factorial of n.

Equations
theorem Nat.mul_factorial_pred {n : } (hn : 0 < n) :
theorem Nat.dvd_factorial {m : } {n : } :
0 < mm nm Nat.factorial n
theorem Nat.factorial_lt {m : } {n : } (hn : 0 < n) :
theorem Nat.lt_factorial_self {n : } (hi : 3 n) :
theorem Nat.add_factorial_lt_factorial_add {i : } {n : } (hi : 2 i) (hn : 1 n) :

Ascending and descending factorials #

def Nat.ascFactorial (n : ) :

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.

Equations
theorem Nat.succ_ascFactorial (n : ) (k : ) :
(n + 1) * Nat.ascFactorial (Nat.succ n) k = (n + k + 1) * Nat.ascFactorial n k

n.ascFactorial k = (n + k)! / n! but without ℕ-division. See Nat.ascFactorial_eq_div for the version with ℕ-division.

Avoid in favor of Nat.factorial_mul_ascFactorial if you can. ℕ-division isn't worth it.

theorem Nat.ascFactorial_of_sub {n : } {k : } (h : k < n) :
(n - k) * Nat.ascFactorial (n - k) k = Nat.ascFactorial (n - (k + 1)) (k + 1)
theorem Nat.pow_lt_ascFactorial' (n : ) (k : ) :
(n + 1) ^ (k + 2) < Nat.ascFactorial n (k + 2)
theorem Nat.pow_lt_ascFactorial (n : ) {k : } :
2 k(n + 1) ^ k < Nat.ascFactorial n k
theorem Nat.ascFactorial_lt_pow_add (n : ) {k : } :
2 kNat.ascFactorial n k < (n + k) ^ k
def Nat.descFactorial (n : ) :

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.

Equations
theorem Nat.succ_descFactorial (n : ) (k : ) :
(n + 1 - k) * Nat.descFactorial (n + 1) k = (n + 1) * Nat.descFactorial n k
theorem Nat.descFactorial_of_lt {n : } {k : } :
n < kNat.descFactorial n k = 0

Alias of the reverse direction of Nat.descFactorial_eq_zero_iff_lt.

n.descFactorial k = n! / (n - k)! but without ℕ-division. See Nat.descFactorial_eq_div for the version using ℕ-division.

Avoid in favor of Nat.factorial_mul_descFactorial if you can. ℕ-division isn't worth it.

theorem Nat.pow_sub_lt_descFactorial' {n : } {k : } :
k + 2 n(n - (k + 1)) ^ (k + 2) < Nat.descFactorial n (k + 2)
theorem Nat.pow_sub_lt_descFactorial {n : } {k : } :
2 kk n(n + 1 - k) ^ k < Nat.descFactorial n k
theorem Nat.descFactorial_lt_pow {n : } (hn : 1 n) {k : } :
2 kNat.descFactorial n k < n ^ k