154 case 0 |
154 case 0 |
155 then show ?case by simp |
155 then show ?case by simp |
156 next |
156 next |
157 case (Suc n) |
157 case (Suc n) |
158 have "(\<Sum>k\<le>Suc n. stirling (Suc n) k) = stirling (Suc n) 0 + (\<Sum>k\<le>n. stirling (Suc n) (Suc k))" |
158 have "(\<Sum>k\<le>Suc n. stirling (Suc n) k) = stirling (Suc n) 0 + (\<Sum>k\<le>n. stirling (Suc n) (Suc k))" |
159 by (simp only: sum_atMost_Suc_shift) |
159 by (simp only: sum.atMost_Suc_shift) |
160 also have "\<dots> = (\<Sum>k\<le>n. stirling (Suc n) (Suc k))" |
160 also have "\<dots> = (\<Sum>k\<le>n. stirling (Suc n) (Suc k))" |
161 by simp |
161 by simp |
162 also have "\<dots> = (\<Sum>k\<le>n. n * stirling n (Suc k) + stirling n k)" |
162 also have "\<dots> = (\<Sum>k\<le>n. n * stirling n (Suc k) + stirling n k)" |
163 by simp |
163 by simp |
164 also have "\<dots> = n * (\<Sum>k\<le>n. stirling n (Suc k)) + (\<Sum>k\<le>n. stirling n k)" |
164 also have "\<dots> = n * (\<Sum>k\<le>n. stirling n (Suc k)) + (\<Sum>k\<le>n. stirling n k)" |
165 by (simp add: sum.distrib sum_distrib_left) |
165 by (simp add: sum.distrib sum_distrib_left) |
166 also have "\<dots> = n * fact n + fact n" |
166 also have "\<dots> = n * fact n + fact n" |
167 proof - |
167 proof - |
168 have "n * (\<Sum>k\<le>n. stirling n (Suc k)) = n * ((\<Sum>k\<le>Suc n. stirling n k) - stirling n 0)" |
168 have "n * (\<Sum>k\<le>n. stirling n (Suc k)) = n * ((\<Sum>k\<le>Suc n. stirling n k) - stirling n 0)" |
169 by (metis add_diff_cancel_left' sum_atMost_Suc_shift) |
169 by (metis add_diff_cancel_left' sum.atMost_Suc_shift) |
170 also have "\<dots> = n * (\<Sum>k\<le>n. stirling n k)" |
170 also have "\<dots> = n * (\<Sum>k\<le>n. stirling n k)" |
171 by (cases n) simp_all |
171 by (cases n) simp_all |
172 also have "\<dots> = n * fact n" |
172 also have "\<dots> = n * fact n" |
173 using Suc.hyps by simp |
173 using Suc.hyps by simp |
174 finally have "n * (\<Sum>k\<le>n. stirling n (Suc k)) = n * fact n" . |
174 finally have "n * (\<Sum>k\<le>n. stirling n (Suc k)) = n * fact n" . |
190 have "of_nat (n * stirling n 0) = (0 :: 'a)" by (cases n) simp_all |
190 have "of_nat (n * stirling n 0) = (0 :: 'a)" by (cases n) simp_all |
191 then have "(\<Sum>k\<le>Suc n. of_nat (stirling (Suc n) k) * x ^ k) = |
191 then have "(\<Sum>k\<le>Suc n. of_nat (stirling (Suc n) k) * x ^ k) = |
192 (of_nat (n * stirling n 0) * x ^ 0 + |
192 (of_nat (n * stirling n 0) * x ^ 0 + |
193 (\<Sum>i\<le>n. of_nat (n * stirling n (Suc i)) * (x ^ Suc i))) + |
193 (\<Sum>i\<le>n. of_nat (n * stirling n (Suc i)) * (x ^ Suc i))) + |
194 (\<Sum>i\<le>n. of_nat (stirling n i) * (x ^ Suc i))" |
194 (\<Sum>i\<le>n. of_nat (stirling n i) * (x ^ Suc i))" |
195 by (subst sum_atMost_Suc_shift) (simp add: sum.distrib ring_distribs) |
195 by (subst sum.atMost_Suc_shift) (simp add: sum.distrib ring_distribs) |
196 also have "\<dots> = pochhammer x (Suc n)" |
196 also have "\<dots> = pochhammer x (Suc n)" |
197 by (subst sum_atMost_Suc_shift [symmetric]) |
197 by (subst sum.atMost_Suc_shift [symmetric]) |
198 (simp add: algebra_simps sum.distrib sum_distrib_left pochhammer_Suc flip: Suc) |
198 (simp add: algebra_simps sum.distrib sum_distrib_left pochhammer_Suc flip: Suc) |
199 finally show ?case . |
199 finally show ?case . |
200 qed |
200 qed |
201 |
201 |
202 |
202 |