equal
deleted
inserted
replaced
35 assumes "m \<ge> n" |
35 assumes "m \<ge> n" |
36 shows "a ^ (m - n) = (a ^ m) div (a ^ n)" |
36 shows "a ^ (m - n) = (a ^ m) div (a ^ n)" |
37 proof - |
37 proof - |
38 def q == "m - n" |
38 def q == "m - n" |
39 moreover with assms have "m = q + n" by (simp add: q_def) |
39 moreover with assms have "m = q + n" by (simp add: q_def) |
40 ultimately show ?thesis using `a \<noteq> 0` by (simp add: power_add) |
40 ultimately show ?thesis using \<open>a \<noteq> 0\<close> by (simp add: power_add) |
41 qed |
41 qed |
42 |
42 |
43 |
43 |
44 subsection \<open>Motivation\<close> |
44 subsection \<open>Motivation\<close> |
45 |
45 |
333 case False |
333 case False |
334 show ?thesis |
334 show ?thesis |
335 proof |
335 proof |
336 show "(\<lambda>n. f n + k) \<lesssim> f" |
336 show "(\<lambda>n. f n + k) \<lesssim> f" |
337 proof |
337 proof |
338 from `\<exists>n. f n > 0` obtain n where "f n > 0" .. |
338 from \<open>\<exists>n. f n > 0\<close> obtain n where "f n > 0" .. |
339 have "\<forall>m>n. f m + k \<le> Suc k * f m" |
339 have "\<forall>m>n. f m + k \<le> Suc k * f m" |
340 proof (rule allI, rule impI) |
340 proof (rule allI, rule impI) |
341 fix m |
341 fix m |
342 assume "n < m" |
342 assume "n < m" |
343 with `mono f` have "f n \<le> f m" |
343 with \<open>mono f\<close> have "f n \<le> f m" |
344 using less_imp_le_nat monoE by blast |
344 using less_imp_le_nat monoE by blast |
345 with `0 < f n` have "0 < f m" by auto |
345 with \<open>0 < f n\<close> have "0 < f m" by auto |
346 then obtain l where "f m = Suc l" by (cases "f m") simp_all |
346 then obtain l where "f m = Suc l" by (cases "f m") simp_all |
347 then show "f m + k \<le> Suc k * f m" by simp |
347 then show "f m + k \<le> Suc k * f m" by simp |
348 qed |
348 qed |
349 then show "\<exists>c>0. \<exists>n. \<forall>m>n. f m + k \<le> c * f m" by blast |
349 then show "\<exists>c>0. \<exists>n. \<forall>m>n. f m + k \<le> c * f m" by blast |
350 qed |
350 qed |
364 show "\<exists>n. 0 < f n" |
364 show "\<exists>n. 0 < f n" |
365 proof (rule ccontr) |
365 proof (rule ccontr) |
366 assume "\<not> (\<exists>n. 0 < f n)" |
366 assume "\<not> (\<exists>n. 0 < f n)" |
367 then have "\<And>n. f n = 0" by simp |
367 then have "\<And>n. f n = 0" by simp |
368 then have "f 0 = f 1" by simp |
368 then have "f 0 = f 1" by simp |
369 moreover from `strict_mono f` have "f 0 < f 1" |
369 moreover from \<open>strict_mono f\<close> have "f 0 < f 1" |
370 by (simp add: strict_mono_def) |
370 by (simp add: strict_mono_def) |
371 ultimately show False by simp |
371 ultimately show False by simp |
372 qed |
372 qed |
373 qed |
373 qed |
374 |
374 |