src/HOL/Library/Stirling.thy
changeset 70113 c8deb8ba6d05
parent 68975 5ce4d117cea7
equal deleted inserted replaced
70097:4005298550a6 70113:c8deb8ba6d05
   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