src/HOL/Library/Function_Growth.thy
changeset 61975 b4b11391c676
parent 61833 c601d3c76362
child 63040 eb4ddd18d635
equal deleted inserted replaced
61974:5b067c681989 61975:b4b11391c676
    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