| 1 |
(* ========================================================================== *) |
| 2 |
(* Formal verification of nonlinear inequalities in HOL Light *) |
| 3 |
(* *) |
| 4 |
(* Copyright (c) 2014 Alexey Solovyev *) |
| 5 |
(* *) |
| 6 |
(* This file is distributed under the terms of the MIT licence *) |
| 7 |
(* ========================================================================== *) |
| 8 |
|
| 9 |
(* -------------------------------------------------------------------------- *) |
| 10 |
(* Formal power series *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Multivariate/realanalysis.ml";; |
| 14 |
|
| 15 |
module Series = struct |
| 16 |
|
| 17 |
prioritize_real();; |
| 18 |
|
| 19 |
let abs_neg_pow = prove |
| 20 |
(`!x n. abs (--x pow n) = abs x pow n`, |
| 21 |
REWRITE_TAC[REAL_ABS_POW; REAL_ABS_NEG]);; |
| 22 |
|
| 23 |
let abs_neg_one_pow = prove |
| 24 |
(`!n. abs (-- &1 pow n) = &1`, |
| 25 |
REWRITE_TAC[abs_neg_pow; REAL_ARITH `abs (&1) = &1`; REAL_POW_ONE]);; |
| 26 |
|
| 27 |
let real_infsum_offset = prove |
| 28 |
(`!m k f. real_summable (from m) f /\ m <= k |
| 29 |
==> real_infsum (from m) f = sum (m..k) f + real_infsum (from (k + 1)) f`, |
| 30 |
REPEAT STRIP_TAC THEN |
| 31 |
FIRST_ASSUM (MP_TAC o SPEC `k + 1` o MATCH_MP REAL_SUMMABLE_FROM_ELSEWHERE) THEN |
| 32 |
UNDISCH_TAC `real_summable (from m) f` THEN |
| 33 |
REWRITE_TAC[real_summable] THEN REPEAT STRIP_TAC THEN |
| 34 |
ASM_SIMP_TAC[REAL_INFSUM_UNIQUE] THEN |
| 35 |
MP_TAC (SPECL[`f:num->real`; `l:real`; `m:num`; `k + 1`] REAL_SUMS_OFFSET) THEN |
| 36 |
ASM_REWRITE_TAC[ARITH_RULE `m < k + 1 <=> m <= k`; ARITH_RULE `(k + 1) - 1 = k`] THEN |
| 37 |
DISCH_THEN (MP_TAC o MATCH_MP REAL_INFSUM_UNIQUE) THEN |
| 38 |
REAL_ARITH_TAC);; |
| 39 |
|
| 40 |
let real_infsum_offset_alt = prove |
| 41 |
(`!m k f. real_summable (from m) f /\ m < k |
| 42 |
==> real_infsum (from m) f = sum (m..k - 1) f + real_infsum (from k) f`, |
| 43 |
REPEAT STRIP_TAC THEN |
| 44 |
SUBGOAL_THEN `?t. k = t + 1 /\ m <= t` STRIP_ASSUME_TAC THENL [ |
| 45 |
EXISTS_TAC `k - 1` THEN ASM_ARITH_TAC; |
| 46 |
ALL_TAC |
| 47 |
] THEN |
| 48 |
ASM_REWRITE_TAC[ARITH_RULE `(t + 1) - 1 = t`] THEN |
| 49 |
MATCH_MP_TAC real_infsum_offset THEN ASM_REWRITE_TAC[]);; |
| 50 |
|
| 51 |
let power_series_simple_bound = prove |
| 52 |
(`!a u x m. real_summable (from m) (\i. a i * x pow i) |
| 53 |
/\ (!i. m <= i ==> abs (a i) <= u) |
| 54 |
/\ abs x < &1 |
| 55 |
==> abs (real_infsum (from m) (\i. a i * x pow i)) |
| 56 |
<= u * abs x pow m / (&1 - abs x)`, |
| 57 |
REPEAT STRIP_TAC THEN |
| 58 |
MATCH_MP_TAC REAL_SERIES_BOUND THEN |
| 59 |
MAP_EVERY EXISTS_TAC [`\i. a i * x pow i`; `\i. u * abs x pow i`; `from m`] THEN |
| 60 |
REPEAT STRIP_TAC THENL [ |
| 61 |
ASM_SIMP_TAC[REAL_SUMS_INFSUM]; |
| 62 |
REWRITE_TAC[real_div] THEN MATCH_MP_TAC REAL_SERIES_LMUL THEN |
| 63 |
REWRITE_TAC[GSYM real_div] THEN MATCH_MP_TAC REAL_SUMS_GP THEN |
| 64 |
ASM_REWRITE_TAC[REAL_ABS_ABS]; |
| 65 |
ALL_TAC |
| 66 |
] THEN |
| 67 |
REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_POW] THEN |
| 68 |
MATCH_MP_TAC REAL_LE_RMUL THEN |
| 69 |
CONJ_TAC THENL [ ALL_TAC; MATCH_MP_TAC REAL_POW_LE THEN REAL_ARITH_TAC ] THEN |
| 70 |
POP_ASSUM MP_TAC THEN REWRITE_TAC[IN_FROM] THEN DISCH_TAC THEN |
| 71 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);; |
| 72 |
|
| 73 |
let power_series_simple_bound2 = prove |
| 74 |
(`!a x m. real_summable (from m) (\i. a i * x pow i) |
| 75 |
/\ (!i. m <= i ==> abs (a (SUC i)) <= abs (a i)) |
| 76 |
/\ abs x < &1 |
| 77 |
==> abs (real_infsum (from m) (\i. a i * x pow i)) |
| 78 |
<= abs (a m) * abs x pow m / (&1 - abs x)`, |
| 79 |
REPEAT STRIP_TAC THEN |
| 80 |
MATCH_MP_TAC power_series_simple_bound THEN ASM_REWRITE_TAC[] THEN |
| 81 |
INDUCT_TAC THEN REWRITE_TAC[LE] THEN REPEAT STRIP_TAC THEN ASM_REWRITE_TAC[REAL_LE_REFL] THEN |
| 82 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `abs (a (i:num))` THEN |
| 83 |
ASM_SIMP_TAC[]);; |
| 84 |
|
| 85 |
let real_sums_simple_bound = prove |
| 86 |
(`!a u t x n m. ((\i. a i * x pow i) real_sums t) (from n) |
| 87 |
/\ n < m |
| 88 |
/\ (!i. m <= i ==> abs (a i) <= u) |
| 89 |
/\ abs x < &1 |
| 90 |
==> abs (t - sum (n..m - 1) (\i. a i * x pow i)) |
| 91 |
<= u * abs x pow m / (&1 - abs x)`, |
| 92 |
REPEAT STRIP_TAC THEN |
| 93 |
FIRST_ASSUM (ASSUME_TAC o MATCH_MP REAL_SUMS_SUMMABLE) THEN |
| 94 |
FIRST_ASSUM (ASSUME_TAC o MATCH_MP REAL_INFSUM_UNIQUE) THEN |
| 95 |
MP_TAC (SPECL[`n:num`; `m:num`; `\i. a i * x pow i`] real_infsum_offset_alt) THEN |
| 96 |
ASM_REWRITE_TAC[REAL_ARITH `a = s + r <=> a - s = r:real`] THEN |
| 97 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN |
| 98 |
MATCH_MP_TAC power_series_simple_bound THEN ASM_REWRITE_TAC[] THEN |
| 99 |
MATCH_MP_TAC REAL_SUMMABLE_FROM_ELSEWHERE THEN |
| 100 |
EXISTS_TAC `n:num` THEN ASM_REWRITE_TAC[]);; |
| 101 |
|
| 102 |
|
| 103 |
let real_sums_simple_bound2 = prove |
| 104 |
(`!a t x n m. ((\i. a i * x pow i) real_sums t) (from n) |
| 105 |
/\ n < m |
| 106 |
/\ (!i. m <= i ==> abs (a (SUC i)) <= abs (a i)) |
| 107 |
/\ abs x < &1 |
| 108 |
==> abs (t - sum (n..m - 1) (\i. a i * x pow i)) |
| 109 |
<= abs (a m) * abs x pow m / (&1 - abs x)`, |
| 110 |
REPEAT STRIP_TAC THEN |
| 111 |
FIRST_ASSUM (ASSUME_TAC o MATCH_MP REAL_SUMS_SUMMABLE) THEN |
| 112 |
FIRST_ASSUM (ASSUME_TAC o MATCH_MP REAL_INFSUM_UNIQUE) THEN |
| 113 |
MP_TAC (SPECL[`n:num`; `m:num`; `\i. a i * x pow i`] real_infsum_offset_alt) THEN |
| 114 |
ASM_REWRITE_TAC[REAL_ARITH `a = s + r <=> a - s = r:real`] THEN |
| 115 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN |
| 116 |
MATCH_MP_TAC power_series_simple_bound2 THEN ASM_REWRITE_TAC[] THEN |
| 117 |
MATCH_MP_TAC REAL_SUMMABLE_FROM_ELSEWHERE THEN |
| 118 |
EXISTS_TAC `n:num` THEN ASM_REWRITE_TAC[]);; |
| 119 |
|
| 120 |
let abs_sum_lemma_pos = prove |
| 121 |
(`!a b. &0 <= a * b ==> abs (a + b) = abs a + abs b`, |
| 122 |
REWRITE_TAC[REAL_MUL_POS_LE] THEN REAL_ARITH_TAC);; |
| 123 |
|
| 124 |
let abs_sum_lemma_neg = prove |
| 125 |
(`!a b. a * b <= &0 ==> abs (a + b) = abs (abs a - abs b)`, |
| 126 |
ONCE_REWRITE_TAC[REAL_ARITH `a * b <= &0 <=> &0 <= (--a) * b`] THEN |
| 127 |
REWRITE_TAC[REAL_MUL_POS_LE] THEN REAL_ARITH_TAC);; |
| 128 |
|
| 129 |
let sign_mul_lemma = prove |
| 130 |
(`!a b c. a * b <= &0 /\ &0 <= b * c /\ ~(b = &0) ==> a * c <= &0`, |
| 131 |
REPEAT STRIP_TAC THEN |
| 132 |
MP_TAC (SPECL[`b * c:real`; `a * b:real`; `&0`] REAL_LE_LMUL) THEN |
| 133 |
ASM_REWRITE_TAC[REAL_MUL_RZERO] THEN |
| 134 |
REWRITE_TAC[REAL_ARITH `(b * c) * a * b = (b * b) * (a * c):real`] THEN |
| 135 |
POP_ASSUM (MP_TAC o REWRITE_RULE[GSYM REAL_LT_SQUARE]) THEN |
| 136 |
ONCE_REWRITE_TAC[REAL_ARITH `(b * b) * x <= &0 <=> &0 <= (--(b * b) * x)`] THEN |
| 137 |
REWRITE_TAC[REAL_MUL_POS_LE] THEN REAL_ARITH_TAC);; |
| 138 |
|
| 139 |
let sum_bound_lemma = prove |
| 140 |
(`!m n f. |
| 141 |
(!k. abs (f (k + 1)) <= abs (f k) /\ f (k + 1) * f k <= &0) ==> |
| 142 |
abs (sum (m..n) f) <= abs (f m) /\ &0 <= sum (m..n) f * f m`, |
| 143 |
GEN_TAC THEN GEN_TAC THEN |
| 144 |
ABBREV_TAC `t:num = n - m` THEN |
| 145 |
POP_ASSUM MP_TAC THEN |
| 146 |
MAP_EVERY (fun tm -> SPEC_TAC (tm, tm)) [`m:num`; `n:num`; `t:num`] THEN |
| 147 |
INDUCT_TAC THEN REPEAT (FIRST [GEN_TAC; DISCH_TAC]) THENL [ |
| 148 |
SUBGOAL_THEN `n < m \/ n = m:num` DISJ_CASES_TAC THENL [ |
| 149 |
UNDISCH_TAC `n - m = 0` THEN ARITH_TAC; |
| 150 |
ASM_SIMP_TAC[SUM_TRIV_NUMSEG; REAL_ABS_0; REAL_ABS_POS; REAL_MUL_LZERO; REAL_LE_REFL]; |
| 151 |
ALL_TAC |
| 152 |
] THEN |
| 153 |
ASM_REWRITE_TAC[SUM_SING_NUMSEG; REAL_LE_REFL; REAL_LE_SQUARE]; |
| 154 |
ALL_TAC |
| 155 |
] THEN |
| 156 |
SUBGOAL_THEN `m <= n:num /\ n - (m + 1) = t` ASSUME_TAC THENL [ |
| 157 |
UNDISCH_TAC `n - m = SUC t` THEN ARITH_TAC; |
| 158 |
ALL_TAC |
| 159 |
] THEN |
| 160 |
ASM_SIMP_TAC[SUM_CLAUSES_LEFT] THEN |
| 161 |
FIRST_X_ASSUM (MP_TAC o SPECL[`n:num`; `m + 1`]) THEN |
| 162 |
ASM_REWRITE_TAC[] THEN |
| 163 |
DISCH_THEN (MP_TAC o SPEC `f:num->real`) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN |
| 164 |
FIRST_X_ASSUM (MP_TAC o SPEC `m:num`) THEN STRIP_TAC THEN |
| 165 |
ASM_CASES_TAC `f (m + 1) = &0` THENL [ |
| 166 |
SUBGOAL_THEN `sum (m + 1..n) f = &0` ASSUME_TAC THENL [ |
| 167 |
UNDISCH_TAC `abs (sum (m + 1..n) f) <= abs (f (m + 1))` THEN |
| 168 |
ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC; |
| 169 |
ALL_TAC |
| 170 |
] THEN |
| 171 |
ASM_REWRITE_TAC[REAL_ADD_RID; REAL_LE_SQUARE; REAL_LE_REFL]; |
| 172 |
ALL_TAC |
| 173 |
] THEN |
| 174 |
ABBREV_TAC `a = (f:num->real) m` THEN |
| 175 |
ABBREV_TAC `b = (f:num->real) (m + 1)` THEN |
| 176 |
ABBREV_TAC `c = sum (m + 1..n) f` THEN |
| 177 |
CONJ_TAC THENL [ |
| 178 |
SUBGOAL_THEN `a * c <= &0` ASSUME_TAC THENL [ |
| 179 |
MATCH_MP_TAC sign_mul_lemma THEN |
| 180 |
EXISTS_TAC `b:real` THEN |
| 181 |
ONCE_REWRITE_TAC[REAL_ARITH `a * b = b * a:real`] THEN |
| 182 |
ASM_REWRITE_TAC[]; |
| 183 |
ALL_TAC |
| 184 |
] THEN |
| 185 |
ASM_SIMP_TAC[abs_sum_lemma_neg] THEN |
| 186 |
MAP_EVERY UNDISCH_TAC [`abs c <= abs b`; `abs b <= abs a`] THEN |
| 187 |
REAL_ARITH_TAC; |
| 188 |
ALL_TAC |
| 189 |
] THEN |
| 190 |
SUBGOAL_THEN `abs (a * c) <= abs (a * a)` MP_TAC THENL [ |
| 191 |
REWRITE_TAC[REAL_ABS_MUL] THEN |
| 192 |
MATCH_MP_TAC REAL_LE_LMUL THEN |
| 193 |
MAP_EVERY UNDISCH_TAC [`abs c <= abs b`; `abs b <= abs a`] THEN |
| 194 |
REAL_ARITH_TAC; |
| 195 |
ALL_TAC |
| 196 |
] THEN |
| 197 |
REWRITE_TAC[REAL_ARITH `(a + c) * a = a * a + c * a:real`] THEN |
| 198 |
SUBGOAL_THEN `abs (a * a) = a * a` (fun th -> REWRITE_TAC[th]) THENL [ |
| 199 |
REWRITE_TAC[REAL_ABS_REFL; REAL_LE_SQUARE]; |
| 200 |
ALL_TAC |
| 201 |
] THEN |
| 202 |
REAL_ARITH_TAC);; |
| 203 |
|
| 204 |
let alt_sign_converges = prove |
| 205 |
(`!f k. (!n. abs (f (n + 1)) <= abs (f n) /\ f (n + 1) * f n <= &0) /\ |
| 206 |
((f ---> &0) sequentially) |
| 207 |
==> ?l. (f real_sums l) (from k)`, |
| 208 |
REWRITE_TAC[REAL_SERIES_CAUCHY; REALLIM_SEQUENTIALLY; GSYM IMP_IMP; REAL_SUB_RZERO] THEN |
| 209 |
REPEAT GEN_TAC THEN DISCH_THEN (LABEL_TAC "h1") THEN REPEAT STRIP_TAC THEN |
| 210 |
REWRITE_TAC[FROM_INTER_NUMSEG_GEN] THEN |
| 211 |
FIRST_X_ASSUM (MP_TAC o SPEC `e:real`) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN |
| 212 |
EXISTS_TAC `N:num` THEN REPEAT STRIP_TAC THEN |
| 213 |
REMOVE_THEN "h1" (MP_TAC o MATCH_MP sum_bound_lemma) THEN |
| 214 |
COND_CASES_TAC THENL [ |
| 215 |
DISCH_THEN (MP_TAC o SPECL[`k:num`; `n:num`]) THEN |
| 216 |
FIRST_X_ASSUM (MP_TAC o SPEC `k:num`) THEN |
| 217 |
ANTS_TAC THENL [ ASM_ARITH_TAC; ALL_TAC ] THEN |
| 218 |
REAL_ARITH_TAC; |
| 219 |
ALL_TAC |
| 220 |
] THEN |
| 221 |
DISCH_THEN (MP_TAC o SPECL[`m:num`; `n:num`]) THEN |
| 222 |
FIRST_X_ASSUM (MP_TAC o SPEC `m:num`) THEN |
| 223 |
ANTS_TAC THENL [ ASM_ARITH_TAC; ALL_TAC ] THEN |
| 224 |
REAL_ARITH_TAC);; |
| 225 |
|
| 226 |
let alt_sign_summable = prove |
| 227 |
(`!f k. (!n. abs (f (n + 1)) <= abs (f n) /\ f (n + 1) * f n <= &0) /\ |
| 228 |
((f ---> &0) sequentially) |
| 229 |
==> real_summable (from k) f`, |
| 230 |
ASM_SIMP_TAC[real_summable; alt_sign_converges]);; |
| 231 |
|
| 232 |
let alt_sign_converges2 = prove |
| 233 |
(`!f k. (!n. abs (f (n + 1)) <= abs (f n) /\ f (n + 1) * f n <= &0) /\ |
| 234 |
((f ---> &0) sequentially) |
| 235 |
==> ?l. (f real_sums l) (from k) |
| 236 |
/\ abs l <= abs (f k) /\ &0 <= l * f k`, |
| 237 |
REPEAT STRIP_TAC THEN |
| 238 |
MP_TAC (SPEC_ALL alt_sign_converges) THEN ASM_REWRITE_TAC[] THEN |
| 239 |
STRIP_TAC THEN EXISTS_TAC `l:real` THEN ASM_REWRITE_TAC[] THEN |
| 240 |
POP_ASSUM MP_TAC THEN REWRITE_TAC[real_sums; FROM_INTER_NUMSEG] THEN DISCH_TAC THEN |
| 241 |
FIRST_ASSUM (MP_TAC o MATCH_MP (REWRITE_RULE[GSYM IMP_IMP] REALLIM_UBOUND)) THEN |
| 242 |
FIRST_ASSUM (MP_TAC o MATCH_MP (REWRITE_RULE[GSYM IMP_IMP] REALLIM_LBOUND)) THEN |
| 243 |
FIRST_ASSUM (ASSUME_TAC o SPEC `(f:num->real) k` o MATCH_MP REALLIM_RMUL) THEN |
| 244 |
FIRST_ASSUM (MP_TAC o MATCH_MP (REWRITE_RULE[GSYM IMP_IMP] REALLIM_LBOUND)) THEN |
| 245 |
REWRITE_TAC[TRIVIAL_LIMIT_SEQUENTIALLY; EVENTUALLY_SEQUENTIALLY] THEN |
| 246 |
DISCH_THEN (ASSUME_TAC o SPEC `&0`) THEN |
| 247 |
DISCH_THEN (ASSUME_TAC o SPEC `--abs (f (k:num))`) THEN |
| 248 |
DISCH_THEN (ASSUME_TAC o SPEC `abs (f (k:num))`) THEN |
| 249 |
POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN |
| 250 |
FIRST_X_ASSUM (ASSUME_TAC o MATCH_MP sum_bound_lemma) THEN |
| 251 |
ANTS_TAC THENL [ |
| 252 |
EXISTS_TAC `0` THEN ASM_REWRITE_TAC[LE_0]; |
| 253 |
ALL_TAC |
| 254 |
] THEN |
| 255 |
DISCH_TAC THEN |
| 256 |
ANTS_TAC THENL [ |
| 257 |
EXISTS_TAC `0` THEN REWRITE_TAC[LE_0] THEN GEN_TAC THEN |
| 258 |
FIRST_X_ASSUM (MP_TAC o SPECL[`k:num`; `n:num`]) THEN |
| 259 |
REAL_ARITH_TAC; |
| 260 |
ALL_TAC |
| 261 |
] THEN |
| 262 |
DISCH_TAC THEN |
| 263 |
ANTS_TAC THENL [ |
| 264 |
EXISTS_TAC `0` THEN REWRITE_TAC[LE_0] THEN GEN_TAC THEN |
| 265 |
FIRST_X_ASSUM (MP_TAC o SPECL[`k:num`; `n:num`]) THEN |
| 266 |
REAL_ARITH_TAC; |
| 267 |
ALL_TAC |
| 268 |
] THEN |
| 269 |
ASM_REWRITE_TAC[] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC);; |
| 270 |
|
| 271 |
let alt_sign_bound = prove |
| 272 |
(`!f k. (!n. abs (f (n + 1)) <= abs (f n) /\ f (n + 1) * f n <= &0) /\ |
| 273 |
((f ---> &0) sequentially) |
| 274 |
==> abs (real_infsum (from k) f) <= abs (f k)`, |
| 275 |
REPEAT STRIP_TAC THEN |
| 276 |
MP_TAC (SPEC_ALL alt_sign_converges2) THEN ASM_REWRITE_TAC[] THEN |
| 277 |
STRIP_TAC THEN ASM_SIMP_TAC[REAL_INFSUM_UNIQUE]);; |
| 278 |
|
| 279 |
let alt_sign_abs_bound = prove |
| 280 |
(`!f m k. (!n. abs (f (n + 1)) <= abs (f n) /\ f (n + 1) * f n <= &0) /\ |
| 281 |
((f ---> &0) sequentially) /\ m < k |
| 282 |
==> abs (real_infsum (from m) f - sum (m..k - 1) f) <= abs (f k)`, |
| 283 |
REPEAT GEN_TAC THEN DISCH_TAC THEN |
| 284 |
MP_TAC (SPEC_ALL real_infsum_offset_alt) THEN |
| 285 |
MP_TAC (SPEC_ALL alt_sign_bound) THEN |
| 286 |
ASM_SIMP_TAC[alt_sign_summable] THEN |
| 287 |
REAL_ARITH_TAC);; |
| 288 |
|
| 289 |
let alt_sign_upper_bound = prove |
| 290 |
(`!f m k. (!n. abs (f (n + 1)) <= abs (f n) /\ f (n + 1) * f n <= &0) /\ |
| 291 |
(f ---> &0) sequentially /\ m < k |
| 292 |
==> real_infsum (from m) f <= sum (m..k - 1) f + abs (f k)`, |
| 293 |
REPEAT GEN_TAC THEN DISCH_THEN (MP_TAC o MATCH_MP alt_sign_abs_bound) THEN |
| 294 |
REAL_ARITH_TAC);; |
| 295 |
|
| 296 |
let alt_sign_lower_bound = prove |
| 297 |
(`!f m k. (!n. abs (f (n + 1)) <= abs (f n) /\ f (n + 1) * f n <= &0) /\ |
| 298 |
(f ---> &0) sequentially /\ m < k |
| 299 |
==> sum (m..k - 1) f - abs (f k) <= real_infsum (from m) f`, |
| 300 |
REPEAT GEN_TAC THEN DISCH_THEN (MP_TAC o MATCH_MP alt_sign_abs_bound) THEN |
| 301 |
REAL_ARITH_TAC);; |
| 302 |
|
| 303 |
let abs_neg_pow = prove |
| 304 |
(`!x n. abs (--x pow n) = abs x pow n`, |
| 305 |
REWRITE_TAC[REAL_ABS_POW; REAL_ABS_NEG]);; |
| 306 |
|
| 307 |
let abs_neg_one_pow = prove |
| 308 |
(`!n. abs (-- &1 pow n) = &1`, |
| 309 |
REWRITE_TAC[abs_neg_pow; REAL_ABS_1; REAL_POW_ONE]);; |
| 310 |
|
| 311 |
let integral_uniform_limit = prove |
| 312 |
(`!f g s a b. |
| 313 |
(!e. &0 < e ==> ?N. !n x. N <= n /\ x IN real_interval[a,b] ==> abs (f n x - g x) < e) /\ |
| 314 |
(!n. ((f n) has_real_integral (s n)) (real_interval[a,b])) |
| 315 |
==> (?r. (g has_real_integral r) (real_interval[a,b]) /\ |
| 316 |
(s ---> r) sequentially)`, |
| 317 |
REPEAT STRIP_TAC THEN |
| 318 |
MP_TAC (SPECL[`g:real->real`; `a:real`; `b:real`] REAL_INTEGRABLE_UNIFORM_LIMIT) THEN |
| 319 |
ANTS_TAC THENL [ |
| 320 |
GEN_TAC THEN DISCH_THEN (fun th -> FIRST_ASSUM (MP_TAC o C MATCH_MP th)) THEN |
| 321 |
STRIP_TAC THEN EXISTS_TAC `(f:num->real->real) N` THEN |
| 322 |
POP_ASSUM (MP_TAC o SPEC `N:num`) THEN |
| 323 |
REWRITE_TAC[REAL_ARITH `abs (a - b) = abs (b - a)`] THEN |
| 324 |
SIMP_TAC[LE_REFL; REAL_LT_IMP_LE] THEN DISCH_THEN (K ALL_TAC) THEN |
| 325 |
REWRITE_TAC[real_integrable_on] THEN |
| 326 |
EXISTS_TAC `(s:num->real) N` THEN ASM_REWRITE_TAC[]; |
| 327 |
ALL_TAC |
| 328 |
] THEN |
| 329 |
REWRITE_TAC[real_integrable_on] THEN STRIP_TAC THEN |
| 330 |
EXISTS_TAC `y:real` THEN ASM_REWRITE_TAC[REALLIM_SEQUENTIALLY] THEN |
| 331 |
REPEAT STRIP_TAC THEN |
| 332 |
ASM_CASES_TAC `b <= a:real` THENL [ |
| 333 |
EXISTS_TAC `0` THEN REPEAT STRIP_TAC THEN |
| 334 |
FIRST_X_ASSUM (MP_TAC o SPEC `n:num`) THEN |
| 335 |
UNDISCH_TAC `(g has_real_integral y) (real_interval[a,b])` THEN |
| 336 |
UNDISCH_TAC `&0 < e` THEN |
| 337 |
ASM_SIMP_TAC[HAS_REAL_INTEGRAL_NULL_EQ] THEN |
| 338 |
REAL_ARITH_TAC; |
| 339 |
ALL_TAC |
| 340 |
] THEN |
| 341 |
FIRST_X_ASSUM (MP_TAC o SPEC `(e / &2) / (b - a)`) THEN |
| 342 |
ANTS_TAC THENL [ |
| 343 |
MATCH_MP_TAC REAL_LT_DIV THEN |
| 344 |
POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 345 |
ALL_TAC |
| 346 |
] THEN |
| 347 |
STRIP_TAC THEN EXISTS_TAC `N:num` THEN REPEAT STRIP_TAC THEN |
| 348 |
MATCH_MP_TAC REAL_LET_TRANS THEN EXISTS_TAC `e / &2` THEN |
| 349 |
CONJ_TAC THENL [ ALL_TAC; UNDISCH_TAC `&0 < e` THEN REAL_ARITH_TAC ] THEN |
| 350 |
SUBGOAL_THEN `e / &2 = ((e / &2) / (b - a)) * (b - a)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 351 |
UNDISCH_TAC `~(b <= a:real)` THEN CONV_TAC REAL_FIELD; |
| 352 |
ALL_TAC |
| 353 |
] THEN |
| 354 |
MATCH_MP_TAC HAS_REAL_INTEGRAL_BOUND THEN |
| 355 |
EXISTS_TAC `\x:real. f (n:num) x - (g x):real` THEN |
| 356 |
REPEAT CONJ_TAC THENL [ |
| 357 |
MATCH_MP_TAC REAL_LE_DIV THEN |
| 358 |
UNDISCH_TAC `&0 < e` THEN UNDISCH_TAC `~(b <= a:real)` THEN REAL_ARITH_TAC; |
| 359 |
UNDISCH_TAC `~(b <= a:real)` THEN REAL_ARITH_TAC; |
| 360 |
MATCH_MP_TAC HAS_REAL_INTEGRAL_SUB THEN ASM_REWRITE_TAC[ETA_AX]; |
| 361 |
ALL_TAC |
| 362 |
] THEN |
| 363 |
REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LT_IMP_LE THEN REWRITE_TAC[] THEN |
| 364 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);; |
| 365 |
|
| 366 |
let integral_series = prove |
| 367 |
(`!f g s r a b. |
| 368 |
(!e. &0 < e ==> ?N. !n x. N <= n /\ x IN real_interval[a,b] |
| 369 |
==> abs (sum (s INTER (0..n)) (\i. f i x) - g x) < e) /\ |
| 370 |
(!n. ((f n) has_real_integral (r n)) (real_interval[a,b])) |
| 371 |
==> (?v. (g has_real_integral v) (real_interval[a,b]) /\ (r real_sums v) s)`, |
| 372 |
REPEAT STRIP_TAC THEN |
| 373 |
REWRITE_TAC[real_sums] THEN |
| 374 |
MATCH_MP_TAC integral_uniform_limit THEN |
| 375 |
EXISTS_TAC `\n x:real. sum (s INTER (0..n)) (\i. f i x)` THEN |
| 376 |
ASM_REWRITE_TAC[] THEN GEN_TAC THEN |
| 377 |
MATCH_MP_TAC HAS_REAL_INTEGRAL_SUM THEN |
| 378 |
ASM_SIMP_TAC[FINITE_NUMSEG; FINITE_INTER]);; |
| 379 |
|
| 380 |
let power_series_uniform = prove |
| 381 |
(`!a s t y. real_summable s (\i. a i * y pow i) /\ abs t < abs y |
| 382 |
==> (!e. &0 < e ==> ?N. !n x. N <= n /\ x IN real_interval[--abs t, abs t] |
| 383 |
==> abs (sum (s INTER (0..n)) (\i. a i * x pow i) |
| 384 |
- real_infsum s (\i. a i * x pow i)) < e)`, |
| 385 |
REPEAT STRIP_TAC THEN |
| 386 |
ABBREV_TAC `M = (abs y + abs t) / (abs y - abs t)` THEN |
| 387 |
SUBGOAL_THEN `&0 < M /\ M * (abs y - abs t) = abs y + abs t` ASSUME_TAC THENL [ |
| 388 |
EXPAND_TAC "M" THEN CONJ_TAC THENL [ |
| 389 |
MATCH_MP_TAC REAL_LT_DIV THEN UNDISCH_TAC `abs t < abs y` THEN REAL_ARITH_TAC; |
| 390 |
ALL_TAC |
| 391 |
] THEN |
| 392 |
MATCH_MP_TAC REAL_DIV_RMUL THEN UNDISCH_TAC `abs t < abs y` THEN REAL_ARITH_TAC; |
| 393 |
ALL_TAC |
| 394 |
] THEN |
| 395 |
MP_TAC (SPECL[`M:real`; `Cx o (a:num->real)`; `Cx y`; `s:num->bool`; `e:real`] POWER_SERIES_UNIFORM_CONVERGENCE_STOLZ) THEN |
| 396 |
ANTS_TAC THEN ASM_REWRITE_TAC[EVENTUALLY_SEQUENTIALLY] THENL [ |
| 397 |
UNDISCH_TAC `real_summable s (\i. a i * y pow i)` THEN |
| 398 |
REWRITE_TAC[REAL_SUMMABLE_COMPLEX; o_THM] THEN |
| 399 |
SUBGOAL_THEN `Cx o (\i. a i * y pow i) = \i. Cx (a i) * Cx y pow i` (fun th -> REWRITE_TAC[th]) THEN |
| 400 |
REWRITE_TAC[FUN_EQ_THM; o_THM; CX_MUL; CX_POW]; |
| 401 |
ALL_TAC |
| 402 |
] THEN |
| 403 |
STRIP_TAC THEN |
| 404 |
EXISTS_TAC `N:num` THEN REWRITE_TAC[IN_REAL_INTERVAL] THEN REPEAT STRIP_TAC THEN |
| 405 |
FIRST_X_ASSUM (MP_TAC o SPEC `n:num`) THEN ASM_REWRITE_TAC[] THEN |
| 406 |
DISCH_THEN (MP_TAC o SPEC `Cx x`) THEN |
| 407 |
REWRITE_TAC[GSYM CX_SUB; COMPLEX_NORM_CX] THEN ANTS_TAC THENL [ |
| 408 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `M * (abs y - abs t)` THEN |
| 409 |
CONJ_TAC THENL [ |
| 410 |
ASM_REWRITE_TAC[] THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 411 |
ALL_TAC |
| 412 |
] THEN |
| 413 |
ASM_SIMP_TAC[REAL_LE_LMUL_EQ] THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 414 |
ALL_TAC |
| 415 |
] THEN |
| 416 |
SUBGOAL_THEN `(\i. (Cx o a) i * Cx x pow i) = (\i. Cx (a i * x pow i))` ASSUME_TAC THENL [ |
| 417 |
REWRITE_TAC[FUN_EQ_THM; o_THM; CX_MUL; CX_POW]; |
| 418 |
ALL_TAC |
| 419 |
] THEN |
| 420 |
ASM_REWRITE_TAC[VSUM_CX] THEN |
| 421 |
SUBGOAL_THEN `infsum s (\i. Cx (a i * x pow i)) = Cx (real_infsum s (\i. a i * x pow i))` ASSUME_TAC THENL [ |
| 422 |
SUBGOAL_THEN `real_summable s (\i. a i * x pow i)` MP_TAC THENL [ |
| 423 |
MATCH_MP_TAC REAL_SERIES_ABSCONV_IMP_CONV THEN REWRITE_TAC[] THEN |
| 424 |
MATCH_MP_TAC REAL_POWER_SERIES_CONV_IMP_ABSCONV THEN |
| 425 |
EXISTS_TAC `y:real` THEN ASM_REWRITE_TAC[] THEN |
| 426 |
MAP_EVERY UNDISCH_TAC [`abs t < abs y`; `--abs t <= x:real`; `x <= abs t:real`] THEN |
| 427 |
REAL_ARITH_TAC; |
| 428 |
ALL_TAC |
| 429 |
] THEN |
| 430 |
REWRITE_TAC[real_summable] THEN STRIP_TAC THEN |
| 431 |
ASM_SIMP_TAC[REAL_INFSUM_UNIQUE] THEN POP_ASSUM MP_TAC THEN |
| 432 |
REWRITE_TAC[REAL_SUMS_COMPLEX] THEN DISCH_TAC THEN |
| 433 |
MATCH_MP_TAC INFSUM_UNIQUE THEN |
| 434 |
SUBGOAL_THEN `(\i. Cx (a i * x pow i)) = Cx o (\i. a i * x pow i)` ASSUME_TAC THENL [ |
| 435 |
REWRITE_TAC[FUN_EQ_THM; o_THM; CX_MUL; CX_POW]; |
| 436 |
ALL_TAC |
| 437 |
] THEN |
| 438 |
ASM_REWRITE_TAC[]; |
| 439 |
ALL_TAC |
| 440 |
] THEN |
| 441 |
ASM_REWRITE_TAC[GSYM CX_SUB; COMPLEX_NORM_CX]);; |
| 442 |
|
| 443 |
let has_real_integral_pow_pos = prove |
| 444 |
(`!n a. &0 <= a ==> |
| 445 |
((\x. x pow n) has_real_integral a pow (n + 1) / &(n + 1)) |
| 446 |
(real_interval[&0, a])`, |
| 447 |
REPEAT STRIP_TAC THEN |
| 448 |
MP_TAC (SPECL[`\t:real. t pow (n + 1) / &(n + 1)`; `\t:real. t pow n`; `&0`; `a:real`] REAL_FUNDAMENTAL_THEOREM_OF_CALCULUS) THEN |
| 449 |
ANTS_TAC THEN ASM_REWRITE_TAC[] THENL [ |
| 450 |
REPEAT STRIP_TAC THEN MATCH_MP_TAC HAS_REAL_DERIVATIVE_ATREAL_WITHIN THEN |
| 451 |
REAL_DIFF_TAC THEN |
| 452 |
REWRITE_TAC[ADD_SUB; REAL_MUL_RID; real_div] THEN |
| 453 |
ONCE_REWRITE_TAC[REAL_ARITH `(a * b) * c = (a * c) * b:real`] THEN |
| 454 |
SUBGOAL_THEN `~(&(n + 1) = &0)` ASSUME_TAC THENL [ |
| 455 |
REWRITE_TAC[GSYM REAL_OF_NUM_ADD] THEN REAL_ARITH_TAC; |
| 456 |
ALL_TAC |
| 457 |
] THEN |
| 458 |
ASM_SIMP_TAC[REAL_MUL_RINV; REAL_MUL_LID]; |
| 459 |
ALL_TAC |
| 460 |
] THEN |
| 461 |
REWRITE_TAC[REAL_POW_ZERO; ARITH_RULE `~(n + 1 = 0)`; real_div; REAL_MUL_LZERO; REAL_SUB_RZERO]);; |
| 462 |
|
| 463 |
let has_real_integral_pow_neg = prove |
| 464 |
(`!n a. a <= &0 ==> |
| 465 |
((\x. x pow n) has_real_integral --(a pow (n + 1) / &(n + 1))) |
| 466 |
(real_interval[a, &0])`, |
| 467 |
REPEAT STRIP_TAC THEN |
| 468 |
MP_TAC (SPECL[`\t:real. t pow (n + 1) / &(n + 1)`; `\t:real. t pow n`; `a:real`; `&0`] REAL_FUNDAMENTAL_THEOREM_OF_CALCULUS) THEN |
| 469 |
ANTS_TAC THEN ASM_REWRITE_TAC[] THENL [ |
| 470 |
REPEAT STRIP_TAC THEN MATCH_MP_TAC HAS_REAL_DERIVATIVE_ATREAL_WITHIN THEN |
| 471 |
REAL_DIFF_TAC THEN |
| 472 |
REWRITE_TAC[ADD_SUB; REAL_MUL_RID; real_div] THEN |
| 473 |
ONCE_REWRITE_TAC[REAL_ARITH `(a * b) * c = (a * c) * b:real`] THEN |
| 474 |
SUBGOAL_THEN `~(&(n + 1) = &0)` ASSUME_TAC THENL [ |
| 475 |
REWRITE_TAC[GSYM REAL_OF_NUM_ADD] THEN REAL_ARITH_TAC; |
| 476 |
ALL_TAC |
| 477 |
] THEN |
| 478 |
ASM_SIMP_TAC[REAL_MUL_RINV; REAL_MUL_LID]; |
| 479 |
ALL_TAC |
| 480 |
] THEN |
| 481 |
REWRITE_TAC[REAL_POW_ZERO; ARITH_RULE `~(n + 1 = 0)`; real_div; REAL_MUL_LZERO; REAL_SUB_LZERO]);; |
| 482 |
|
| 483 |
(* Integration of power series *) |
| 484 |
|
| 485 |
let power_series_integral = prove |
| 486 |
(`!f a s r. (!x. abs x < r ==> ((\i. a i * x pow i) real_sums f x) s) |
| 487 |
==> (!x. abs x < r ==> |
| 488 |
let v = if x < &0 then --real_integral (real_interval[x, &0]) f |
| 489 |
else real_integral (real_interval[&0, x]) f in |
| 490 |
((\i. a i * x pow (i + 1) / &(i + 1)) real_sums v) s)`, |
| 491 |
REPEAT STRIP_TAC THEN LET_TAC THEN |
| 492 |
MP_TAC (SPECL[`\i x:real. a i * x pow i`; `f:real->real`; `s:num->bool`; `\i. a i * (if x < &0 then (-- &1) else &1) * x pow (i + 1) / &(i + 1)`; `min x (&0)`; `max x (&0)`] integral_series) THEN |
| 493 |
ANTS_TAC THENL [ |
| 494 |
CONJ_TAC THENL [ |
| 495 |
ABBREV_TAC `y = abs x + (r - abs x) / &2` THEN |
| 496 |
MP_TAC (SPECL[`a:num->real`; `s:num->bool`; `x:real`; `y:real`] power_series_uniform) THEN |
| 497 |
ANTS_TAC THENL [ |
| 498 |
CONJ_TAC THENL [ ALL_TAC; UNDISCH_TAC `abs x < r` THEN EXPAND_TAC "y" THEN REAL_ARITH_TAC ] THEN |
| 499 |
REWRITE_TAC[real_summable] THEN EXISTS_TAC `(f:real->real) y` THEN |
| 500 |
FIRST_X_ASSUM MATCH_MP_TAC THEN |
| 501 |
UNDISCH_TAC `abs x < r` THEN EXPAND_TAC "y" THEN REAL_ARITH_TAC; |
| 502 |
ALL_TAC |
| 503 |
] THEN |
| 504 |
REPEAT STRIP_TAC THEN |
| 505 |
POP_ASSUM (fun th -> FIRST_X_ASSUM (STRIP_ASSUME_TAC o C MATCH_MP th)) THEN |
| 506 |
EXISTS_TAC `N:num` THEN REPEAT STRIP_TAC THEN |
| 507 |
FIRST_X_ASSUM (MP_TAC o SPECL[`n:num`; `x':real`]) THEN |
| 508 |
ANTS_TAC THEN ASM_REWRITE_TAC[] THENL [ |
| 509 |
POP_ASSUM MP_TAC THEN REWRITE_TAC[IN_REAL_INTERVAL] THEN REAL_ARITH_TAC; |
| 510 |
ALL_TAC |
| 511 |
] THEN |
| 512 |
SUBGOAL_THEN `real_infsum s (\i. a i * x' pow i) = f x'` (fun th -> SIMP_TAC[th]) THEN |
| 513 |
MATCH_MP_TAC REAL_INFSUM_UNIQUE THEN |
| 514 |
FIRST_X_ASSUM MATCH_MP_TAC THEN |
| 515 |
POP_ASSUM MP_TAC THEN UNDISCH_TAC `abs x < r` THEN |
| 516 |
REWRITE_TAC[IN_REAL_INTERVAL] THEN REAL_ARITH_TAC; |
| 517 |
ALL_TAC |
| 518 |
] THEN |
| 519 |
GEN_TAC THEN REWRITE_TAC[] THEN |
| 520 |
MATCH_MP_TAC HAS_REAL_INTEGRAL_LMUL THEN |
| 521 |
COND_CASES_TAC THENL [ |
| 522 |
ASM_SIMP_TAC[REAL_ARITH `x < &0 ==> min x (&0) = x /\ max x (&0) = &0`] THEN |
| 523 |
REWRITE_TAC[REAL_ARITH `-- &1 * t = --t`] THEN |
| 524 |
MATCH_MP_TAC has_real_integral_pow_neg THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 525 |
ALL_TAC |
| 526 |
] THEN |
| 527 |
ASM_SIMP_TAC[REAL_ARITH `~(x < &0) ==> min x (&0) = &0 /\ max x (&0) = x`; REAL_MUL_LID] THEN |
| 528 |
MATCH_MP_TAC has_real_integral_pow_pos THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 529 |
ALL_TAC |
| 530 |
] THEN |
| 531 |
STRIP_TAC THEN |
| 532 |
SUBGOAL_THEN `v:real = if x < &0 then --v' else v'` ASSUME_TAC THENL [ |
| 533 |
POP_ASSUM (K ALL_TAC) THEN POP_ASSUM MP_TAC THEN |
| 534 |
EXPAND_TAC "v" THEN COND_CASES_TAC THENL [ |
| 535 |
ASM_SIMP_TAC[REAL_ARITH `x < &0 ==> min x (&0) = x /\ max x (&0) = &0`] THEN |
| 536 |
DISCH_THEN (MP_TAC o MATCH_MP REAL_INTEGRAL_UNIQUE) THEN REAL_ARITH_TAC; |
| 537 |
ALL_TAC |
| 538 |
] THEN |
| 539 |
ASM_SIMP_TAC[REAL_ARITH `~(x < &0) ==> min x (&0) = &0 /\ max x (&0) = x`] THEN |
| 540 |
DISCH_THEN (MP_TAC o MATCH_MP REAL_INTEGRAL_UNIQUE) THEN REWRITE_TAC[]; |
| 541 |
ALL_TAC |
| 542 |
] THEN |
| 543 |
ASM_REWRITE_TAC[] THEN POP_ASSUM (K ALL_TAC) THEN POP_ASSUM MP_TAC THEN |
| 544 |
COND_CASES_TAC THEN REWRITE_TAC[] THENL [ |
| 545 |
DISCH_THEN (MP_TAC o MATCH_MP REAL_SERIES_NEG) THEN |
| 546 |
REWRITE_TAC[REAL_ARITH `--(a * (-- &1) * b) = a * b:real`]; |
| 547 |
ALL_TAC |
| 548 |
] THEN |
| 549 |
REWRITE_TAC[REAL_MUL_LID]);; |
| 550 |
|
| 551 |
let power_series_integral2 = prove |
| 552 |
(`!f f' a s r. |
| 553 |
(!x. abs x < r ==> (f has_real_derivative f' x) (atreal x)) /\ |
| 554 |
(!x. abs x < r ==> ((\i. a i * x pow i) real_sums f' x) s) |
| 555 |
==> (!x. abs x < r |
| 556 |
==> ((\i. a i * x pow (i + 1) / &(i + 1)) real_sums f x - f (&0)) s)`, |
| 557 |
REWRITE_TAC[GSYM IMP_IMP] THEN REPEAT GEN_TAC THEN DISCH_TAC THEN |
| 558 |
DISCH_THEN (MP_TAC o MATCH_MP power_series_integral) THEN REPEAT STRIP_TAC THEN |
| 559 |
FIRST_ASSUM (fun th -> FIRST_X_ASSUM (MP_TAC o C MATCH_MP th)) THEN |
| 560 |
LET_TAC THEN |
| 561 |
SUBGOAL_THEN `v = (f:real->real) x - f (&0)` (fun th -> REWRITE_TAC[th]) THEN |
| 562 |
EXPAND_TAC "v" THEN COND_CASES_TAC THENL [ |
| 563 |
MP_TAC (SPECL[`f:real->real`; `f':real->real`; `x:real`; `&0`] REAL_FUNDAMENTAL_THEOREM_OF_CALCULUS) THEN |
| 564 |
ANTS_TAC THENL [ |
| 565 |
ASM_SIMP_TAC[REAL_LT_IMP_LE; IN_REAL_INTERVAL] THEN REPEAT STRIP_TAC THEN |
| 566 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_ATREAL_WITHIN THEN |
| 567 |
FIRST_X_ASSUM MATCH_MP_TAC THEN |
| 568 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 569 |
ALL_TAC |
| 570 |
] THEN |
| 571 |
DISCH_THEN (MP_TAC o MATCH_MP REAL_INTEGRAL_UNIQUE) THEN REAL_ARITH_TAC; |
| 572 |
ALL_TAC |
| 573 |
] THEN |
| 574 |
MP_TAC (SPECL[`f:real->real`; `f':real->real`; `&0`; `x:real`] REAL_FUNDAMENTAL_THEOREM_OF_CALCULUS) THEN |
| 575 |
ANTS_TAC THENL [ |
| 576 |
CONJ_TAC THENL [ POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; ALL_TAC ] THEN |
| 577 |
REWRITE_TAC[IN_REAL_INTERVAL] THEN REPEAT STRIP_TAC THEN |
| 578 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_ATREAL_WITHIN THEN |
| 579 |
FIRST_X_ASSUM MATCH_MP_TAC THEN |
| 580 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 581 |
ALL_TAC |
| 582 |
] THEN |
| 583 |
DISCH_THEN (MP_TAC o MATCH_MP REAL_INTEGRAL_UNIQUE) THEN REAL_ARITH_TAC);; |
| 584 |
|
| 585 |
|
| 586 |
(****************************) |
| 587 |
|
| 588 |
let strict_increasing_num_le = prove |
| 589 |
(`!h:num->num. (!n. h n < h (n + 1)) ==> (!n. n <= h n)`, |
| 590 |
GEN_TAC THEN DISCH_TAC THEN INDUCT_TAC THEN TRY ARITH_TAC THEN |
| 591 |
FIRST_X_ASSUM (MP_TAC o SPEC `n:num`) THEN |
| 592 |
REWRITE_TAC[ADD1] THEN POP_ASSUM MP_TAC THEN ARITH_TAC);; |
| 593 |
|
| 594 |
let strict_increasing_num_lt = prove |
| 595 |
(`!h:num->num. (!n. h n < h (n + 1)) ==> (!n m. n < m ==> h n < h m)`, |
| 596 |
GEN_TAC THEN DISCH_TAC THEN INDUCT_TAC THEN INDUCT_TAC THEN TRY ARITH_TAC THENL [ |
| 597 |
FIRST_X_ASSUM (MP_TAC o SPEC `m:num`) THEN |
| 598 |
ASM_CASES_TAC `m = 0` THEN ASM_SIMP_TAC[ADD1] THEN ASM_ARITH_TAC; |
| 599 |
ALL_TAC |
| 600 |
] THEN |
| 601 |
REWRITE_TAC[LT_SUC] THEN |
| 602 |
ASM_CASES_TAC `SUC n = m` THEN ASM_REWRITE_TAC[ADD1] THEN DISCH_TAC THEN |
| 603 |
REPEAT (FIRST_X_ASSUM (MP_TAC o SPEC `m:num`)) THEN |
| 604 |
ASM_ARITH_TAC);; |
| 605 |
|
| 606 |
let strict_increasing_num_inj = prove |
| 607 |
(`!h:num->num. (!n. h n < h (n + 1)) ==> (!n m. h n = h m ==> n = m)`, |
| 608 |
GEN_TAC THEN DISCH_THEN (MP_TAC o MATCH_MP strict_increasing_num_lt) THEN |
| 609 |
REPEAT STRIP_TAC THEN |
| 610 |
DISJ_CASES_TAC (ARITH_RULE `n = m:num \/ n < m \/ m < n`) THEN ASM_REWRITE_TAC[] THEN |
| 611 |
POP_ASSUM DISJ_CASES_TAC THEN POP_ASSUM (fun th -> FIRST_X_ASSUM (MP_TAC o C MATCH_MP th)) THEN ASM_ARITH_TAC);; |
| 612 |
|
| 613 |
let strict_increasing_num_le_eq = prove |
| 614 |
(`!h:num->num. (!n. h n < h (n + 1)) ==> (!n m. h n <= h m <=> n <= m)`, |
| 615 |
MESON_TAC[strict_increasing_num_lt; LE_LT; NOT_LE]);; |
| 616 |
|
| 617 |
let strict_increasing_num_lt_eq = prove |
| 618 |
(`!h:num->num. (!n. h n < h (n + 1)) ==> (!n m. h n < h m <=> n < m)`, |
| 619 |
MESON_TAC[strict_increasing_num_lt; LT_LE; NOT_LT]);; |
| 620 |
|
| 621 |
let strict_increasing_num_le2 = prove |
| 622 |
(`!h:num->num. (!n. h n < h (n + 1)) ==> (!n m. h n <= m ==> n <= m)`, |
| 623 |
MESON_TAC[strict_increasing_num_le; strict_increasing_num_le_eq; LE_TRANS]);; |
| 624 |
|
| 625 |
|
| 626 |
let real_sums_image = prove |
| 627 |
(`!f h s l. (!n. h n < h (n + 1)) |
| 628 |
==> ((f real_sums l) (IMAGE h s) <=> ((f o h) real_sums l) s)`, |
| 629 |
REWRITE_TAC[real_sums; REALLIM_SEQUENTIALLY] THEN REPEAT STRIP_TAC THEN |
| 630 |
EQ_TAC THEN REPEAT STRIP_TAC THENL [ |
| 631 |
POP_ASSUM (fun th -> FIRST_X_ASSUM (STRIP_ASSUME_TAC o C MATCH_MP th)) THEN |
| 632 |
EXISTS_TAC `N:num` THEN REPEAT STRIP_TAC THEN |
| 633 |
SUBGOAL_THEN `?m. N <= m /\ IMAGE (h:num->num) s INTER (0..m) = IMAGE h (s INTER (0..n))` STRIP_ASSUME_TAC THENL [ |
| 634 |
EXISTS_TAC `(h:num->num) n` THEN |
| 635 |
FIRST_ASSUM (LABEL_TAC "h_le" o MATCH_MP strict_increasing_num_le) THEN |
| 636 |
FIRST_ASSUM (LABEL_TAC "h_le_eq" o MATCH_MP strict_increasing_num_le_eq) THEN |
| 637 |
CONJ_TAC THENL [ |
| 638 |
UNDISCH_TAC `N <= n:num` THEN REMOVE_THEN "h_le" (MP_TAC o SPEC `n:num`) THEN |
| 639 |
ARITH_TAC; |
| 640 |
ALL_TAC |
| 641 |
] THEN |
| 642 |
REWRITE_TAC[EXTENSION; IN_INTER; IN_IMAGE; IN_NUMSEG; LE_0] THEN |
| 643 |
GEN_TAC THEN EQ_TAC THEN STRIP_TAC THENL [ |
| 644 |
EXISTS_TAC `x':num` THEN POP_ASSUM MP_TAC THEN ASM_REWRITE_TAC[]; |
| 645 |
ALL_TAC |
| 646 |
] THEN |
| 647 |
ASM_REWRITE_TAC[] THEN EXISTS_TAC `x':num` THEN ASM_REWRITE_TAC[]; |
| 648 |
ALL_TAC |
| 649 |
] THEN |
| 650 |
FIRST_X_ASSUM (MP_TAC o SPEC `m:num`) THEN ASM_REWRITE_TAC[] THEN |
| 651 |
SUBGOAL_THEN `!x y. x IN (s INTER (0..n)) /\ y IN (s INTER (0..n)) /\ h x = (h:num->num) y ==> x = y` ASSUME_TAC THENL [ |
| 652 |
ASM_MESON_TAC[strict_increasing_num_inj]; |
| 653 |
ALL_TAC |
| 654 |
] THEN |
| 655 |
POP_ASSUM (MP_TAC o MATCH_MP SUM_IMAGE) THEN SIMP_TAC[]; |
| 656 |
ALL_TAC |
| 657 |
] THEN |
| 658 |
POP_ASSUM (fun th -> FIRST_X_ASSUM (STRIP_ASSUME_TAC o C MATCH_MP th)) THEN |
| 659 |
EXISTS_TAC `(h:num->num) N` THEN REPEAT STRIP_TAC THEN |
| 660 |
ABBREV_TAC `k = @t. (h:num->num) t <= n /\ (!i. h i <= n ==> i <= t)` THEN |
| 661 |
SUBGOAL_THEN `h k <= n /\ !i. (h:num->num) i <= n ==> i <= k` STRIP_ASSUME_TAC THENL [ |
| 662 |
EXPAND_TAC "k" THEN CONV_TAC SELECT_CONV THEN |
| 663 |
REWRITE_TAC[GSYM num_MAX] THEN |
| 664 |
CONJ_TAC THENL [ EXISTS_TAC `N:num` THEN ASM_REWRITE_TAC[]; EXISTS_TAC `n:num` ] THEN |
| 665 |
ASM_MESON_TAC[strict_increasing_num_le2]; |
| 666 |
ALL_TAC |
| 667 |
] THEN |
| 668 |
POP_ASSUM (LABEL_TAC "i_le_k") THEN |
| 669 |
SUBGOAL_THEN `N <= k:num` ASSUME_TAC THENL [ |
| 670 |
FIRST_X_ASSUM (MP_TAC o SPEC `N:num`) THEN ASM_REWRITE_TAC[]; |
| 671 |
ALL_TAC |
| 672 |
] THEN |
| 673 |
SUBGOAL_THEN `IMAGE (h:num->num) s INTER (0..n) = IMAGE h (s INTER (0..k))` ASSUME_TAC THENL [ |
| 674 |
FIRST_ASSUM (LABEL_TAC "h_le" o MATCH_MP strict_increasing_num_le) THEN |
| 675 |
REWRITE_TAC[EXTENSION; IN_INTER; IN_IMAGE; IN_NUMSEG; LE_0] THEN |
| 676 |
GEN_TAC THEN EQ_TAC THEN STRIP_TAC THENL [ |
| 677 |
EXISTS_TAC `x':num` THEN ASM_REWRITE_TAC[] THEN |
| 678 |
FIRST_X_ASSUM MATCH_MP_TAC THEN |
| 679 |
UNDISCH_TAC `x = (h:num->num) x'` THEN DISCH_THEN (fun th -> ASM_REWRITE_TAC[GSYM th]); |
| 680 |
ALL_TAC |
| 681 |
] THEN |
| 682 |
CONJ_TAC THENL [ EXISTS_TAC `x':num` THEN ASM_REWRITE_TAC[]; ALL_TAC ] THEN |
| 683 |
FIRST_ASSUM (MP_TAC o SPECL[`x':num`; `k:num`] o MATCH_MP strict_increasing_num_le_eq) THEN |
| 684 |
ASM_REWRITE_TAC[] THEN ASM_ARITH_TAC; |
| 685 |
ALL_TAC |
| 686 |
] THEN |
| 687 |
REMOVE_THEN "i_le_k" (K ALL_TAC) THEN |
| 688 |
FIRST_X_ASSUM (MP_TAC o SPEC `k:num`) THEN ASM_REWRITE_TAC[] THEN |
| 689 |
SUBGOAL_THEN `!x y. x IN (s INTER (0..k)) /\ y IN (s INTER (0..k)) /\ h x = (h:num->num) y ==> x = y` ASSUME_TAC THENL [ |
| 690 |
ASM_MESON_TAC[strict_increasing_num_inj]; |
| 691 |
ALL_TAC |
| 692 |
] THEN |
| 693 |
POP_ASSUM (MP_TAC o MATCH_MP SUM_IMAGE) THEN SIMP_TAC[]);; |
| 694 |
|
| 695 |
let real_summable_image = prove |
| 696 |
(`!f h s. (!n. h n < h (n + 1)) |
| 697 |
==> (real_summable (IMAGE h s) f <=> real_summable s (f o h))`, |
| 698 |
REPEAT GEN_TAC THEN DISCH_THEN (MP_TAC o MATCH_MP real_sums_image) THEN |
| 699 |
REWRITE_TAC[real_summable] THEN DISCH_TAC THEN EQ_TAC THEN REPEAT STRIP_TAC THENL [ |
| 700 |
EXISTS_TAC `l:real` THEN POP_ASSUM MP_TAC THEN ASM_REWRITE_TAC[]; |
| 701 |
EXISTS_TAC `l:real` THEN ASM_REWRITE_TAC[] |
| 702 |
]);; |
| 703 |
|
| 704 |
let real_sums_image_odd = prove |
| 705 |
(`!f l. ((\i. if ODD i then f i else &0) real_sums l) (:num) |
| 706 |
<=> ((\i. f (2 * i + 1)) real_sums l) (:num)`, |
| 707 |
REPEAT GEN_TAC THEN ONCE_REWRITE_TAC[GSYM (ISPEC `ODD` IN)] THEN |
| 708 |
REWRITE_TAC[REAL_SERIES_RESTRICT] THEN |
| 709 |
ABBREV_TAC `h = \i. 2 * i + 1` THEN |
| 710 |
SUBGOAL_THEN `ODD = IMAGE h (:num)` (fun th -> REWRITE_TAC[th]) THENL [ |
| 711 |
EXPAND_TAC "h" THEN REWRITE_TAC[EXTENSION; IN_IMAGE; IN_UNIV; IN; ODD_EXISTS; ADD1]; |
| 712 |
ALL_TAC |
| 713 |
] THEN |
| 714 |
SUBGOAL_THEN `!n. h n < (h:num->num) (n + 1)` MP_TAC THENL [ |
| 715 |
EXPAND_TAC "h" THEN ARITH_TAC; |
| 716 |
ALL_TAC |
| 717 |
] THEN |
| 718 |
DISCH_THEN (MP_TAC o MATCH_MP real_sums_image) THEN |
| 719 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN |
| 720 |
SUBGOAL_THEN `f o h = \i. (f:num->real) (2 * i + 1)` (fun th -> REWRITE_TAC[th]) THEN |
| 721 |
EXPAND_TAC "h" THEN REWRITE_TAC[FUN_EQ_THM; o_THM]);; |
| 722 |
|
| 723 |
let real_sums_image_even = prove |
| 724 |
(`!f l. ((\i. if EVEN i then f i else &0) real_sums l) (:num) |
| 725 |
<=> ((\i. f (2 * i)) real_sums l) (:num)`, |
| 726 |
REPEAT GEN_TAC THEN ONCE_REWRITE_TAC[GSYM (ISPEC `EVEN` IN)] THEN |
| 727 |
REWRITE_TAC[REAL_SERIES_RESTRICT] THEN |
| 728 |
ABBREV_TAC `h = \i. 2 * i` THEN |
| 729 |
SUBGOAL_THEN `EVEN = IMAGE h (:num)` (fun th -> REWRITE_TAC[th]) THENL [ |
| 730 |
EXPAND_TAC "h" THEN REWRITE_TAC[EXTENSION; IN_IMAGE; IN_UNIV; IN; EVEN_EXISTS; ADD1]; |
| 731 |
ALL_TAC |
| 732 |
] THEN |
| 733 |
SUBGOAL_THEN `!n. h n < (h:num->num) (n + 1)` MP_TAC THENL [ |
| 734 |
EXPAND_TAC "h" THEN ARITH_TAC; |
| 735 |
ALL_TAC |
| 736 |
] THEN |
| 737 |
DISCH_THEN (MP_TAC o MATCH_MP real_sums_image) THEN |
| 738 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN |
| 739 |
SUBGOAL_THEN `f o h = \i. (f:num->real) (2 * i)` (fun th -> REWRITE_TAC[th]) THEN |
| 740 |
EXPAND_TAC "h" THEN REWRITE_TAC[FUN_EQ_THM; o_THM]);; |
| 741 |
|
| 742 |
|
| 743 |
(* Differentiation of power series *) |
| 744 |
|
| 745 |
let n_le_pow_lemma = prove |
| 746 |
(`!e. &0 < e ==> ?N. !n. N <= n ==> &n <= (&1 + e) pow n`, |
| 747 |
REPEAT STRIP_TAC THEN |
| 748 |
MP_TAC (SPEC `&2 / e pow 2 + &2` REAL_ARCH_SIMPLE) THEN STRIP_TAC THEN |
| 749 |
EXISTS_TAC `n:num` THEN X_GEN_TAC `i:num` THEN DISCH_TAC THEN |
| 750 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&(binom(i, 2)) * e pow 2` THEN |
| 751 |
SUBGOAL_THEN `2 <= i` ASSUME_TAC THENL [ |
| 752 |
MATCH_MP_TAC LE_TRANS THEN EXISTS_TAC `n:num` THEN ASM_REWRITE_TAC[] THEN |
| 753 |
REWRITE_TAC[GSYM REAL_OF_NUM_LE] THEN POP_ASSUM (K ALL_TAC) THEN |
| 754 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&2 / e pow 2 + &2` THEN |
| 755 |
ASM_REWRITE_TAC[REAL_ARITH `a <= b + a <=> &0 <= b`] THEN |
| 756 |
MATCH_MP_TAC REAL_LE_DIV THEN REWRITE_TAC[REAL_LE_POW_2; REAL_POS]; |
| 757 |
ALL_TAC |
| 758 |
] THEN |
| 759 |
CONJ_TAC THENL [ |
| 760 |
SUBGOAL_THEN `&(binom(i,2)) = &i * (&i - &1) / &2` ASSUME_TAC THENL [ |
| 761 |
REWRITE_TAC[TWO; ONE] THEN |
| 762 |
REWRITE_TAC[BINOM_BOTTOM_STEP_REAL; ADD1; binom] THEN |
| 763 |
CONV_TAC NUM_REDUCE_CONV THEN REAL_ARITH_TAC; |
| 764 |
ALL_TAC |
| 765 |
] THEN |
| 766 |
ASM_REWRITE_TAC[REAL_ARITH `x <= (x * b / &2) * c <=> x * &2 <= x * b * c`] THEN |
| 767 |
MATCH_MP_TAC REAL_LE_LMUL THEN REWRITE_TAC[REAL_POS] THEN |
| 768 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `(&n - &1) * e pow 2` THEN |
| 769 |
CONJ_TAC THENL [ |
| 770 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `(&2 / e pow 2 + &1) * e pow 2` THEN |
| 771 |
CONJ_TAC THENL [ |
| 772 |
REWRITE_TAC[REAL_ARITH `(a / b + &1) * b = (a * inv b * b) + b`] THEN |
| 773 |
ASM_SIMP_TAC[REAL_MUL_LINV; REAL_LT_POW_2; REAL_ARITH `&0 < e ==> ~(e = &0)`] THEN |
| 774 |
REWRITE_TAC[REAL_ARITH `&2 <= &2 * &1 + x <=> &0 <= x`; REAL_LE_POW_2]; |
| 775 |
ALL_TAC |
| 776 |
] THEN |
| 777 |
MATCH_MP_TAC REAL_LE_RMUL THEN REWRITE_TAC[REAL_LE_POW_2] THEN |
| 778 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 779 |
ALL_TAC |
| 780 |
] THEN |
| 781 |
MATCH_MP_TAC REAL_LE_RMUL THEN REWRITE_TAC[REAL_LE_POW_2] THEN |
| 782 |
UNDISCH_TAC `n <= i:num` THEN REWRITE_TAC[GSYM REAL_OF_NUM_LE] THEN REAL_ARITH_TAC; |
| 783 |
ALL_TAC |
| 784 |
] THEN |
| 785 |
ONCE_REWRITE_TAC[REAL_ARITH `&1 + e = e + &1`] THEN |
| 786 |
REWRITE_TAC[REAL_BINOMIAL_THEOREM] THEN |
| 787 |
ABBREV_TAC `r = &(binom (i,2)) * e pow 2` THEN |
| 788 |
SUBGOAL_THEN `r = sum (0..i) (\k. if k IN {2} then r else &0)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 789 |
SUBGOAL_THEN `r = sum {2} (\i. r)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 790 |
REWRITE_TAC[SUM_SING]; |
| 791 |
ALL_TAC |
| 792 |
] THEN |
| 793 |
ONCE_REWRITE_TAC[EQ_SYM_EQ] THEN |
| 794 |
MATCH_MP_TAC SUM_EQ_SUPERSET THEN |
| 795 |
REWRITE_TAC[FINITE_SING; SUBSET; IN_SING; IN_NUMSEG] THEN |
| 796 |
REPEAT CONJ_TAC THEN REPEAT STRIP_TAC THEN ASM_REWRITE_TAC[] THEN TRY ARITH_TAC THEN |
| 797 |
REWRITE_TAC[SUM_SING]; |
| 798 |
ALL_TAC |
| 799 |
] THEN |
| 800 |
MATCH_MP_TAC SUM_LE_NUMSEG THEN REWRITE_TAC[IN_SING] THEN REPEAT STRIP_TAC THEN |
| 801 |
REWRITE_TAC[REAL_POW_ONE; REAL_MUL_RID] THEN |
| 802 |
COND_CASES_TAC THENL [ ASM_REWRITE_TAC[REAL_LE_REFL]; ALL_TAC ] THEN |
| 803 |
MATCH_MP_TAC REAL_LE_MUL THEN REWRITE_TAC[REAL_POS] THEN |
| 804 |
MATCH_MP_TAC REAL_POW_LE THEN ASM_SIMP_TAC[REAL_ARITH `&0 < e ==> &0 <= e`]);; |
| 805 |
|
| 806 |
let real_summable_lmul_eq = prove |
| 807 |
(`!c f s. ~(c = &0) |
| 808 |
==> (real_summable s (\i. c * f i) <=> real_summable s f)`, |
| 809 |
REPEAT STRIP_TAC THEN EQ_TAC THEN DISCH_TAC THENL [ |
| 810 |
SUBGOAL_THEN `f = (\i:num. inv c * c * f i)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [ |
| 811 |
ASM_SIMP_TAC[REAL_MUL_ASSOC; REAL_MUL_LINV; REAL_MUL_LID; ETA_AX]; |
| 812 |
ALL_TAC |
| 813 |
] THEN |
| 814 |
MATCH_MP_TAC REAL_SUMMABLE_LMUL THEN ASM_REWRITE_TAC[]; |
| 815 |
ALL_TAC |
| 816 |
] THEN |
| 817 |
MATCH_MP_TAC REAL_SUMMABLE_LMUL THEN ASM_REWRITE_TAC[]);; |
| 818 |
|
| 819 |
let summable_power_series_shift = prove |
| 820 |
(`!k s a x. real_summable s (\i. a i * x pow i) |
| 821 |
==> real_summable s (\i. a i * x pow (i - k))`, |
| 822 |
REPEAT STRIP_TAC THEN |
| 823 |
ASM_CASES_TAC `x = &0` THENL [ |
| 824 |
MATCH_MP_TAC REAL_SUMMABLE_COMPARISON THEN |
| 825 |
EXISTS_TAC `\n:num. &0` THEN CONJ_TAC THENL [ REWRITE_TAC[REAL_SUMMABLE_0]; ALL_TAC ] THEN |
| 826 |
EXISTS_TAC `k + 2` THEN REPEAT STRIP_TAC THEN |
| 827 |
ASM_SIMP_TAC[REAL_POW_ZERO; ARITH_RULE `n >= k + 2 ==> ~(n - k = 0)`] THEN |
| 828 |
REAL_ARITH_TAC; |
| 829 |
ALL_TAC |
| 830 |
] THEN |
| 831 |
MP_TAC (SPEC `x pow k` real_summable_lmul_eq) THEN ASM_SIMP_TAC[REAL_POW_NZ] THEN |
| 832 |
DISCH_THEN (fun th -> ONCE_REWRITE_TAC[GSYM th]) THEN REWRITE_TAC[] THEN |
| 833 |
MP_TAC (SPECL[`\i. a i * x pow i`; `\i. x pow k * a i * x pow (i - k)`; `s:num->bool`] REAL_SUMMABLE_IFF_EVENTUALLY) THEN |
| 834 |
ANTS_TAC THENL [ |
| 835 |
EXISTS_TAC `k:num` THEN REPEAT STRIP_TAC THEN REWRITE_TAC[] THEN |
| 836 |
ASM_SIMP_TAC[REAL_POW_SUB] THEN |
| 837 |
REWRITE_TAC[REAL_ARITH `x * a * x2 / x = (x / x) * a * x2`] THEN |
| 838 |
ASM_SIMP_TAC[REAL_DIV_REFL; REAL_POW_NZ; REAL_MUL_LID]; |
| 839 |
ALL_TAC |
| 840 |
] THEN |
| 841 |
ASM_SIMP_TAC[]);; |
| 842 |
|
| 843 |
let power_sum_derivative_shift_lemma = prove |
| 844 |
(`!a s n. |
| 845 |
sum ((s DIFF {0}) INTER (0..n)) (\i. &i * a i) |
| 846 |
= sum (s INTER (0..n)) (\i. &i * a i)`, |
| 847 |
REPEAT GEN_TAC THEN MATCH_MP_TAC EQ_SYM THEN MATCH_MP_TAC SUM_EQ_SUPERSET THEN |
| 848 |
ASM_SIMP_TAC[FINITE_INTER; FINITE_NUMSEG; SUBSET_INTER; INTER_SUBSET] THEN |
| 849 |
CONJ_TAC THENL [ |
| 850 |
SIMP_TAC[SUBSET; IN_INTER; IN_DIFF]; |
| 851 |
ALL_TAC |
| 852 |
] THEN |
| 853 |
REWRITE_TAC[IN_INTER; IN_DIFF; DE_MORGAN_THM; IN_SING] THEN |
| 854 |
REWRITE_TAC[TAUT `((A /\ B) /\ ((~A \/ C) \/ ~B)) <=> A /\ B /\ C`] THEN |
| 855 |
REPEAT STRIP_TAC THEN ASM_REWRITE_TAC[REAL_MUL_LZERO]);; |
| 856 |
|
| 857 |
let power_sum_derivative_shift_lemma2 = prove |
| 858 |
(`!a s n. 0 < n |
| 859 |
==> sum ((IMAGE PRE (s DIFF {0})) INTER (0..PRE n)) (\i. &(SUC i) * a (SUC i)) |
| 860 |
= sum (s INTER (0..n)) (\i. &i * a i)`, |
| 861 |
REPEAT STRIP_TAC THEN MATCH_MP_TAC EQ_SYM THEN |
| 862 |
SUBGOAL_THEN `IMAGE PRE (s DIFF {0}) INTER (0..PRE n) = IMAGE PRE ((s DIFF {0}) INTER (0..n))` (fun th -> REWRITE_TAC[th]) THENL [ |
| 863 |
REWRITE_TAC[EXTENSION; IN_IMAGE; IN_INTER; IN_DIFF; IN_NUMSEG; IN_SING] THEN |
| 864 |
GEN_TAC THEN EQ_TAC THEN REPEAT STRIP_TAC THENL [ |
| 865 |
EXISTS_TAC `x':num` THEN ASM_REWRITE_TAC[] THEN ASM_ARITH_TAC; |
| 866 |
EXISTS_TAC `x':num` THEN ASM_REWRITE_TAC[] THEN ARITH_TAC; |
| 867 |
REWRITE_TAC[LE_0]; |
| 868 |
ASM_ARITH_TAC; |
| 869 |
]; |
| 870 |
ALL_TAC |
| 871 |
] THEN |
| 872 |
ABBREV_TAC `t = (s DIFF {0}) INTER (0..n)` THEN |
| 873 |
ONCE_REWRITE_TAC[GSYM power_sum_derivative_shift_lemma] THEN |
| 874 |
ASM_REWRITE_TAC[] THEN |
| 875 |
MP_TAC (ISPECL[`PRE`; `\i. &(SUC i) * a (SUC i)`; `t:num->bool`] SUM_IMAGE) THEN |
| 876 |
ANTS_TAC THENL [ |
| 877 |
REPEAT GEN_TAC THEN EXPAND_TAC "t" THEN |
| 878 |
REWRITE_TAC[IN_INTER; IN_DIFF; IN_SING] THEN ARITH_TAC; |
| 879 |
ALL_TAC |
| 880 |
] THEN |
| 881 |
DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN |
| 882 |
MATCH_MP_TAC SUM_EQ THEN GEN_TAC THEN EXPAND_TAC "t" THEN |
| 883 |
REWRITE_TAC[IN_DIFF; IN_INTER; IN_SING; o_THM] THEN STRIP_TAC THEN |
| 884 |
ASM_SIMP_TAC[ARITH_RULE `~(x = 0) ==> SUC (PRE x) = x`]);; |
| 885 |
|
| 886 |
let power_sum_derivative_shift_lemma3 = prove |
| 887 |
(`!a s n x. 0 < n |
| 888 |
==> sum ((IMAGE PRE (s DIFF {0})) INTER (0..PRE n)) (\i. (&(SUC i) * a (SUC i)) * x pow i) |
| 889 |
= sum (s INTER (0..n)) (\i. (&i * a i) * x pow (i - 1))`, |
| 890 |
REPEAT STRIP_TAC THEN |
| 891 |
MP_TAC (SPECL[`\i. a i * x pow (i - 1)`; `s:num->bool`; `n:num`] power_sum_derivative_shift_lemma2) THEN |
| 892 |
ASM_REWRITE_TAC[ARITH_RULE `SUC i - 1 = i`; REAL_MUL_ASSOC]);; |
| 893 |
|
| 894 |
let power_series_derivative_shift_lemma = prove |
| 895 |
(`!a s l. |
| 896 |
((\i. &i * a i) real_sums l) s <=> ((\i. &i * a i) real_sums l) (s DIFF {0})`, |
| 897 |
REPEAT GEN_TAC THEN REWRITE_TAC[real_sums] THEN |
| 898 |
REWRITE_TAC[power_sum_derivative_shift_lemma]);; |
| 899 |
|
| 900 |
let power_series_derivative_shift = prove |
| 901 |
(`!a s x l. |
| 902 |
((\i. (&i * a i) * x pow (i - 1)) real_sums l) s |
| 903 |
<=> ((\i. (&(SUC i) * a (SUC i)) * x pow i) real_sums l) (IMAGE PRE (s DIFF {0}))`, |
| 904 |
REPEAT GEN_TAC THEN |
| 905 |
ABBREV_TAC `t = IMAGE PRE (s DIFF {0})` THEN |
| 906 |
SUBGOAL_THEN `(\i. (&(SUC i) * a (SUC i)) * x pow i) = (\i. (&i * a i) * x pow (i - 1)) o SUC` (fun th -> REWRITE_TAC[th]) THENL [ |
| 907 |
REWRITE_TAC[FUN_EQ_THM; o_THM; ARITH_RULE `SUC n - 1 = n`; REAL_MUL_ASSOC]; |
| 908 |
ALL_TAC |
| 909 |
] THEN |
| 910 |
MP_TAC (SPECL [`\i. (&i * a i) * x pow (i - 1)`; `SUC`; `t:num->bool`] real_sums_image) THEN |
| 911 |
REWRITE_TAC[ARITH_RULE `SUC n < SUC (n + 1)`] THEN |
| 912 |
DISCH_THEN (fun th -> REWRITE_TAC[GSYM th]) THEN |
| 913 |
REWRITE_TAC[GSYM REAL_MUL_ASSOC] THEN |
| 914 |
GEN_REWRITE_TAC LAND_CONV [power_series_derivative_shift_lemma] THEN |
| 915 |
AP_TERM_TAC THEN |
| 916 |
EXPAND_TAC "t" THEN |
| 917 |
REWRITE_TAC[EXTENSION; IN_DIFF; IN_IMAGE; IN_SING] THEN |
| 918 |
GEN_TAC THEN EQ_TAC THEN REPEAT STRIP_TAC THEN ASM_REWRITE_TAC[] THENL [ |
| 919 |
EXISTS_TAC `PRE x` THEN CONJ_TAC THEN TRY ASM_ARITH_TAC THEN |
| 920 |
EXISTS_TAC `x:num` THEN ASM_REWRITE_TAC[]; |
| 921 |
ASM_SIMP_TAC[ARITH_RULE `~(a = 0) ==> SUC (PRE a) = a`]; |
| 922 |
POP_ASSUM MP_TAC THEN ASM_REWRITE_TAC[] THEN ARITH_TAC |
| 923 |
]);; |
| 924 |
|
| 925 |
let summable_power_series_derivative = prove |
| 926 |
(`!a s y. real_summable s (\i. a i * y pow i) |
| 927 |
==> (!x. abs x < y ==> real_summable s (\i. (&i * a i) * x pow (i - 1)))`, |
| 928 |
REPEAT STRIP_TAC THEN |
| 929 |
MATCH_MP_TAC summable_power_series_shift THEN |
| 930 |
ASM_CASES_TAC `x = &0` THENL [ |
| 931 |
MATCH_MP_TAC REAL_SUMMABLE_COMPARISON THEN |
| 932 |
EXISTS_TAC `\n:num. &0` THEN CONJ_TAC THENL [ REWRITE_TAC[REAL_SUMMABLE_0]; ALL_TAC ] THEN |
| 933 |
EXISTS_TAC `2` THEN REPEAT STRIP_TAC THEN |
| 934 |
ASM_SIMP_TAC[REAL_POW_ZERO; ARITH_RULE `n >= 2 ==> ~(n = 0)`] THEN |
| 935 |
REAL_ARITH_TAC; |
| 936 |
ALL_TAC |
| 937 |
] THEN |
| 938 |
SUBGOAL_THEN `~(y = &0) /\ &0 < y /\ &0 < abs x /\ ~(abs x = &0)` ASSUME_TAC THENL [ |
| 939 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 940 |
ALL_TAC |
| 941 |
] THEN |
| 942 |
ABBREV_TAC `e = (y / (abs x) - &1) / &2` THEN |
| 943 |
SUBGOAL_THEN `&0 < e` ASSUME_TAC THENL [ |
| 944 |
EXPAND_TAC "e" THEN |
| 945 |
MATCH_MP_TAC REAL_LT_DIV THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THEN |
| 946 |
REWRITE_TAC[REAL_ARITH `&0 < a - b <=> b < a`] THEN |
| 947 |
ASM_SIMP_TAC[REAL_LT_RDIV_EQ; REAL_MUL_LID]; |
| 948 |
ALL_TAC |
| 949 |
] THEN |
| 950 |
SUBGOAL_THEN `abs (x * (&1 + e)) < y` ASSUME_TAC THENL [ |
| 951 |
ASM_SIMP_TAC[REAL_ABS_MUL; REAL_ARITH `&0 < e ==> abs (&1 + e) = &1 + e`] THEN |
| 952 |
EXPAND_TAC "e" THEN REWRITE_TAC[REAL_ARITH `x * (&1 + e) = x + x * e`] THEN |
| 953 |
ASM_SIMP_TAC[REAL_FIELD `!x. ~(x = &0) ==> x * (y / x - &1) / &2 = (y - x) / &2`] THEN |
| 954 |
UNDISCH_TAC `abs x < y` THEN REAL_ARITH_TAC; |
| 955 |
ALL_TAC |
| 956 |
] THEN |
| 957 |
MATCH_MP_TAC REAL_SUMMABLE_COMPARISON THEN |
| 958 |
EXISTS_TAC `\i. abs (a i * (x * (&1 + e)) pow i)` THEN |
| 959 |
CONJ_TAC THENL [ |
| 960 |
MATCH_MP_TAC REAL_POWER_SERIES_CONV_IMP_ABSCONV THEN |
| 961 |
EXISTS_TAC `y:real` THEN ASM_REWRITE_TAC[] THEN |
| 962 |
MP_TAC (REAL_ARITH `abs x < y ==> abs y = y`) THEN |
| 963 |
ASM_SIMP_TAC[]; |
| 964 |
ALL_TAC |
| 965 |
] THEN |
| 966 |
MP_TAC (SPEC `e:real` n_le_pow_lemma) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN |
| 967 |
EXISTS_TAC `N:num` THEN REPEAT STRIP_TAC THEN |
| 968 |
REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_POW; REAL_POW_MUL] THEN |
| 969 |
REWRITE_TAC[REAL_ARITH `abs ((a:num->real) n) * t pow n * y = (y * abs (a n)) * t pow n`] THEN |
| 970 |
MATCH_MP_TAC REAL_LE_RMUL THEN CONJ_TAC THENL [ |
| 971 |
MATCH_MP_TAC REAL_LE_RMUL THEN REWRITE_TAC[REAL_ABS_POS] THEN |
| 972 |
ASM_SIMP_TAC[REAL_ARITH `&0 < e ==> abs (&1 + e) = &1 + e`] THEN |
| 973 |
REWRITE_TAC[REAL_ARITH `abs (&n) = &n`] THEN |
| 974 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[GSYM GE]; |
| 975 |
ALL_TAC |
| 976 |
] THEN |
| 977 |
MATCH_MP_TAC REAL_POW_LE THEN REWRITE_TAC[REAL_ABS_POS]);; |
| 978 |
|
| 979 |
let power_series_has_derivative = prove |
| 980 |
(`!f a s r. |
| 981 |
(!x. abs x < r ==> ((\i. a i * x pow i) real_sums f x) s) |
| 982 |
==> ?f'. (!x. abs x < r ==> (f has_real_derivative f' x) (atreal x) /\ |
| 983 |
((\i. (&i * a i) * x pow (i - 1)) real_sums f' x) s)`, |
| 984 |
REPEAT STRIP_TAC THEN |
| 985 |
SUBGOAL_THEN `(!w. &0 < w /\ abs w < r /\ w < r /\ abs w < abs r ==> |
| 986 |
?f'. (!x. abs x < w ==> (f has_real_derivative f' x) (atreal x) /\ |
| 987 |
((\i. (&i * a i) * x pow (i - 1)) real_sums f' x) s)) |
| 988 |
==> ?f'. (!x. abs x < r ==> (f has_real_derivative f' x) (atreal x) /\ |
| 989 |
((\i. (&i * a i) * x pow (i - 1)) real_sums f' x) s)` MATCH_MP_TAC THENL [ |
| 990 |
REWRITE_TAC[SKOLEM_THM_GEN] THEN |
| 991 |
DISCH_THEN (X_CHOOSE_THEN `p:real->real->real` ASSUME_TAC) THEN |
| 992 |
EXISTS_TAC `\x. (p:real->real->real) ((abs x + r) / &2) x` THEN GEN_TAC THEN DISCH_TAC THEN |
| 993 |
FIRST_X_ASSUM (MP_TAC o SPEC `(abs x + r) / &2`) THEN ANTS_TAC THENL [ |
| 994 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 995 |
ALL_TAC |
| 996 |
] THEN |
| 997 |
REWRITE_TAC[] THEN |
| 998 |
DISCH_THEN MATCH_MP_TAC THEN |
| 999 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 1000 |
ALL_TAC |
| 1001 |
] THEN |
| 1002 |
GEN_TAC THEN DISCH_THEN (LABEL_TAC "hw") THEN |
| 1003 |
MP_TAC (SPECL[`real_interval (--w, w)`; `\i x. a i * x pow i`; `\i x. (&i * a i) * x pow (i - 1)`; `\x. real_infsum s (\i. (&i * a i) * x pow (i - 1))`; `s:num->bool`] HAS_REAL_DERIVATIVE_SERIES) THEN |
| 1004 |
REWRITE_TAC[IS_REALINTERVAL_INTERVAL; IN_REAL_INTERVAL] THEN |
| 1005 |
ANTS_TAC THEN REPEAT STRIP_TAC THENL [ |
| 1006 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_ATREAL_WITHIN THEN |
| 1007 |
REAL_DIFF_TAC THEN REAL_ARITH_TAC; |
| 1008 |
|
| 1009 |
ABBREV_TAC `y = (r + w) / &2` THEN |
| 1010 |
ABBREV_TAC `y2 = (y + r) / &2` THEN |
| 1011 |
SUBGOAL_THEN `&0 < y /\ abs y < r /\ w < y /\ abs w < y /\ abs w < abs y /\ &0 < y2 /\ abs y2 < r /\ y < y2 /\ abs y < abs y2 /\ abs y < y2` (LABEL_TAC "hy") THENL [ |
| 1012 |
REMOVE_THEN "hw" MP_TAC THEN EXPAND_TAC "y2" THEN EXPAND_TAC "y" THEN REAL_ARITH_TAC; |
| 1013 |
ALL_TAC |
| 1014 |
] THEN |
| 1015 |
MP_TAC (SPECL[`a:num->real`; `s:num->bool`; `y2:real`] summable_power_series_derivative) THEN |
| 1016 |
ANTS_TAC THENL [ |
| 1017 |
REWRITE_TAC[real_summable] THEN EXISTS_TAC `(f:real->real) y2` THEN |
| 1018 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]; |
| 1019 |
ALL_TAC |
| 1020 |
] THEN |
| 1021 |
DISCH_TAC THEN |
| 1022 |
MP_TAC (SPECL[`\i. &(SUC i) * a (SUC i)`; `IMAGE PRE (s DIFF {0})`; `w:real`; `y:real`] power_series_uniform) THEN REWRITE_TAC[] THEN |
| 1023 |
ANTS_TAC THENL [ |
| 1024 |
REWRITE_TAC[real_summable; GSYM power_series_derivative_shift] THEN |
| 1025 |
ASM_REWRITE_TAC[GSYM real_summable] THEN |
| 1026 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]; |
| 1027 |
ALL_TAC |
| 1028 |
] THEN |
| 1029 |
DISCH_THEN (MP_TAC o SPEC `e:real`) THEN ASM_REWRITE_TAC[] THEN |
| 1030 |
REPEAT STRIP_TAC THEN |
| 1031 |
EXISTS_TAC `N + 1` THEN GEN_TAC THEN X_GEN_TAC `t:real` THEN DISCH_TAC THEN |
| 1032 |
SUBGOAL_THEN `0 < n` ASSUME_TAC THENL [ POP_ASSUM MP_TAC THEN ARITH_TAC; ALL_TAC ] THEN |
| 1033 |
FIRST_X_ASSUM (MP_TAC o SPECL[`PRE n`; `t:real`]) THEN |
| 1034 |
ANTS_TAC THENL [ |
| 1035 |
CONJ_TAC THENL [ POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN ARITH_TAC; ALL_TAC ] THEN |
| 1036 |
REWRITE_TAC[IN_REAL_INTERVAL] THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN |
| 1037 |
REAL_ARITH_TAC; |
| 1038 |
ALL_TAC |
| 1039 |
] THEN |
| 1040 |
ASM_SIMP_TAC[power_sum_derivative_shift_lemma3] THEN |
| 1041 |
REWRITE_TAC[real_infsum] THEN |
| 1042 |
SIMP_TAC[power_series_derivative_shift; REAL_LT_IMP_LE]; |
| 1043 |
EXISTS_TAC `&0` THEN REWRITE_TAC[RIGHT_EXISTS_AND_THM] THEN |
| 1044 |
CONJ_TAC THENL [ POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; ALL_TAC ] THEN |
| 1045 |
MATCH_MP_TAC REAL_SERIES_COMPARISON THEN |
| 1046 |
EXISTS_TAC `\n:num. &0` THEN CONJ_TAC THENL [ |
| 1047 |
EXISTS_TAC `&0` THEN REWRITE_TAC[REAL_SERIES_0]; |
| 1048 |
ALL_TAC |
| 1049 |
] THEN |
| 1050 |
EXISTS_TAC `1` THEN REPEAT STRIP_TAC THEN |
| 1051 |
ASM_SIMP_TAC[REAL_POW_ZERO; ARITH_RULE `n >= 1 ==> ~(n = 0)`] THEN |
| 1052 |
REAL_ARITH_TAC; |
| 1053 |
ALL_TAC |
| 1054 |
] THEN |
| 1055 |
EXISTS_TAC `\x. real_infsum s (\i. (&i * a i) * x pow (i - 1))` THEN |
| 1056 |
REPEAT STRIP_TAC THENL [ |
| 1057 |
SUBGOAL_THEN `!y. abs y < w ==> (g:real->real) y = f y` (LABEL_TAC "eq") THENL [ |
| 1058 |
REPEAT STRIP_TAC THEN |
| 1059 |
FIRST_X_ASSUM (MP_TAC o SPEC `y:real`) THEN ANTS_TAC THENL [ |
| 1060 |
POP_ASSUM MP_TAC THEN REMOVE_THEN "hw" MP_TAC THEN REAL_ARITH_TAC; |
| 1061 |
ALL_TAC |
| 1062 |
] THEN |
| 1063 |
STRIP_TAC THEN POP_ASSUM (K ALL_TAC) THEN |
| 1064 |
MATCH_MP_TAC REAL_SERIES_UNIQUE THEN |
| 1065 |
MAP_EVERY EXISTS_TAC [`\n. a n * y pow n`; `s:num->bool`] THEN |
| 1066 |
FIRST_X_ASSUM (MP_TAC o SPEC `y:real`) THEN ANTS_TAC THENL [ |
| 1067 |
REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC; |
| 1068 |
ALL_TAC |
| 1069 |
] THEN |
| 1070 |
ASM_SIMP_TAC[]; |
| 1071 |
ALL_TAC |
| 1072 |
] THEN |
| 1073 |
POP_ASSUM MP_TAC THEN |
| 1074 |
FIRST_X_ASSUM (MP_TAC o SPEC `x:real`) THEN ANTS_TAC THENL [ |
| 1075 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 1076 |
ALL_TAC |
| 1077 |
] THEN |
| 1078 |
REPEAT STRIP_TAC THEN |
| 1079 |
MATCH_MP_TAC HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL THEN |
| 1080 |
MAP_EVERY EXISTS_TAC [`g:real->real`; `(w - abs x) / &2`] THEN |
| 1081 |
CONJ_TAC THENL [ |
| 1082 |
UNDISCH_TAC `abs x < w` THEN REAL_ARITH_TAC; |
| 1083 |
ALL_TAC |
| 1084 |
] THEN |
| 1085 |
CONJ_TAC THENL [ |
| 1086 |
REPEAT STRIP_TAC THEN FIRST_X_ASSUM MATCH_MP_TAC THEN |
| 1087 |
POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 1088 |
ALL_TAC |
| 1089 |
] THEN |
| 1090 |
SUBGOAL_THEN `x IN real_interval (--w, w) /\ real_open (real_interval (--w, w))` ASSUME_TAC THENL [ |
| 1091 |
REWRITE_TAC[REAL_OPEN_REAL_INTERVAL; IN_REAL_INTERVAL] THEN |
| 1092 |
UNDISCH_TAC `abs x < w` THEN REAL_ARITH_TAC; |
| 1093 |
ALL_TAC |
| 1094 |
] THEN |
| 1095 |
POP_ASSUM (MP_TAC o MATCH_MP HAS_REAL_DERIVATIVE_WITHIN_REAL_OPEN) THEN |
| 1096 |
DISCH_THEN (fun th -> ONCE_REWRITE_TAC[GSYM th]) THEN |
| 1097 |
ASM_REWRITE_TAC[]; |
| 1098 |
ALL_TAC |
| 1099 |
] THEN |
| 1100 |
REWRITE_TAC[REAL_SUMS_INFSUM] THEN |
| 1101 |
MP_TAC (SPECL[`a:num->real`; `s:num->bool`; `w:real`] summable_power_series_derivative) THEN |
| 1102 |
ANTS_TAC THENL [ |
| 1103 |
REWRITE_TAC[real_summable] THEN EXISTS_TAC `(f:real->real) w` THEN |
| 1104 |
FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]; |
| 1105 |
ALL_TAC |
| 1106 |
] THEN |
| 1107 |
DISCH_THEN MATCH_MP_TAC THEN |
| 1108 |
ASM_REWRITE_TAC[]);; |
| 1109 |
|
| 1110 |
let power_series_has_derivative2 = prove |
| 1111 |
(`!f a r. |
| 1112 |
(!x. abs x < r ==> ((\i. a i * x pow i) real_sums f x) (:num)) |
| 1113 |
==> ?f'. (!x. abs x < r ==> |
| 1114 |
(f has_real_derivative f' x) (atreal x) /\ |
| 1115 |
((\i. (&(SUC i) * a (SUC i)) * x pow i) real_sums f' x) (:num))`, |
| 1116 |
REPEAT GEN_TAC THEN DISCH_THEN (MP_TAC o MATCH_MP power_series_has_derivative) THEN |
| 1117 |
REWRITE_TAC[power_series_derivative_shift] THEN |
| 1118 |
SUBGOAL_THEN `IMAGE PRE ((:num) DIFF {0}) = (:num)` (fun th -> REWRITE_TAC[th]) THEN |
| 1119 |
REWRITE_TAC[EXTENSION; IN_IMAGE; IN_UNIV; IN_DIFF; IN_SING] THEN GEN_TAC THEN |
| 1120 |
EXISTS_TAC `SUC x` THEN ARITH_TAC);; |
| 1121 |
|
| 1122 |
(* i * x^i *) |
| 1123 |
|
| 1124 |
let real_sums_i_xi = prove |
| 1125 |
(`!x. abs x < &1 |
| 1126 |
==> ((\i. &i * x pow i) real_sums (x / (&1 - x) pow 2)) (:num)`, |
| 1127 |
REPEAT STRIP_TAC THEN |
| 1128 |
MP_TAC (SPECL[`\x. &1 / (&1 - x)`; `\i:num. &1`; `(:num)`; `&1`] power_series_has_derivative) THEN |
| 1129 |
ANTS_TAC THENL [ |
| 1130 |
GEN_TAC THEN DISCH_THEN (MP_TAC o SPEC `0` o MATCH_MP REAL_SUMS_GP) THEN |
| 1131 |
REWRITE_TAC[REAL_MUL_LID; real_pow; FROM_0]; |
| 1132 |
ALL_TAC |
| 1133 |
] THEN |
| 1134 |
STRIP_TAC THEN POP_ASSUM (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN |
| 1135 |
POP_ASSUM MP_TAC THEN POP_ASSUM (LABEL_TAC "d") THEN DISCH_THEN (LABEL_TAC "sums") THEN |
| 1136 |
SUBGOAL_THEN `(f':real->real) x = &1 / (&1 - x) pow 2` ASSUME_TAC THENL [ |
| 1137 |
MATCH_MP_TAC REAL_DERIVATIVE_UNIQUE_ATREAL THEN |
| 1138 |
MAP_EVERY EXISTS_TAC [`\x. &1 / (&1 - x)`; `x:real`] THEN ASM_REWRITE_TAC[] THEN |
| 1139 |
REAL_DIFF_TAC THEN |
| 1140 |
ASM_SIMP_TAC[REAL_ARITH `abs x < &1 ==> ~(&1 - x = &0)`] THEN |
| 1141 |
REAL_ARITH_TAC; |
| 1142 |
ALL_TAC |
| 1143 |
] THEN |
| 1144 |
REMOVE_THEN "sums" MP_TAC THEN ASM_REWRITE_TAC[] THEN |
| 1145 |
DISCH_THEN (MP_TAC o SPEC `x:real` o MATCH_MP REAL_SERIES_LMUL) THEN |
| 1146 |
REWRITE_TAC[real_div; REAL_MUL_ASSOC; REAL_MUL_RID] THEN |
| 1147 |
SUBGOAL_THEN `!n. (x * &n) * x pow (n - 1) = &n * x pow n` (fun th -> REWRITE_TAC[th]) THEN |
| 1148 |
GEN_TAC THEN ASM_CASES_TAC `n = 0` THENL [ |
| 1149 |
ASM_REWRITE_TAC[REAL_MUL_LZERO; REAL_MUL_RZERO]; |
| 1150 |
REWRITE_TAC[REAL_ARITH `(x * &n) * t = &n * (x * t)`] THEN |
| 1151 |
REWRITE_TAC[GSYM real_pow] THEN |
| 1152 |
ASM_SIMP_TAC[ARITH_RULE `~(n = 0) ==> SUC (n - 1) = n`] |
| 1153 |
]);; |
| 1154 |
|
| 1155 |
let real_sums_neg_i_xi = prove |
| 1156 |
(`!x. abs x < &1 |
| 1157 |
==> ((\i. ((-- &1) pow i * &i) * x pow i) real_sums |
| 1158 |
--(x / (&1 + x) pow 2)) (:num)`, |
| 1159 |
REPEAT STRIP_TAC THEN |
| 1160 |
MP_TAC (SPEC `--x` real_sums_i_xi) THEN ANTS_TAC THENL [ |
| 1161 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 1162 |
ALL_TAC |
| 1163 |
] THEN |
| 1164 |
ONCE_REWRITE_TAC[REAL_ARITH `--x = -- &1 * x`] THEN |
| 1165 |
REWRITE_TAC[REAL_POW_MUL; REAL_POW_ONE; REAL_MUL_RID; REAL_ARITH `-- &1 * x = --x`] THEN |
| 1166 |
ONCE_REWRITE_TAC[REAL_ARITH `&i * a * b = (a * &i) * b`] THEN |
| 1167 |
REWRITE_TAC[REAL_ARITH `--x / a = --(x / a) /\ &1 - --x = &1 + x`]);; |
| 1168 |
|
| 1169 |
let real_sums_neg_xi = prove |
| 1170 |
(`!x. abs x < &1 |
| 1171 |
==> ((\i. (-- &1) pow i * x pow i) real_sums &1 / (&1 + x)) (:num)`, |
| 1172 |
REPEAT STRIP_TAC THEN |
| 1173 |
MP_TAC (SPECL [`0`; `--x`] REAL_SUMS_GP) THEN ANTS_TAC THENL [ |
| 1174 |
POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; |
| 1175 |
ALL_TAC |
| 1176 |
] THEN |
| 1177 |
ONCE_REWRITE_TAC[REAL_ARITH `--x = -- &1 * x`] THEN |
| 1178 |
REWRITE_TAC[REAL_POW_MUL; REAL_POW_ONE; REAL_MUL_RID; REAL_ARITH `-- &1 * x = --x`] THEN |
| 1179 |
REWRITE_TAC[real_pow; REAL_MUL_LID; REAL_ARITH `a - --b = a + b`; FROM_0]);; |
| 1180 |
|
| 1181 |
(* exp *) |
| 1182 |
|
| 1183 |
let exp_series = prove |
| 1184 |
(`!x. ((\k. &1 / &(FACT k) * x pow k) real_sums exp x) (:num)`, |
| 1185 |
GEN_TAC THEN REWRITE_TAC[REAL_SUMS] THEN |
| 1186 |
MP_TAC (SPECL[`Cx x`] CEXP_CONVERGES) THEN |
| 1187 |
REWRITE_TAC[GSYM CX_EXP] THEN |
| 1188 |
SUBGOAL_THEN `!n. Cx x pow n / Cx (&(FACT n)) = Cx (&1 / &(FACT n) * x pow n)` ASSUME_TAC THENL [ |
| 1189 |
REWRITE_TAC[REAL_ARITH `&1 / a * b = b / a`; CX_DIV; CX_POW]; |
| 1190 |
ALL_TAC |
| 1191 |
] THEN |
| 1192 |
ASM_REWRITE_TAC[SERIES_CX_LIFT] THEN |
| 1193 |
SUBGOAL_THEN `lift o (\k. &1 / &(FACT k) * x pow k) = \k. lift (&1 / &(FACT k) * x pow k)` ASSUME_TAC THENL [ |
| 1194 |
REWRITE_TAC[FUN_EQ_THM; o_THM]; |
| 1195 |
ALL_TAC |
| 1196 |
] THEN |
| 1197 |
ASM_REWRITE_TAC[FROM_0]);; |
| 1198 |
|
| 1199 |
let exp_infsum = prove |
| 1200 |
(`!x. real_infsum (from 0) (\k. &1 / &(FACT k) * x pow k) = exp x`, |
| 1201 |
GEN_TAC THEN MP_TAC (MATCH_MP REAL_INFSUM_UNIQUE (SPEC_ALL exp_series)) THEN |
| 1202 |
REWRITE_TAC[FROM_0]);; |
| 1203 |
|
| 1204 |
(* log *) |
| 1205 |
|
| 1206 |
let log_derivative_series = prove |
| 1207 |
(`!x. abs x < &1 |
| 1208 |
==> ((\k. (-- &1) pow k * x pow k) real_sums inv (&1 + x)) (:num)`, |
| 1209 |
REPEAT STRIP_TAC THEN |
| 1210 |
MP_TAC (SPECL[`0`; `-- &1 * x`] REAL_SUMS_GP) THEN |
| 1211 |
ASM_REWRITE_TAC[REAL_POW_MUL; real_pow; REAL_ARITH `abs (-- &1 * x) = abs x`] THEN |
| 1212 |
REWRITE_TAC[FROM_0; REAL_ARITH `a - -- &1 * x = a + x`; REAL_MUL_LID; real_div]);; |
| 1213 |
|
| 1214 |
let log_series = prove |
| 1215 |
(`!x. abs x < &1 |
| 1216 |
==> ((\k. (-- &1) pow k / &(k + 1) * x pow (k + 1)) real_sums log (&1 + x)) (:num)`, |
| 1217 |
REPEAT STRIP_TAC THEN |
| 1218 |
MP_TAC (SPECL[`\x. log (&1 + x)`; `\x. inv (&1 + x)`; `\k. (-- &1) pow k`; `(:num)`; `&1`] |
| 1219 |
power_series_integral2) THEN |
| 1220 |
ANTS_TAC THEN REPEAT STRIP_TAC THEN REWRITE_TAC[] THENL [ |
| 1221 |
REAL_DIFF_TAC THEN ASM_ARITH_TAC; |
| 1222 |
ASM_SIMP_TAC[log_derivative_series]; |
| 1223 |
ALL_TAC |
| 1224 |
] THEN |
| 1225 |
FIRST_X_ASSUM (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN |
| 1226 |
REWRITE_TAC[REAL_ADD_RID; LOG_1; REAL_SUB_RZERO] THEN |
| 1227 |
REWRITE_TAC[REAL_ARITH `a * x / b = a / b * x`]);; |
| 1228 |
|
| 1229 |
let log_infsum = prove |
| 1230 |
(`!x. abs x < &1 ==> |
| 1231 |
real_infsum (from 0) (\k. ((-- &1) pow k / &(k + 1)) * x pow (k + 1)) = log (&1 + x)`, |
| 1232 |
GEN_TAC THEN DISCH_THEN (MP_TAC o MATCH_MP REAL_INFSUM_UNIQUE o MATCH_MP log_series) THEN |
| 1233 |
REWRITE_TAC[FROM_0]);; |
| 1234 |
|
| 1235 |
(* atn *) |
| 1236 |
|
| 1237 |
let atn_derivative_series = prove |
| 1238 |
(`!x. abs x < &1 |
| 1239 |
==> ((\k. (if EVEN k then (-- &1) pow (k DIV 2) else &0) * x pow k) |
| 1240 |
real_sums inv (&1 + x pow 2)) (:num)`, |
| 1241 |
REPEAT STRIP_TAC THEN |
| 1242 |
MP_TAC (SPECL[`0`; `(-- &1) * x pow 2`] REAL_SUMS_GP) THEN |
| 1243 |
ANTS_TAC THENL [ |
| 1244 |
REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_POW; REAL_ARITH `abs (-- &1) = &1`; REAL_MUL_LID] THEN |
| 1245 |
ASM_REWRITE_TAC[ABS_SQUARE_LT_1; REAL_ABS_ABS]; |
| 1246 |
ALL_TAC |
| 1247 |
] THEN |
| 1248 |
REWRITE_TAC[COND_RAND; COND_RATOR; REAL_MUL_LZERO; real_sums_image_even; FROM_0] THEN |
| 1249 |
REWRITE_TAC[ARITH_RULE `(2 * k) DIV 2 = k`; REAL_POW_MUL; REAL_POW_POW] THEN |
| 1250 |
REWRITE_TAC[real_pow; real_div; MULT_0; REAL_MUL_LID; REAL_SUB_RNEG; REAL_MUL_LNEG]);; |
| 1251 |
|
| 1252 |
let atn_series = prove |
| 1253 |
(`!x. abs x < &1 |
| 1254 |
==> ((\k. ((-- &1) pow k) / &(2 * k + 1) * x pow (2 * k + 1)) |
| 1255 |
real_sums atn x) (:num)`, |
| 1256 |
REPEAT STRIP_TAC THEN |
| 1257 |
MP_TAC (SPECL[`atn`; `\x. inv (&1 + x pow 2)`; `\k. if EVEN k then (-- &1) pow (k DIV 2) else &0`; `(:num)`; `&1`] power_series_integral2) THEN |
| 1258 |
REWRITE_TAC[HAS_REAL_DERIVATIVE_ATN; atn_derivative_series] THEN |
| 1259 |
DISCH_THEN (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[ATN_0; REAL_SUB_RZERO] THEN |
| 1260 |
REWRITE_TAC[COND_RAND; COND_RATOR; REAL_MUL_LZERO; real_sums_image_even] THEN |
| 1261 |
REWRITE_TAC[ARITH_RULE `(2 * i) DIV 2 = i`; real_div; REAL_MUL_AC]);; |
| 1262 |
|
| 1263 |
let atn_infsum = prove |
| 1264 |
(`!x. abs x < &1 ==> |
| 1265 |
real_infsum (from 0) (\k. ((-- &1) pow k / &(2 * k + 1)) * x pow (2 * k + 1)) = atn x`, |
| 1266 |
GEN_TAC THEN DISCH_THEN (MP_TAC o MATCH_MP REAL_INFSUM_UNIQUE o MATCH_MP atn_series) THEN |
| 1267 |
REWRITE_TAC[FROM_0]);; |
| 1268 |
|
| 1269 |
|
| 1270 |
(* sin *) |
| 1271 |
|
| 1272 |
let sin_series = prove |
| 1273 |
(`!x. ((\k. ((-- &1) pow k / &(FACT (2 * k + 1))) * x pow (2 * k + 1)) real_sums sin x) (:num)`, |
| 1274 |
GEN_TAC THEN REWRITE_TAC[REAL_SUMS] THEN |
| 1275 |
MP_TAC (SPECL[`Cx x`] CSIN_CONVERGES) THEN |
| 1276 |
REWRITE_TAC[GSYM CX_SIN] THEN |
| 1277 |
SUBGOAL_THEN `!n. -- Cx (&1) pow n * Cx x pow (2 * n + 1) / Cx (&(FACT (2 * n + 1))) = Cx (((-- &1) pow n / &(FACT (2 * n + 1))) * x pow (2 * n + 1))` (fun th -> REWRITE_TAC[th]) THENL [ |
| 1278 |
REWRITE_TAC[CX_MUL; CX_POW; CX_DIV; CX_NEG; complex_div; COMPLEX_MUL_AC]; |
| 1279 |
ALL_TAC |
| 1280 |
] THEN |
| 1281 |
REWRITE_TAC[SERIES_CX_LIFT] THEN |
| 1282 |
SUBGOAL_THEN `lift o (\k. -- &1 pow k / &(FACT (2 * k + 1)) * x pow (2 * k + 1)) = \k. lift (-- &1 pow k / &(FACT (2 * k + 1)) * x pow (2 * k + 1))` (fun th -> SIMP_TAC[th; FROM_0]) THEN |
| 1283 |
REWRITE_TAC[FUN_EQ_THM; o_THM]);; |
| 1284 |
|
| 1285 |
let sin_infsum = prove |
| 1286 |
(`!x. real_infsum (from 0) (\k. ((-- &1) pow k / &(FACT(2 * k + 1))) * x pow (2 * k + 1)) = sin x`, |
| 1287 |
GEN_TAC THEN MP_TAC (MATCH_MP REAL_INFSUM_UNIQUE (SPEC_ALL sin_series)) THEN |
| 1288 |
REWRITE_TAC[FROM_0]);; |
| 1289 |
|
| 1290 |
(* cos *) |
| 1291 |
|
| 1292 |
let cos_series = prove |
| 1293 |
(`!x. ((\k. ((-- &1) pow k / &(FACT (2 * k))) * x pow (2 * k)) real_sums cos x) (:num)`, |
| 1294 |
GEN_TAC THEN REWRITE_TAC[REAL_SUMS] THEN |
| 1295 |
MP_TAC (SPECL[`Cx x`] CCOS_CONVERGES) THEN |
| 1296 |
REWRITE_TAC[GSYM CX_COS] THEN |
| 1297 |
SUBGOAL_THEN `!n. -- Cx (&1) pow n * Cx x pow (2 * n) / Cx (&(FACT (2 * n))) = Cx (((-- &1) pow n / &(FACT (2 * n))) * x pow (2 * n))` (fun th -> REWRITE_TAC[th]) THENL [ |
| 1298 |
REWRITE_TAC[CX_MUL; CX_POW; CX_DIV; CX_NEG; complex_div; COMPLEX_MUL_AC]; |
| 1299 |
ALL_TAC |
| 1300 |
] THEN |
| 1301 |
REWRITE_TAC[SERIES_CX_LIFT] THEN |
| 1302 |
SUBGOAL_THEN `lift o (\k. -- &1 pow k / &(FACT (2 * k)) * x pow (2 * k)) = \k. lift (-- &1 pow k / &(FACT (2 * k)) * x pow (2 * k))` (fun th -> SIMP_TAC[th; FROM_0]) THEN |
| 1303 |
REWRITE_TAC[FUN_EQ_THM; o_THM]);; |
| 1304 |
|
| 1305 |
let cos_infsum = prove |
| 1306 |
(`!x. real_infsum (from 0) (\k. ((-- &1) pow k / &(FACT(2 * k))) * x pow (2 * k)) = cos x`, |
| 1307 |
GEN_TAC THEN MP_TAC (MATCH_MP REAL_INFSUM_UNIQUE (SPEC_ALL cos_series)) THEN |
| 1308 |
REWRITE_TAC[FROM_0]);; |
| 1309 |
|
| 1310 |
end;; |