src/HOL/ex/Fib.ML
changeset 5143 b94cd208f073
parent 5069 3ea049f7979d
child 5537 c2bd39a2c0ee
equal deleted inserted replaced
5142:c56aa8b59dc0 5143:b94cd208f073
    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);