src/HOL/Hyperreal/Series.ML
changeset 14334 6137d24eef79
parent 14331 8dbbb7cf3637
child 14348 744c868ee0b7
equal deleted inserted replaced
14333:14f29eb097a3 14334:6137d24eef79
    28 qed "sumr_add_lbound_zero";
    28 qed "sumr_add_lbound_zero";
    29 Addsimps [sumr_add_lbound_zero];
    29 Addsimps [sumr_add_lbound_zero];
    30 
    30 
    31 Goal "sumr m n f + sumr m n g = sumr m n (%n. f n + g n)";
    31 Goal "sumr m n f + sumr m n g = sumr m n (%n. f n + g n)";
    32 by (induct_tac "n" 1);
    32 by (induct_tac "n" 1);
    33 by (auto_tac (claset(),simpset() addsimps real_add_ac));
    33 by (auto_tac (claset(),simpset() addsimps add_ac));
    34 qed "sumr_add";
    34 qed "sumr_add";
    35 
    35 
    36 Goal "r * sumr m n f = sumr m n (%n. r * f n)";
    36 Goal "r * sumr m n f = sumr m n (%n. r * f n)";
    37 by (induct_tac "n" 1);
    37 by (induct_tac "n" 1);
    38 by (Auto_tac);
    38 by (Auto_tac);
    39 by (auto_tac (claset(),simpset() addsimps 
    39 by (auto_tac (claset(),simpset() addsimps 
    40     [real_add_mult_distrib2]));
    40     [right_distrib]));
    41 qed "sumr_mult";
    41 qed "sumr_mult";
    42 
    42 
    43 Goal "n < p --> sumr 0 n f + sumr n p f = sumr 0 p f";
    43 Goal "n < p --> sumr 0 n f + sumr n p f = sumr 0 p f";
    44 by (induct_tac "p" 1);
    44 by (induct_tac "p" 1);
    45 by (auto_tac (claset() addSDs [CLAIM "n < Suc na ==> n <= na",
    45 by (auto_tac (claset() addSDs [CLAIM "n < Suc na ==> n <= na",
    47 qed_spec_mp "sumr_split_add";
    47 qed_spec_mp "sumr_split_add";
    48 
    48 
    49 Goal "n < p ==> sumr 0 p f + \
    49 Goal "n < p ==> sumr 0 p f + \
    50 \                - sumr 0 n f = sumr n p f";
    50 \                - sumr 0 n f = sumr n p f";
    51 by (dres_inst_tac [("f1","f")] (sumr_split_add RS sym) 1);
    51 by (dres_inst_tac [("f1","f")] (sumr_split_add RS sym) 1);
    52 by (asm_simp_tac (simpset() addsimps real_add_ac) 1);
    52 by (asm_simp_tac (simpset() addsimps add_ac) 1);
    53 qed "sumr_split_add_minus";
    53 qed "sumr_split_add_minus";
    54 
    54 
    55 Goal "0 < n --> n < p --> sumr (Suc 0) n f + sumr n p f = sumr (Suc 0) p f";
    55 Goal "0 < n --> n < p --> sumr (Suc 0) n f + sumr n p f = sumr (Suc 0) p f";
    56 by (induct_tac "p" 1);
    56 by (induct_tac "p" 1);
    57 by (auto_tac (claset() addSDs [CLAIM "[| m < Suc n; n <= m |] ==> m = n"],
    57 by (auto_tac (claset() addSDs [CLAIM "[| m < Suc n; n <= m |] ==> m = n"],
    64 qed "sumr_split_add3";
    64 qed "sumr_split_add3";
    65 
    65 
    66 Goal "abs(sumr m n f) <= sumr m n (%i. abs(f i))";
    66 Goal "abs(sumr m n f) <= sumr m n (%i. abs(f i))";
    67 by (induct_tac "n" 1);
    67 by (induct_tac "n" 1);
    68 by (auto_tac (claset() addIs [abs_triangle_ineq RS order_trans,
    68 by (auto_tac (claset() addIs [abs_triangle_ineq RS order_trans,
    69                               real_add_le_mono1], 
    69                               add_right_mono], 
    70               simpset()));
    70               simpset()));
    71 qed "sumr_rabs";
    71 qed "sumr_rabs";
    72 
    72 
    73 Goal "!!f g. (ALL r. m <= r & r < n --> f r = g r) \
    73 Goal "!!f g. (ALL r. m <= r & r < n --> f r = g r) \
    74 \                --> sumr m n f = sumr m n g";
    74 \                --> sumr m n f = sumr m n g";
    77 qed_spec_mp "sumr_fun_eq";
    77 qed_spec_mp "sumr_fun_eq";
    78 
    78 
    79 Goal "sumr 0 n (%i. r) = real n * r";
    79 Goal "sumr 0 n (%i. r) = real n * r";
    80 by (induct_tac "n" 1);
    80 by (induct_tac "n" 1);
    81 by (auto_tac (claset(),
    81 by (auto_tac (claset(),
    82               simpset() addsimps [real_add_mult_distrib,real_of_nat_zero,
    82               simpset() addsimps [left_distrib,real_of_nat_zero,
    83                                   real_of_nat_Suc]));
    83                                   real_of_nat_Suc]));
    84 qed "sumr_const";
    84 qed "sumr_const";
    85 Addsimps [sumr_const];
    85 Addsimps [sumr_const];
    86 
    86 
    87 Goal "sumr 0 n f + -(real n * r) = sumr 0 n (%i. f i + -r)";
    87 Goal "sumr 0 n f + -(real n * r) = sumr 0 n (%i. f i + -r)";
    88 by (full_simp_tac (HOL_ss addsimps [sumr_add RS sym, real_minus_mult_eq2]) 1);
    88 by (full_simp_tac (HOL_ss addsimps [sumr_add RS sym, minus_mult_right]) 1);
    89 by (Simp_tac 1);
    89 by (Simp_tac 1);
    90 qed "sumr_add_mult_const";
    90 qed "sumr_add_mult_const";
    91 
    91 
    92 Goalw [real_diff_def] 
    92 Goalw [real_diff_def] 
    93      "sumr 0 n f - (real n*r) = sumr 0 n (%i. f i - r)";
    93      "sumr 0 n f - (real n*r) = sumr 0 n (%i. f i - r)";
   101 Addsimps [sumr_less_bounds_zero];
   101 Addsimps [sumr_less_bounds_zero];
   102 
   102 
   103 Goal "sumr m n (%i. - f i) = - sumr m n f";
   103 Goal "sumr m n (%i. - f i) = - sumr m n f";
   104 by (induct_tac "n" 1);
   104 by (induct_tac "n" 1);
   105 by (case_tac "Suc n <= m" 2);
   105 by (case_tac "Suc n <= m" 2);
   106 by (auto_tac (claset(),simpset() addsimps 
   106 by (auto_tac (claset(),simpset() addsimps [minus_add_distrib]));
   107     [real_minus_add_distrib]));
       
   108 qed "sumr_minus";
   107 qed "sumr_minus";
   109 
   108 
   110 Goal "sumr (m+k) (n+k) f = sumr m n (%i. f(i + k))";
   109 Goal "sumr (m+k) (n+k) f = sumr m n (%i. f(i + k))";
   111 by (induct_tac "n" 1);
   110 by (induct_tac "n" 1);
   112 by (Auto_tac);
   111 by (Auto_tac);
   129 by (Step_tac 1);
   128 by (Step_tac 1);
   130 by (asm_full_simp_tac (simpset() addsimps [le_Suc_eq])  2);
   129 by (asm_full_simp_tac (simpset() addsimps [le_Suc_eq])  2);
   131 by (Step_tac 1);
   130 by (Step_tac 1);
   132 by (dres_inst_tac [("x","n")] spec 3);
   131 by (dres_inst_tac [("x","n")] spec 3);
   133 by (auto_tac (claset() addSDs [le_imp_less_or_eq], simpset()));
   132 by (auto_tac (claset() addSDs [le_imp_less_or_eq], simpset()));
   134 by (asm_simp_tac (simpset() addsimps [real_add_mult_distrib, Suc_diff_n,
   133 by (asm_simp_tac (simpset() addsimps [left_distrib, Suc_diff_n,
   135                                       real_of_nat_Suc]) 1);
   134                                       real_of_nat_Suc]) 1);
   136 qed_spec_mp "sumr_interval_const";
   135 qed_spec_mp "sumr_interval_const";
   137 
   136 
   138 Goal "(ALL n. m <= n --> f n = r) & m <= na \
   137 Goal "(ALL n. m <= n --> f n = r) & m <= na \
   139 \     --> sumr m na f = (real (na - m) * r)";
   138 \     --> sumr m na f = (real (na - m) * r)";
   142 by (asm_full_simp_tac (simpset() addsimps [le_Suc_eq])  2);
   141 by (asm_full_simp_tac (simpset() addsimps [le_Suc_eq])  2);
   143 by (Step_tac 1);
   142 by (Step_tac 1);
   144 by (dres_inst_tac [("x","n")] spec 3);
   143 by (dres_inst_tac [("x","n")] spec 3);
   145 by (auto_tac (claset() addSDs [le_imp_less_or_eq],
   144 by (auto_tac (claset() addSDs [le_imp_less_or_eq],
   146     simpset()));
   145     simpset()));
   147 by (asm_simp_tac (simpset() addsimps [Suc_diff_n, real_add_mult_distrib,
   146 by (asm_simp_tac (simpset() addsimps [Suc_diff_n, left_distrib,
   148                                       real_of_nat_Suc]) 1);
   147                                       real_of_nat_Suc]) 1);
   149 qed_spec_mp "sumr_interval_const2";
   148 qed_spec_mp "sumr_interval_const2";
   150 
   149 
   151 Goal "(ALL n. m <= n --> 0 <= f n) & m < k --> sumr 0 m f <= sumr 0 k f";
   150 Goal "(ALL n. m <= n --> 0 <= f n) & m < k --> sumr 0 m f <= sumr 0 k f";
   152 by (induct_tac "k" 1);
   151 by (induct_tac "k" 1);
   153 by (Step_tac 1);
   152 by (Step_tac 1);
   154 by (ALLGOALS(asm_full_simp_tac (simpset() addsimps [less_Suc_eq_le])));
   153 by (ALLGOALS(asm_full_simp_tac (simpset() addsimps [less_Suc_eq_le])));
   155 by (ALLGOALS(dres_inst_tac [("x","n")] spec));
   154 by (ALLGOALS(dres_inst_tac [("x","n")] spec));
   156 by (Step_tac 1);
   155 by (Step_tac 1);
   157 by (dtac le_imp_less_or_eq 1 THEN Step_tac 1);
   156 by (dtac le_imp_less_or_eq 1 THEN Step_tac 1);
   158 by (dtac real_add_le_mono 2);
   157 by (dres_inst_tac [("a","sumr 0 m f")] add_mono 2);
   159 by (dres_inst_tac [("i","sumr 0 m f")] (order_refl RS real_add_le_mono) 1);
   158 by (dres_inst_tac [("a","sumr 0 m f")] (order_refl RS add_mono) 1);
   160 by (Auto_tac);
   159 by (Auto_tac);
   161 qed_spec_mp "sumr_le";
   160 qed_spec_mp "sumr_le";
   162 
   161 
   163 Goal "!!f g. (ALL r. m <= r & r < n --> f r <= g r) \
   162 Goal "!!f g. (ALL r. m <= r & r < n --> f r <= g r) \
   164 \                --> sumr m n f <= sumr m n g";
   163 \                --> sumr m n f <= sumr m n g";
   165 by (induct_tac "n" 1);
   164 by (induct_tac "n" 1);
   166 by (auto_tac (claset() addIs [real_add_le_mono],
   165 by (auto_tac (claset() addIs [add_mono],
   167     simpset() addsimps [le_def]));
   166     simpset() addsimps [le_def]));
   168 qed_spec_mp "sumr_le2";
   167 qed_spec_mp "sumr_le2";
   169 
   168 
   170 Goal "(ALL n. 0 <= f n) --> 0 <= sumr m n f";
   169 Goal "(ALL n. 0 <= f n) --> 0 <= sumr m n f";
   171 by (induct_tac "n" 1);
   170 by (induct_tac "n" 1);
   226 qed_spec_mp "sumr_subst";
   225 qed_spec_mp "sumr_subst";
   227 
   226 
   228 Goal "(ALL p. m <= p & p < m + n --> (f(p) <= K)) \
   227 Goal "(ALL p. m <= p & p < m + n --> (f(p) <= K)) \
   229 \     --> (sumr m (m + n) f <= (real n * K))";
   228 \     --> (sumr m (m + n) f <= (real n * K))";
   230 by (induct_tac "n" 1);
   229 by (induct_tac "n" 1);
   231 by (auto_tac (claset() addIs [real_add_le_mono],
   230 by (auto_tac (claset() addIs [add_mono],
   232               simpset() addsimps [real_add_mult_distrib, real_of_nat_Suc]));
   231               simpset() addsimps [left_distrib, real_of_nat_Suc]));
   233 qed_spec_mp "sumr_bound";
   232 qed_spec_mp "sumr_bound";
   234 
   233 
   235 Goal "(ALL p. 0 <= p & p < n --> (f(p) <= K)) \
   234 Goal "(ALL p. 0 <= p & p < n --> (f(p) <= K)) \
   236 \     --> (sumr 0 n f <= (real n * K))";
   235 \     --> (sumr 0 n f <= (real n * K))";
   237 by (induct_tac "n" 1);
   236 by (induct_tac "n" 1);
   238 by (auto_tac (claset() addIs [real_add_le_mono],
   237 by (auto_tac (claset() addIs [add_mono],
   239         simpset() addsimps [real_add_mult_distrib, real_of_nat_Suc]));
   238         simpset() addsimps [left_distrib, real_of_nat_Suc]));
   240 qed_spec_mp "sumr_bound2";
   239 qed_spec_mp "sumr_bound2";
   241 
   240 
   242 Goal "sumr 0 n (%m. sumr (m * k) (m*k + k) f) = sumr 0 (n * k) f";
   241 Goal "sumr 0 n (%m. sumr (m * k) (m*k + k) f) = sumr 0 (n * k) f";
   243 by (subgoal_tac "k = 0 | 0 < k" 1);
   242 by (subgoal_tac "k = 0 | 0 < k" 1);
   244 by (Auto_tac);
   243 by (Auto_tac);
   356 \     ==> sumr 0 n f < suminf f";
   355 \     ==> sumr 0 n f < suminf f";
   357 by (dtac summable_sums 1);
   356 by (dtac summable_sums 1);
   358 by (auto_tac (claset(),simpset() addsimps [sums_def,LIMSEQ_def]));
   357 by (auto_tac (claset(),simpset() addsimps [sums_def,LIMSEQ_def]));
   359 by (dres_inst_tac [("x","f(n) + f(n + 1)")] spec 1);
   358 by (dres_inst_tac [("x","f(n) + f(n + 1)")] spec 1);
   360 by (Auto_tac);
   359 by (Auto_tac);
   361 by (rtac ccontr 2 THEN dtac real_leI 2);
   360 by (rtac ccontr 2 THEN dtac (linorder_not_less RS iffD1) 2);
   362 by (subgoal_tac "sumr 0 (n + Suc (Suc 0)) f <= sumr 0 (Suc (Suc 0) * (Suc no) + n) f" 2);
   361 by (subgoal_tac "sumr 0 (n + Suc (Suc 0)) f <= sumr 0 (Suc (Suc 0) * (Suc no) + n) f" 2);
   363 by (induct_tac "no" 3 THEN Simp_tac 3);
   362 by (induct_tac "no" 3 THEN Simp_tac 3);
   364 by (res_inst_tac [("y","sumr 0 (Suc (Suc 0)*(Suc na)+n) f")] order_trans 3);
   363 by (res_inst_tac [("y","sumr 0 (Suc (Suc 0)*(Suc na)+n) f")] order_trans 3);
   365 by (assume_tac 3);
   364 by (assume_tac 3);
   366 by (dres_inst_tac [("x","Suc na")] spec 3);
   365 by (dres_inst_tac [("x","Suc na")] spec 3);
   417 Goal "x ~= 1 ==> sumr 0 n (%n. x ^ n) = (x ^ n - 1) / (x - 1)";
   416 Goal "x ~= 1 ==> sumr 0 n (%n. x ^ n) = (x ^ n - 1) / (x - 1)";
   418 by (induct_tac "n" 1);
   417 by (induct_tac "n" 1);
   419 by (Auto_tac);
   418 by (Auto_tac);
   420 by (res_inst_tac [("c1","x - 1")] (real_mult_right_cancel RS iffD1) 1);
   419 by (res_inst_tac [("c1","x - 1")] (real_mult_right_cancel RS iffD1) 1);
   421 by (auto_tac (claset(),
   420 by (auto_tac (claset(),
   422        simpset() addsimps [real_mult_assoc, real_add_mult_distrib]));
   421        simpset() addsimps [real_mult_assoc, left_distrib]));
   423 by (auto_tac (claset(),
   422 by (auto_tac (claset(),
   424        simpset() addsimps [real_add_mult_distrib2,
   423        simpset() addsimps [right_distrib,
   425                            real_diff_def, real_mult_commute]));
   424                            real_diff_def, real_mult_commute]));
   426 qed "sumr_geometric";
   425 qed "sumr_geometric";
   427 
   426 
   428 Goal "abs(x) < 1 ==> (%n. x ^ n) sums (1/(1 - x))";
   427 Goal "abs(x) < 1 ==> (%n. x ^ n) sums (1/(1 - x))";
   429 by (case_tac "x = 1" 1);
   428 by (case_tac "x = 1" 1);
   430 by (auto_tac (claset() addSDs [LIMSEQ_rabs_realpow_zero2],
   429 by (auto_tac (claset() addSDs [LIMSEQ_rabs_realpow_zero2],
   431              simpset() addsimps [sumr_geometric ,sums_def,
   430              simpset() addsimps [sumr_geometric ,sums_def,
   432                                  real_diff_def, real_add_divide_distrib]));
   431                                  real_diff_def, add_divide_distrib]));
   433 by (subgoal_tac "1 / (1 + -x) = 0/(x - 1) + - 1/(x - 1)" 1); 
   432 by (subgoal_tac "1 / (1 + -x) = 0/(x - 1) + - 1/(x - 1)" 1); 
   434 by (asm_full_simp_tac (simpset() addsimps [thm"minus_divide_right"]) 2); 
   433 by (asm_full_simp_tac (simpset() addsimps [thm"minus_divide_right"]) 2); 
   435 by (etac ssubst 1); 
   434 by (etac ssubst 1); 
   436 by (rtac LIMSEQ_add 1 THEN rtac LIMSEQ_divide 1);
   435 by (rtac LIMSEQ_add 1 THEN rtac LIMSEQ_divide 1);
   437 by (auto_tac (claset() addIs [LIMSEQ_const], 
   436 by (auto_tac (claset() addIs [LIMSEQ_const], 
   540 Goal "[| c <= 0; abs x <= c * abs y |] ==> x = (0::real)";
   539 Goal "[| c <= 0; abs x <= c * abs y |] ==> x = (0::real)";
   541 by (dtac order_le_imp_less_or_eq 1);
   540 by (dtac order_le_imp_less_or_eq 1);
   542 by Auto_tac;  
   541 by Auto_tac;  
   543 by (subgoal_tac "0 <= c * abs y" 1);
   542 by (subgoal_tac "0 <= c * abs y" 1);
   544 by (arith_tac 2);
   543 by (arith_tac 2);
   545 by (asm_full_simp_tac (simpset() addsimps [real_0_le_mult_iff]) 1); 
   544 by (asm_full_simp_tac (simpset() addsimps [zero_le_mult_iff]) 1); 
   546 qed "rabs_ratiotest_lemma";
   545 qed "rabs_ratiotest_lemma";
   547 
   546 
   548 (* lemmas *)
   547 (* lemmas *)
   549 
   548 
   550 Goal "(k::nat) <= l ==> (EX n. l = k + n)";
   549 Goal "(k::nat) <= l ==> (EX n. l = k + n)";
   577 by (res_inst_tac [("x","N")] exI 1 THEN Step_tac 1);
   576 by (res_inst_tac [("x","N")] exI 1 THEN Step_tac 1);
   578 by (dtac (le_Suc_ex_iff RS iffD1) 1);
   577 by (dtac (le_Suc_ex_iff RS iffD1) 1);
   579 by (auto_tac (claset(),simpset() addsimps [realpow_add, realpow_not_zero]));
   578 by (auto_tac (claset(),simpset() addsimps [realpow_add, realpow_not_zero]));
   580 by (induct_tac "na" 1 THEN Auto_tac);
   579 by (induct_tac "na" 1 THEN Auto_tac);
   581 by (res_inst_tac [("y","c*abs(f(N + n))")] order_trans 1);
   580 by (res_inst_tac [("y","c*abs(f(N + n))")] order_trans 1);
   582 by (auto_tac (claset() addIs [real_mult_le_mono1],
   581 by (auto_tac (claset() addIs [mult_right_mono],
   583               simpset() addsimps [summable_def]));
   582               simpset() addsimps [summable_def]));
   584 by (asm_full_simp_tac (simpset() addsimps real_mult_ac) 1);
   583 by (asm_full_simp_tac (simpset() addsimps mult_ac) 1);
   585 by (res_inst_tac [("x","abs(f N) * (1/(1 - c)) / (c ^ N)")] exI 1);
   584 by (res_inst_tac [("x","abs(f N) * (1/(1 - c)) / (c ^ N)")] exI 1);
   586 by (rtac sums_divide 1); 
   585 by (rtac sums_divide 1); 
   587 by (rtac sums_mult 1); 
   586 by (rtac sums_mult 1); 
   588 by (auto_tac (claset() addSIs [sums_mult,geometric_sums], 
   587 by (auto_tac (claset() addSIs [sums_mult,geometric_sums], 
   589               simpset() addsimps [real_abs_def]));
   588               simpset() addsimps [real_abs_def]));