equal
deleted
inserted
replaced
66 |
66 |
67 text{*This is the well-known version, but it's harder to use because of the |
67 text{*This is the well-known version, but it's harder to use because of the |
68 need to reason about division.*} |
68 need to reason about division.*} |
69 lemma binomial_Suc_Suc_eq_times: |
69 lemma binomial_Suc_Suc_eq_times: |
70 "k \<le> n ==> (Suc n choose Suc k) = (Suc n * (n choose k)) div Suc k" |
70 "k \<le> n ==> (Suc n choose Suc k) = (Suc n * (n choose k)) div Suc k" |
71 by (simp add: Suc_times_binomial_eq div_mult_self_is_m zero_less_Suc |
71 by (simp add: Suc_times_binomial_eq del: mult_Suc mult_Suc_right) |
72 del: mult_Suc mult_Suc_right) |
|
73 |
72 |
74 text{*Another version, with -1 instead of Suc.*} |
73 text{*Another version, with -1 instead of Suc.*} |
75 lemma times_binomial_minus1_eq: |
74 lemma times_binomial_minus1_eq: |
76 "[|k \<le> n; 0<k|] ==> (n choose k) * k = n * ((n - 1) choose (k - 1))" |
75 "[|k \<le> n; 0<k|] ==> (n choose k) * k = n * ((n - 1) choose (k - 1))" |
77 apply (cut_tac n = "n - 1" and k = "k - 1" in Suc_times_binomial_eq) |
76 apply (cut_tac n = "n - 1" and k = "k - 1" in Suc_times_binomial_eq) |
253 lemma pochhammer_of_nat_eq_0_lemma: assumes kn: "k > n" |
252 lemma pochhammer_of_nat_eq_0_lemma: assumes kn: "k > n" |
254 shows "pochhammer (- (of_nat n :: 'a:: idom)) k = 0" |
253 shows "pochhammer (- (of_nat n :: 'a:: idom)) k = 0" |
255 proof- |
254 proof- |
256 from kn obtain h where h: "k = Suc h" by (cases k, auto) |
255 from kn obtain h where h: "k = Suc h" by (cases k, auto) |
257 {assume n0: "n=0" then have ?thesis using kn |
256 {assume n0: "n=0" then have ?thesis using kn |
258 by (cases k, simp_all add: pochhammer_rec del: pochhammer_Suc)} |
257 by (cases k) (simp_all add: pochhammer_rec)} |
259 moreover |
258 moreover |
260 {assume n0: "n \<noteq> 0" |
259 {assume n0: "n \<noteq> 0" |
261 then have ?thesis apply (simp add: h pochhammer_Suc_setprod) |
260 then have ?thesis apply (simp add: h pochhammer_Suc_setprod) |
262 apply (rule_tac x="n" in bexI) |
261 apply (rule_tac x="n" in bexI) |
263 using h kn by auto} |
262 using h kn by auto} |
309 {fix h assume h: "k = Suc h" |
308 {fix h assume h: "k = Suc h" |
310 have eq: "((- 1) ^ Suc h :: 'a) = setprod (%i. - 1) {0 .. h}" |
309 have eq: "((- 1) ^ Suc h :: 'a) = setprod (%i. - 1) {0 .. h}" |
311 using setprod_constant[where A="{0 .. h}" and y="- 1 :: 'a"] |
310 using setprod_constant[where A="{0 .. h}" and y="- 1 :: 'a"] |
312 by auto |
311 by auto |
313 have ?thesis |
312 have ?thesis |
314 unfolding h h pochhammer_Suc_setprod eq setprod_timesf[symmetric] |
313 unfolding h pochhammer_Suc_setprod eq setprod_timesf[symmetric] |
315 apply (rule strong_setprod_reindex_cong[where f = "%i. h - i"]) |
314 apply (rule strong_setprod_reindex_cong[where f = "%i. h - i"]) |
316 apply (auto simp add: inj_on_def image_def h ) |
315 apply (auto simp add: inj_on_def image_def h ) |
317 apply (rule_tac x="h - x" in bexI) |
316 apply (rule_tac x="h - x" in bexI) |
318 by (auto simp add: fun_eq_iff h of_nat_diff)} |
317 by (auto simp add: fun_eq_iff h of_nat_diff)} |
319 ultimately show ?thesis by (cases k, auto) |
318 ultimately show ?thesis by (cases k, auto) |