helm/matita/library/nat/factorial.ma

   1 (**************************************************************************)
   2 (*       ___                                                                *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
   8 (*      ||A||       E.Tassi, S.Zacchiroli                                 *)
   9 (*      \   /                                                             *)
  10 (*       \ /        Matita is distributed under the terms of the          *)
  11 (*        v         GNU Lesser General Public License Version 2.1         *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 set "baseuri" "cic:/matita/nat/factorial".
  16
  17 include "nat/le_arith.ma".
  18
  19 let rec fact n \def
  20   match n with
  21   [ O \Rightarrow (S O)
  22   | (S m) \Rightarrow (S m)*(fact m)].
  23
  24 theorem le_SO_fact : \forall n. (S O) \le (fact n).
  25 intro.elim n.simplify.apply le_n.
  26 change with (S O) \le (S n1)*(fact n1).
  27 apply trans_le ? ((S n1)*(S O)).simplify.
  28 apply le_S_S.apply le_O_n.
  29 apply le_times_r.assumption.
  30 qed.
  31
  32 theorem le_SSO_fact : \forall n. (S O) < n \to (S(S O)) \le (fact n).
  33 intro.apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
  34 intros.change with (S (S O)) \le (S m)*(fact m).
  35 apply trans_le ? ((S(S O))*(S O)).apply le_n.
  36 apply le_times.exact H.apply le_SO_fact.
  37 qed.
  38
  39 theorem le_n_fact_n: \forall n. n \le (fact n).
  40 intro. elim n.apply le_O_n.
  41 change with S n1 \le (S n1)*(fact n1).
  42 apply trans_le ? ((S n1)*(S O)).
  43 rewrite < times_n_SO.apply le_n.
  44 apply le_times.apply le_n.
  45 apply le_SO_fact.
  46 qed.
  47
  48 theorem lt_n_fact_n: \forall n. (S(S O)) < n \to n < (fact n).
  49 intro.apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S(S O)) H.
  50 intros.change with (S m) < (S m)*(fact m).
  51 apply lt_to_le_to_lt ? ((S m)*(S (S O))).
  52 rewrite < sym_times.
  53 simplify.
  54 apply le_S_S.rewrite < plus_n_O.
  55 apply le_plus_n.
  56 apply le_times_r.apply le_SSO_fact.
  57 simplify.apply le_S_S_to_le.exact H.
  58 qed.
  59