src/HOL/Library/Binomial.thy
changeset 36309 4da07afb065b
parent 35372 ca158c7b1144
child 36350 bc7982c54e37
equal deleted inserted replaced
36308:bbcfeddeafbb 36309:4da07afb065b
   389   
   389   
   390 lemma binomial_fact: 
   390 lemma binomial_fact: 
   391   assumes kn: "k \<le> n" 
   391   assumes kn: "k \<le> n" 
   392   shows "(of_nat (n choose k) :: 'a::field_char_0) = of_nat (fact n) / (of_nat (fact k) * of_nat (fact (n - k)))"
   392   shows "(of_nat (n choose k) :: 'a::field_char_0) = of_nat (fact n) / (of_nat (fact k) * of_nat (fact (n - k)))"
   393   using binomial_fact_lemma[OF kn]
   393   using binomial_fact_lemma[OF kn]
   394   by (simp add: field_simps of_nat_mult[symmetric])
   394   by (simp add: field_eq_simps of_nat_mult [symmetric])
   395 
   395 
   396 lemma binomial_gbinomial: "of_nat (n choose k) = of_nat n gchoose k"
   396 lemma binomial_gbinomial: "of_nat (n choose k) = of_nat n gchoose k"
   397 proof-
   397 proof-
   398   {assume kn: "k > n" 
   398   {assume kn: "k > n" 
   399     from kn binomial_eq_0[OF kn] have ?thesis 
   399     from kn binomial_eq_0[OF kn] have ?thesis 
   400       by (simp add: gbinomial_pochhammer field_simps
   400       by (simp add: gbinomial_pochhammer field_eq_simps
   401         pochhammer_of_nat_eq_0_iff)}
   401         pochhammer_of_nat_eq_0_iff)}
   402   moreover
   402   moreover
   403   {assume "k=0" then have ?thesis by simp}
   403   {assume "k=0" then have ?thesis by simp}
   404   moreover
   404   moreover
   405   {assume kn: "k \<le> n" and k0: "k\<noteq> 0"
   405   {assume kn: "k \<le> n" and k0: "k\<noteq> 0"
   418     have th0: "finite {1..n - Suc h}" "finite {n - h .. n}" 
   418     have th0: "finite {1..n - Suc h}" "finite {n - h .. n}" 
   419 "{1..n - Suc h} \<inter> {n - h .. n} = {}" and eq3: "{1..n - Suc h} \<union> {n - h .. n} = {1..n}" using h kn by auto
   419 "{1..n - Suc h} \<inter> {n - h .. n} = {}" and eq3: "{1..n - Suc h} \<union> {n - h .. n} = {1..n}" using h kn by auto
   420     from eq[symmetric]
   420     from eq[symmetric]
   421     have ?thesis using kn
   421     have ?thesis using kn
   422       apply (simp add: binomial_fact[OF kn, where ?'a = 'a] 
   422       apply (simp add: binomial_fact[OF kn, where ?'a = 'a] 
   423         gbinomial_pochhammer field_simps pochhammer_Suc_setprod)
   423         gbinomial_pochhammer field_eq_simps pochhammer_Suc_setprod)
   424       apply (simp add: pochhammer_Suc_setprod fact_altdef_nat h of_nat_setprod setprod_timesf[symmetric] eq' del: One_nat_def power_Suc)
   424       apply (simp add: pochhammer_Suc_setprod fact_altdef_nat h of_nat_setprod setprod_timesf[symmetric] eq' del: One_nat_def power_Suc)
   425       unfolding setprod_Un_disjoint[OF th0, unfolded eq3, of "of_nat:: nat \<Rightarrow> 'a"] eq[unfolded h]
   425       unfolding setprod_Un_disjoint[OF th0, unfolded eq3, of "of_nat:: nat \<Rightarrow> 'a"] eq[unfolded h]
   426       unfolding mult_assoc[symmetric] 
   426       unfolding mult_assoc[symmetric] 
   427       unfolding setprod_timesf[symmetric]
   427       unfolding setprod_timesf[symmetric]
   428       apply simp
   428       apply simp
   447 lemma gbinomial_mult_1: "a * (a gchoose n) = of_nat n * (a gchoose n) + of_nat (Suc n) * (a gchoose (Suc n))" (is "?l = ?r")
   447 lemma gbinomial_mult_1: "a * (a gchoose n) = of_nat n * (a gchoose n) + of_nat (Suc n) * (a gchoose (Suc n))" (is "?l = ?r")
   448 proof-
   448 proof-
   449   have "?r = ((- 1) ^n * pochhammer (- a) n / of_nat (fact n)) * (of_nat n - (- a + of_nat n))"
   449   have "?r = ((- 1) ^n * pochhammer (- a) n / of_nat (fact n)) * (of_nat n - (- a + of_nat n))"
   450     unfolding gbinomial_pochhammer
   450     unfolding gbinomial_pochhammer
   451     pochhammer_Suc fact_Suc of_nat_mult right_diff_distrib power_Suc
   451     pochhammer_Suc fact_Suc of_nat_mult right_diff_distrib power_Suc
   452     by (simp add:  field_simps del: of_nat_Suc)
   452     by (simp add:  field_eq_simps del: of_nat_Suc)
   453   also have "\<dots> = ?l" unfolding gbinomial_pochhammer
   453   also have "\<dots> = ?l" unfolding gbinomial_pochhammer
   454     by (simp add: ring_simps)
   454     by (simp add: ring_simps)
   455   finally show ?thesis ..
   455   finally show ?thesis ..
   456 qed
   456 qed
   457 
   457