src/HOL/Inequalities.thy
changeset 61609 77b453bd616f
parent 60758 d8d85a8172b5
child 61649 268d88ec9087
equal deleted inserted replaced
61553:933eb9e6a1cc 61609:77b453bd616f
    29 shows "\<Sum> {m..n} = (n*(n+1) - m*(m-1)) div 2"
    29 shows "\<Sum> {m..n} = (n*(n+1) - m*(m-1)) div 2"
    30 proof -
    30 proof -
    31   have "m*(m-1) \<le> n*(n + 1)"
    31   have "m*(m-1) \<le> n*(n + 1)"
    32    using assms by (meson diff_le_self order_trans le_add1 mult_le_mono)
    32    using assms by (meson diff_le_self order_trans le_add1 mult_le_mono)
    33   hence "int(\<Sum> {m..n}) = int((n*(n+1) - m*(m-1)) div 2)" using assms
    33   hence "int(\<Sum> {m..n}) = int((n*(n+1) - m*(m-1)) div 2)" using assms
    34     by (auto simp: Setsum_Icc_int[transferred, OF assms] zdiv_int int_mult
    34     by (auto simp: Setsum_Icc_int[transferred, OF assms] zdiv_int int_mult simp del: of_nat_setsum
    35       split: zdiff_int_split)
    35           split: zdiff_int_split)
    36   thus ?thesis by simp
    36   thus ?thesis
       
    37     by blast 
    37 qed
    38 qed
    38 
    39 
    39 lemma Setsum_Ico_nat: assumes "(m::nat) \<le> n"
    40 lemma Setsum_Ico_nat: assumes "(m::nat) \<le> n"
    40 shows "\<Sum> {m..<n} = (n*(n-1) - m*(m-1)) div 2"
    41 shows "\<Sum> {m..<n} = (n*(n-1) - m*(m-1)) div 2"
    41 proof cases
    42 proof cases
    73   fixes a b :: "nat \<Rightarrow> nat"
    74   fixes a b :: "nat \<Rightarrow> nat"
    74   shows "(\<And>i j. \<lbrakk> i\<le>j; j<n \<rbrakk> \<Longrightarrow> a i \<le> a j) \<Longrightarrow>
    75   shows "(\<And>i j. \<lbrakk> i\<le>j; j<n \<rbrakk> \<Longrightarrow> a i \<le> a j) \<Longrightarrow>
    75          (\<And>i j. \<lbrakk> i\<le>j; j<n \<rbrakk> \<Longrightarrow> b i \<ge> b j) \<Longrightarrow>
    76          (\<And>i j. \<lbrakk> i\<le>j; j<n \<rbrakk> \<Longrightarrow> b i \<ge> b j) \<Longrightarrow>
    76     n * (\<Sum>i=0..<n. a i * b i) \<le> (\<Sum>i=0..<n. a i) * (\<Sum>i=0..<n. b i)"
    77     n * (\<Sum>i=0..<n. a i * b i) \<le> (\<Sum>i=0..<n. a i) * (\<Sum>i=0..<n. b i)"
    77 using Chebyshev_sum_upper[where 'a=real, of n a b]
    78 using Chebyshev_sum_upper[where 'a=real, of n a b]
    78 by (simp del: real_of_nat_mult real_of_nat_setsum
    79 by (simp del: of_nat_mult of_nat_setsum  add: of_nat_mult[symmetric] of_nat_setsum[symmetric])
    79   add: real_of_nat_mult[symmetric] real_of_nat_setsum[symmetric] real_of_nat_def[symmetric])
       
    80 
    80 
    81 end
    81 end