src/HOL/Analysis/Harmonic_Numbers.thy
changeset 66495 0b46bd081228
parent 66447 a1f5c5c26fa6
child 66554 19bf4d5966dc
equal deleted inserted replaced
66487:307c19f24d5c 66495:0b46bd081228
    36 
    36 
    37 lemma of_real_harm: "of_real (harm n) = harm n"
    37 lemma of_real_harm: "of_real (harm n) = harm n"
    38   unfolding harm_def by simp
    38   unfolding harm_def by simp
    39 
    39 
    40 lemma abs_harm [simp]: "(abs (harm n) :: real) = harm n"
    40 lemma abs_harm [simp]: "(abs (harm n) :: real) = harm n"
    41   using harm_nonneg[of n] by (rule abs_of_nonneg)    
    41   using harm_nonneg[of n] by (rule abs_of_nonneg)
    42 
    42 
    43 lemma norm_harm: "norm (harm n) = harm n"
    43 lemma norm_harm: "norm (harm n) = harm n"
    44   by (subst of_real_harm [symmetric]) (simp add: harm_nonneg)
    44   by (subst of_real_harm [symmetric]) (simp add: harm_nonneg)
    45 
    45 
    46 lemma harm_expand:
    46 lemma harm_expand:
    97 lemma harm_at_top: "filterlim (harm :: nat \<Rightarrow> real) at_top sequentially"
    97 lemma harm_at_top: "filterlim (harm :: nat \<Rightarrow> real) at_top sequentially"
    98 proof (rule filterlim_at_top_mono)
    98 proof (rule filterlim_at_top_mono)
    99   show "eventually (\<lambda>n. harm n \<ge> ln (real (Suc n))) at_top"
    99   show "eventually (\<lambda>n. harm n \<ge> ln (real (Suc n))) at_top"
   100     using ln_le_harm by (intro always_eventually allI) (simp_all add: add_ac)
   100     using ln_le_harm by (intro always_eventually allI) (simp_all add: add_ac)
   101   show "filterlim (\<lambda>n. ln (real (Suc n))) at_top sequentially"
   101   show "filterlim (\<lambda>n. ln (real (Suc n))) at_top sequentially"
   102     by (intro filterlim_compose[OF ln_at_top] filterlim_compose[OF filterlim_real_sequentially] 
   102     by (intro filterlim_compose[OF ln_at_top] filterlim_compose[OF filterlim_real_sequentially]
   103               filterlim_Suc)
   103               filterlim_Suc)
   104 qed
   104 qed
   105 
   105 
   106 
   106 
   107 subsection \<open>The Euler--Mascheroni constant\<close>
   107 subsection \<open>The Euler-Mascheroni constant\<close>
   108 
   108 
   109 text \<open>
   109 text \<open>
   110   The limit of the difference between the partial harmonic sum and the natural logarithm
   110   The limit of the difference between the partial harmonic sum and the natural logarithm
   111   (approximately 0.577216). This value occurs e.g. in the definition of the Gamma function.
   111   (approximately 0.577216). This value occurs e.g. in the definition of the Gamma function.
   112  \<close>
   112  \<close>
   248       by (induction n) (simp_all add: inverse_eq_divide)
   248       by (induction n) (simp_all add: inverse_eq_divide)
   249   qed
   249   qed
   250 qed
   250 qed
   251 
   251 
   252 
   252 
   253 subsection \<open>Bounds on the Euler--Mascheroni constant\<close>
   253 subsection \<open>Bounds on the Euler-Mascheroni constant\<close>
   254 
   254 
   255 (* TODO: Move? *)
   255 (* TODO: Move? *)
   256 lemma ln_inverse_approx_le:
   256 lemma ln_inverse_approx_le:
   257   assumes "(x::real) > 0" "a > 0"
   257   assumes "(x::real) > 0" "a > 0"
   258   shows   "ln (x + a) - ln x \<le> a * (inverse x + inverse (x + a))/2" (is "_ \<le> ?A")
   258   shows   "ln (x + a) - ln x \<le> a * (inverse x + inverse (x + a))/2" (is "_ \<le> ?A")
   293     also have "\<dots> = (t - x) * f' + inverse x" using assms
   293     also have "\<dots> = (t - x) * f' + inverse x" using assms
   294       by (simp add: f'_def divide_simps) (simp add: f'_def field_simps)
   294       by (simp add: f'_def divide_simps) (simp add: f'_def field_simps)
   295     finally show "inverse t \<le> (t - x) * f' + inverse x" .
   295     finally show "inverse t \<le> (t - x) * f' + inverse x" .
   296   qed
   296   qed
   297   hence "integral {x..x+a} inverse \<le> integral {x..x+a} ?f" using f'_nonpos assms
   297   hence "integral {x..x+a} inverse \<le> integral {x..x+a} ?f" using f'_nonpos assms
   298     by (intro integral_le has_integral_integrable[OF int1] has_integral_integrable[OF int2] ineq)
   298     by (blast intro: integral_le has_integral_integrable[OF int1] has_integral_integrable[OF int2] ineq)
   299   also have "\<dots> = ?A" using int1 by (rule integral_unique)
   299   also have "\<dots> = ?A" using int1 by (rule integral_unique)
   300   finally show ?thesis .
   300   finally show ?thesis .
   301 qed
   301 qed
   302 
   302 
   303 lemma ln_inverse_approx_ge:
   303 lemma ln_inverse_approx_ge:
   330       by (intro convex_on_imp_above_tangent[of "{0<..}"] convex_on_inverse)
   330       by (intro convex_on_imp_above_tangent[of "{0<..}"] convex_on_inverse)
   331          (auto simp: m_def interior_open f'_def power2_eq_square intro!: derivative_eq_intros)
   331          (auto simp: m_def interior_open f'_def power2_eq_square intro!: derivative_eq_intros)
   332     thus "(t - m) * f' + inverse m \<le> inverse t" by (simp add: algebra_simps)
   332     thus "(t - m) * f' + inverse m \<le> inverse t" by (simp add: algebra_simps)
   333   qed
   333   qed
   334   hence "integral {x..y} inverse \<ge> integral {x..y} (\<lambda>t. (t - m) * f' + inverse m)"
   334   hence "integral {x..y} inverse \<ge> integral {x..y} (\<lambda>t. (t - m) * f' + inverse m)"
   335     using int1 int2 by (intro integral_le has_integral_integrable)
   335     using int1 int2 by (blast intro: integral_le has_integral_integrable)
   336   also have "integral {x..y} (\<lambda>t. (t - m) * f' + inverse m) = ?A"
   336   also have "integral {x..y} (\<lambda>t. (t - m) * f' + inverse m) = ?A"
   337     using integral_unique[OF int1] by simp
   337     using integral_unique[OF int1] by simp
   338   finally show ?thesis .
   338   finally show ?thesis .
   339 qed
   339 qed
   340 
   340 
   357     unfolding inv_def
   357     unfolding inv_def
   358     by (intro sums_divide telescope_sums' LIMSEQ_ignore_initial_segment LIMSEQ_inverse_real_of_nat)
   358     by (intro sums_divide telescope_sums' LIMSEQ_ignore_initial_segment LIMSEQ_inverse_real_of_nat)
   359   from euler_mascheroni_sum_real have "euler_mascheroni = (\<Sum>k. D k)"
   359   from euler_mascheroni_sum_real have "euler_mascheroni = (\<Sum>k. D k)"
   360     by (simp add: sums_iff D_def)
   360     by (simp add: sums_iff D_def)
   361   also have "\<dots> = (\<Sum>k. D (k + Suc n)) + (\<Sum>k\<le>n. D k)"
   361   also have "\<dots> = (\<Sum>k. D (k + Suc n)) + (\<Sum>k\<le>n. D k)"
   362     by (subst suminf_split_initial_segment[OF summable, of "Suc n"], 
   362     by (subst suminf_split_initial_segment[OF summable, of "Suc n"],
   363         subst lessThan_Suc_atMost) simp
   363         subst lessThan_Suc_atMost) simp
   364   finally have sum: "(\<Sum>k\<le>n. D k) - euler_mascheroni = -(\<Sum>k. D (k + Suc n))" by simp
   364   finally have sum: "(\<Sum>k\<le>n. D k) - euler_mascheroni = -(\<Sum>k. D (k + Suc n))" by simp
   365 
   365 
   366   note sum
   366   note sum
   367   also have "\<dots> \<le> -(\<Sum>k. (inv (k + Suc n + 1) - inv (k + Suc n + 2)) / 2)"
   367   also have "\<dots> \<le> -(\<Sum>k. (inv (k + Suc n + 1) - inv (k + Suc n + 2)) / 2)"
   522   and ln2_le_25_over_36: "ln (2::real) \<le> 25/36"
   522   and ln2_le_25_over_36: "ln (2::real) \<le> 25/36"
   523   using ln_approx_bounds[of 2 1, simplified, simplified eval_nat_numeral, simplified] by simp_all
   523   using ln_approx_bounds[of 2 1, simplified, simplified eval_nat_numeral, simplified] by simp_all
   524 
   524 
   525 
   525 
   526 text \<open>
   526 text \<open>
   527   Approximation of the Euler--Mascheroni constant. The lower bound is accurate to about 0.0015;
   527   Approximation of the Euler-Mascheroni constant. The lower bound is accurate to about 0.0015;
   528   the upper bound is accurate to about 0.015.
   528   the upper bound is accurate to about 0.015.
   529 \<close>
   529 \<close>
   530 lemma euler_mascheroni_gt_19_over_33: "(euler_mascheroni :: real) > 19/33" (is ?th1)
   530 lemma euler_mascheroni_gt_19_over_33: "(euler_mascheroni :: real) > 19/33" (is ?th1)
   531   and euler_mascheroni_less_13_over_22: "(euler_mascheroni :: real) < 13/22" (is ?th2)
   531   and euler_mascheroni_less_13_over_22: "(euler_mascheroni :: real) < 13/22" (is ?th2)
   532 proof -
   532 proof -