equal
deleted
inserted
replaced
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) |