43 qed "fib_Suc_neq_0"; |
43 qed "fib_Suc_neq_0"; |
44 |
44 |
45 (* Also add 0 < fib (Suc n) *) |
45 (* Also add 0 < fib (Suc n) *) |
46 Addsimps [fib_Suc_neq_0, [neq0_conv, fib_Suc_neq_0] MRS iffD1]; |
46 Addsimps [fib_Suc_neq_0, [neq0_conv, fib_Suc_neq_0] MRS iffD1]; |
47 |
47 |
48 Goal "!!n. 0<n ==> 0 < fib n"; |
48 Goal "0<n ==> 0 < fib n"; |
49 by (rtac (not0_implies_Suc RS exE) 1); |
49 by (rtac (not0_implies_Suc RS exE) 1); |
50 by Auto_tac; |
50 by Auto_tac; |
51 qed "fib_gr_0"; |
51 qed "fib_gr_0"; |
52 |
52 |
53 |
53 |
91 by (asm_simp_tac (simpset() addsimps [add_commute, gcd_non_0]) 1); |
91 by (asm_simp_tac (simpset() addsimps [add_commute, gcd_non_0]) 1); |
92 by (asm_simp_tac (simpset() addsimps [gcd_non_0 RS sym]) 1); |
92 by (asm_simp_tac (simpset() addsimps [gcd_non_0 RS sym]) 1); |
93 by (asm_simp_tac (simpset() addsimps [gcd_fib_Suc_eq_1, gcd_mult_cancel]) 1); |
93 by (asm_simp_tac (simpset() addsimps [gcd_fib_Suc_eq_1, gcd_mult_cancel]) 1); |
94 qed "gcd_fib_add"; |
94 qed "gcd_fib_add"; |
95 |
95 |
96 Goal "!!m. m <= n ==> gcd(fib m, fib (n-m)) = gcd(fib m, fib n)"; |
96 Goal "m <= n ==> gcd(fib m, fib (n-m)) = gcd(fib m, fib n)"; |
97 by (rtac (gcd_fib_add RS sym RS trans) 1); |
97 by (rtac (gcd_fib_add RS sym RS trans) 1); |
98 by (Asm_simp_tac 1); |
98 by (Asm_simp_tac 1); |
99 qed "gcd_fib_diff"; |
99 qed "gcd_fib_diff"; |
100 |
100 |
101 Goal "!!m. 0<m ==> gcd (fib m, fib (n mod m)) = gcd (fib m, fib n)"; |
101 Goal "0<m ==> gcd (fib m, fib (n mod m)) = gcd (fib m, fib n)"; |
102 by (res_inst_tac [("n","n")] less_induct 1); |
102 by (res_inst_tac [("n","n")] less_induct 1); |
103 by (stac mod_if 1); |
103 by (stac mod_if 1); |
104 by (Asm_simp_tac 1); |
104 by (Asm_simp_tac 1); |
105 by (asm_simp_tac (simpset() addsimps [gcd_fib_diff, mod_less, mod_geq, |
105 by (asm_simp_tac (simpset() addsimps [gcd_fib_diff, mod_less, mod_geq, |
106 not_less_iff_le, diff_less]) 1); |
106 not_less_iff_le, diff_less]) 1); |