src/HOL/Number_Theory/Fib.thy
changeset 36350 bc7982c54e37
parent 35644 d20cf282342e
child 41541 1fa4725c4656
equal deleted inserted replaced
36349:39be26d1bc28 36350:bc7982c54e37
   141 lemma fib_add_nat: "fib ((n::nat) + k + 1) = fib (k + 1) * fib (n + 1) + 
   141 lemma fib_add_nat: "fib ((n::nat) + k + 1) = fib (k + 1) * fib (n + 1) + 
   142     fib k * fib n"
   142     fib k * fib n"
   143   apply (induct n rule: fib_induct_nat)
   143   apply (induct n rule: fib_induct_nat)
   144   apply auto
   144   apply auto
   145   apply (subst fib_reduce_nat)
   145   apply (subst fib_reduce_nat)
   146   apply (auto simp add: ring_simps)
   146   apply (auto simp add: field_simps)
   147   apply (subst (1 3 5) fib_reduce_nat)
   147   apply (subst (1 3 5) fib_reduce_nat)
   148   apply (auto simp add: ring_simps Suc_eq_plus1)
   148   apply (auto simp add: field_simps Suc_eq_plus1)
   149 (* hmmm. Why doesn't "n + (1 + (1 + k))" simplify to "n + k + 2"? *)
   149 (* hmmm. Why doesn't "n + (1 + (1 + k))" simplify to "n + k + 2"? *)
   150   apply (subgoal_tac "n + (k + 2) = n + (1 + (1 + k))")
   150   apply (subgoal_tac "n + (k + 2) = n + (1 + (1 + k))")
   151   apply (erule ssubst) back back
   151   apply (erule ssubst) back back
   152   apply (erule ssubst) back 
   152   apply (erule ssubst) back 
   153   apply auto
   153   apply auto
   182 *}
   182 *}
   183 
   183 
   184 lemma fib_Cassini_aux_int: "fib (int n + 2) * fib (int n) - 
   184 lemma fib_Cassini_aux_int: "fib (int n + 2) * fib (int n) - 
   185     (fib (int n + 1))^2 = (-1)^(n + 1)"
   185     (fib (int n + 1))^2 = (-1)^(n + 1)"
   186   apply (induct n)
   186   apply (induct n)
   187   apply (auto simp add: ring_simps power2_eq_square fib_reduce_int
   187   apply (auto simp add: field_simps power2_eq_square fib_reduce_int
   188       power_add)
   188       power_add)
   189 done
   189 done
   190 
   190 
   191 lemma fib_Cassini_int: "n >= 0 \<Longrightarrow> fib (n + 2) * fib n - 
   191 lemma fib_Cassini_int: "n >= 0 \<Longrightarrow> fib (n + 2) * fib n - 
   192     (fib (n + 1))^2 = (-1)^(nat n + 1)"
   192     (fib (n + 1))^2 = (-1)^(nat n + 1)"
   220   apply (induct n rule: fib_induct_nat)
   220   apply (induct n rule: fib_induct_nat)
   221   apply auto
   221   apply auto
   222   apply (subst (2) fib_reduce_nat)
   222   apply (subst (2) fib_reduce_nat)
   223   apply (auto simp add: Suc_eq_plus1) (* again, natdiff_cancel *)
   223   apply (auto simp add: Suc_eq_plus1) (* again, natdiff_cancel *)
   224   apply (subst add_commute, auto)
   224   apply (subst add_commute, auto)
   225   apply (subst gcd_commute_nat, auto simp add: ring_simps)
   225   apply (subst gcd_commute_nat, auto simp add: field_simps)
   226 done
   226 done
   227 
   227 
   228 lemma coprime_fib_Suc_nat: "coprime (fib n) (fib (Suc n))"
   228 lemma coprime_fib_Suc_nat: "coprime (fib n) (fib (Suc n))"
   229   using coprime_fib_plus_1_nat by (simp add: One_nat_def)
   229   using coprime_fib_plus_1_nat by (simp add: One_nat_def)
   230 
   230 
   303   by auto
   303   by auto
   304 
   304 
   305 theorem fib_mult_eq_setsum_nat:
   305 theorem fib_mult_eq_setsum_nat:
   306     "fib ((n::nat) + 1) * fib n = (\<Sum>k \<in> {..n}. fib k * fib k)"
   306     "fib ((n::nat) + 1) * fib n = (\<Sum>k \<in> {..n}. fib k * fib k)"
   307   apply (induct n)
   307   apply (induct n)
   308   apply (auto simp add: atMost_plus_one_nat fib_plus_2_nat ring_simps)
   308   apply (auto simp add: atMost_plus_one_nat fib_plus_2_nat field_simps)
   309 done
   309 done
   310 
   310 
   311 theorem fib_mult_eq_setsum'_nat:
   311 theorem fib_mult_eq_setsum'_nat:
   312     "fib (Suc n) * fib n = (\<Sum>k \<in> {..n}. fib k * fib k)"
   312     "fib (Suc n) * fib n = (\<Sum>k \<in> {..n}. fib k * fib k)"
   313   using fib_mult_eq_setsum_nat by (simp add: One_nat_def)
   313   using fib_mult_eq_setsum_nat by (simp add: One_nat_def)