src/HOL/Library/Binomial.thy
changeset 46507 1b24c24017dd
parent 39302 d7728f65b353
child 46757 ad878aff9c15
equal deleted inserted replaced
46506:c7faa011bfa7 46507:1b24c24017dd
    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)