]> matita.cs.unibo.it Git - helm.git/blob - helm/matita/library/nat/factorial.ma
fix
[helm.git] / 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 interpretation "factorial" 'fact n = (cic:/matita/nat/factorial/fact.con n).
25
26 theorem le_SO_fact : \forall n. (S O) \le n!.
27 intro.elim n.simplify.apply le_n.
28 change with ((S O) \le (S n1)*n1!).
29 apply (trans_le ? ((S n1)*(S O))).simplify.
30 apply le_S_S.apply le_O_n.
31 apply le_times_r.assumption.
32 qed.
33
34 theorem le_SSO_fact : \forall n. (S O) < n \to (S(S O)) \le n!.
35 intro.apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S O) H).
36 intros.change with ((S (S O)) \le (S m)*m!).
37 apply (trans_le ? ((S(S O))*(S O))).apply le_n.
38 apply le_times.exact H.apply le_SO_fact.
39 qed.
40
41 theorem le_n_fact_n: \forall n. n \le n!.
42 intro. elim n.apply le_O_n.
43 change with (S n1 \le (S n1)*n1!).
44 apply (trans_le ? ((S n1)*(S O))).
45 rewrite < times_n_SO.apply le_n.
46 apply le_times.apply le_n.
47 apply le_SO_fact.
48 qed.
49
50 theorem lt_n_fact_n: \forall n. (S(S O)) < n \to n < n!.
51 intro.apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S(S O)) H).
52 intros.change with ((S m) < (S m)*m!).
53 apply (lt_to_le_to_lt ? ((S m)*(S (S O)))).
54 rewrite < sym_times.
55 simplify.unfold lt.
56 apply le_S_S.rewrite < plus_n_O.
57 apply le_plus_n.
58 apply le_times_r.apply le_SSO_fact.
59 simplify.unfold lt.apply le_S_S_to_le.exact H.
60 qed.
61