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 |