src/HOL/Number_Theory/Binomial.thy
changeset 36350 bc7982c54e37
parent 35731 1bdaa24fb56d
child 41340 9b3f25c934c8
equal deleted inserted replaced
36349:39be26d1bc28 36350:bc7982c54e37
   206   with less have two: "fact (k + 1) * fact (n - k) * (n choose (k + 1)) = 
   206   with less have two: "fact (k + 1) * fact (n - k) * (n choose (k + 1)) = 
   207       (n - k) * fact n" by simp
   207       (n - k) * fact n" by simp
   208   have "fact (k + 1) * fact (n - k) * (n + 1 choose (k + 1)) =
   208   have "fact (k + 1) * fact (n - k) * (n + 1 choose (k + 1)) =
   209       fact (k + 1) * fact (n - k) * (n choose (k + 1)) + 
   209       fact (k + 1) * fact (n - k) * (n choose (k + 1)) + 
   210       fact (k + 1) * fact (n - k) * (n choose k)" 
   210       fact (k + 1) * fact (n - k) * (n choose k)" 
   211     by (subst choose_reduce_nat, auto simp add: ring_simps)
   211     by (subst choose_reduce_nat, auto simp add: field_simps)
   212   also note one
   212   also note one
   213   also note two
   213   also note two
   214   also with less have "(n - k) * fact n + (k + 1) * fact n= fact (n + 1)" 
   214   also with less have "(n - k) * fact n + (k + 1) * fact n= fact (n + 1)" 
   215     apply (subst fact_plus_one_nat)
   215     apply (subst fact_plus_one_nat)
   216     apply (subst left_distrib [symmetric])
   216     apply (subst left_distrib [symmetric])
   277                   (SUM k=0..n. of_nat (n choose k) * a^k * b^(n-k+1))"
   277                   (SUM k=0..n. of_nat (n choose k) * a^k * b^(n-k+1))"
   278     by (subst (1 2) power_plus_one, simp add: setsum_right_distrib mult_ac)
   278     by (subst (1 2) power_plus_one, simp add: setsum_right_distrib mult_ac)
   279   also have "... = (SUM k=0..n. of_nat (n choose k) * a^k * b^(n+1-k)) +
   279   also have "... = (SUM k=0..n. of_nat (n choose k) * a^k * b^(n+1-k)) +
   280                   (SUM k=1..n+1. of_nat (n choose (k - 1)) * a^k * b^(n+1-k))"
   280                   (SUM k=1..n+1. of_nat (n choose (k - 1)) * a^k * b^(n+1-k))"
   281     by (simp add:setsum_shift_bounds_cl_Suc_ivl Suc_diff_le 
   281     by (simp add:setsum_shift_bounds_cl_Suc_ivl Suc_diff_le 
   282              power_Suc ring_simps One_nat_def del:setsum_cl_ivl_Suc)
   282              power_Suc field_simps One_nat_def del:setsum_cl_ivl_Suc)
   283   also have "... = a^(n+1) + b^(n+1) +
   283   also have "... = a^(n+1) + b^(n+1) +
   284                   (SUM k=1..n. of_nat (n choose (k - 1)) * a^k * b^(n+1-k)) +
   284                   (SUM k=1..n. of_nat (n choose (k - 1)) * a^k * b^(n+1-k)) +
   285                   (SUM k=1..n. of_nat (n choose k) * a^k * b^(n+1-k))"
   285                   (SUM k=1..n. of_nat (n choose k) * a^k * b^(n+1-k))"
   286     by (simp add: decomp2 decomp3)
   286     by (simp add: decomp2 decomp3)
   287   also have
   287   also have
   288       "... = a^(n+1) + b^(n+1) + 
   288       "... = a^(n+1) + b^(n+1) + 
   289          (SUM k=1..n. of_nat(n+1 choose k) * a^k * b^(n+1-k))"
   289          (SUM k=1..n. of_nat(n+1 choose k) * a^k * b^(n+1-k))"
   290     by (auto simp add: ring_simps setsum_addf [symmetric]
   290     by (auto simp add: field_simps setsum_addf [symmetric]
   291       choose_reduce_nat)
   291       choose_reduce_nat)
   292   also have "... = (SUM k=0..n+1. of_nat (n+1 choose k) * a^k * b^(n+1-k))"
   292   also have "... = (SUM k=0..n+1. of_nat (n+1 choose k) * a^k * b^(n+1-k))"
   293     using decomp by (simp add: ring_simps)
   293     using decomp by (simp add: field_simps)
   294   finally show "?P (n + 1)" by simp
   294   finally show "?P (n + 1)" by simp
   295 qed
   295 qed
   296 
   296 
   297 lemma set_explicit: "{S. S = T \<and> P S} = (if P T then {T} else {})"
   297 lemma set_explicit: "{S. S = T \<and> P S} = (if P T then {T} else {})"
   298   by auto
   298   by auto