equal
deleted
inserted
replaced
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 |