data.nat.fib | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

92ca63f0

(last sync)

refactor(tactic/wlog): simplify and speed up wlog (#16495)

Benefits:

The tactic is faster
The tactic is easier to port to Lean 4

Downside:

The tactic doesn't do any heavy-lifting for the user

Zulip thread: https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/wlog/near/296996966

Co-authored-by: Yury G. Kudryashov <urkud@urkud.name> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

Diff

@@ -222,15 +222,13 @@ lemma gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m)) =
   see https://proofwiki.org/wiki/GCD_of_Fibonacci_Numbers -/
 lemma fib_gcd (m n : ℕ) : fib (gcd m n) = gcd (fib m) (fib n) :=
 begin
-  wlog h : m ≤ n using [n m, m n],
-  exact le_total m n,
-  { apply gcd.induction m n,
-    { simp },
-    intros m n mpos h,
-    rw ← gcd_rec m n at h,
-    conv_rhs { rw ← mod_add_div' n m },
-    rwa [gcd_fib_add_mul_self m (n % m) (n / m), gcd_comm (fib m) _] },
-  rwa [gcd_comm, gcd_comm (fib m)]
+  wlog h : m ≤ n, { simpa only [gcd_comm] using this _ _ (le_of_not_le h) },
+  apply gcd.induction m n,
+  { simp },
+  intros m n mpos h,
+  rw ← gcd_rec m n at h,
+  conv_rhs { rw ← mod_add_div' n m },
+  rwa [gcd_fib_add_mul_self m (n % m) (n / m), gcd_comm (fib m) _]
 end
 
 lemma fib_dvd (m n : ℕ) (h : m ∣ n) : fib m ∣ fib n :=

008205aa

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

92ca63f0

bump to nightly-2024-04-06-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

e34029c9

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2019 Kevin Kappelmann. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kevin Kappelmann, Kyle Miller, Mario Carneiro
 -/
-import Data.Nat.Gcd.Basic
+import Data.Nat.GCD.Basic
 import Logic.Function.Iterate
 import Data.Finset.NatAntidiagonal
 import Algebra.BigOperators.Basic

92ca63f0

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -172,7 +172,7 @@ theorem fib_add (m n : ℕ) : fib (m + n + 1) = fib m * fib n + fib (m + 1) * fi
   · simp
   · intros
     specialize ih (m + 1)
-    rw [add_assoc m 1 n, add_comm 1 n] at ih 
+    rw [add_assoc m 1 n, add_comm 1 n] at ih
     simp only [fib_add_two, ih]
     ring
 #align nat.fib_add Nat.fib_add
@@ -319,7 +319,7 @@ theorem fib_gcd (m n : ℕ) : fib (gcd m n) = gcd (fib m) (fib n) :=
   apply gcd.induction m n
   · simp
   intro m n mpos h
-  rw [← gcd_rec m n] at h 
+  rw [← gcd_rec m n] at h
   conv_rhs => rw [← mod_add_div' n m]
   rwa [gcd_fib_add_mul_self m (n % m) (n / m), gcd_comm (fib m) _]
 #align nat.fib_gcd Nat.fib_gcd

92ca63f0

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,13 +3,13 @@ Copyright (c) 2019 Kevin Kappelmann. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kevin Kappelmann, Kyle Miller, Mario Carneiro
 -/
-import Mathbin.Data.Nat.Gcd.Basic
-import Mathbin.Logic.Function.Iterate
-import Mathbin.Data.Finset.NatAntidiagonal
-import Mathbin.Algebra.BigOperators.Basic
-import Mathbin.Tactic.Ring
-import Mathbin.Tactic.Zify
-import Mathbin.Tactic.Wlog
+import Data.Nat.Gcd.Basic
+import Logic.Function.Iterate
+import Data.Finset.NatAntidiagonal
+import Algebra.BigOperators.Basic
+import Tactic.Ring
+import Tactic.Zify
+import Tactic.Wlog
 
 #align_import data.nat.fib from "leanprover-community/mathlib"@"92ca63f0fb391a9ca5f22d2409a6080e786d99f7"

92ca63f0

bump to nightly-2023-09-20-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

e28e6964

Diff

@@ -155,7 +155,7 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n :=
 #print Nat.fib_coprime_fib_succ /-
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/
-theorem fib_coprime_fib_succ (n : ℕ) : Nat.coprime (fib n) (fib (n + 1)) :=
+theorem fib_coprime_fib_succ (n : ℕ) : Nat.Coprime (fib n) (fib (n + 1)) :=
   by
   induction' n with n ih
   · simp

92ca63f0

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,11 +2,6 @@
 Copyright (c) 2019 Kevin Kappelmann. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kevin Kappelmann, Kyle Miller, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.fib
-! leanprover-community/mathlib commit 92ca63f0fb391a9ca5f22d2409a6080e786d99f7
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Nat.Gcd.Basic
 import Mathbin.Logic.Function.Iterate
@@ -16,6 +11,8 @@ import Mathbin.Tactic.Ring
 import Mathbin.Tactic.Zify
 import Mathbin.Tactic.Wlog
 
+#align_import data.nat.fib from "leanprover-community/mathlib"@"92ca63f0fb391a9ca5f22d2409a6080e786d99f7"
+
 /-!
 # The Fibonacci Sequence

92ca63f0

bump to nightly-2023-06-10-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/a3e83f0fa4391c8740f7d773a7a9b74e311ae2a3

3fdc57bc

Diff

@@ -345,15 +345,15 @@ theorem fib_succ_eq_sum_choose :
 -/
 
 #print Nat.fib_succ_eq_succ_sum /-
-theorem fib_succ_eq_succ_sum (n : ℕ) : fib (n + 1) = (∑ k in Finset.range n, fib k) + 1 :=
+theorem fib_succ_eq_succ_sum (n : ℕ) : fib (n + 1) = ∑ k in Finset.range n, fib k + 1 :=
   by
   induction' n with n ih
   · simp
   ·
     calc
       fib (n + 2) = fib n + fib (n + 1) := fib_add_two
-      _ = (fib n + ∑ k in Finset.range n, fib k) + 1 := by rw [ih, add_assoc]
-      _ = (∑ k in Finset.range (n + 1), fib k) + 1 := by simp [Finset.range_add_one]
+      _ = fib n + ∑ k in Finset.range n, fib k + 1 := by rw [ih, add_assoc]
+      _ = ∑ k in Finset.range (n + 1), fib k + 1 := by simp [Finset.range_add_one]
 #align nat.fib_succ_eq_succ_sum Nat.fib_succ_eq_succ_sum
 -/

92ca63f0

bump to nightly-2023-06-09-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

16afdc39

Diff

@@ -113,7 +113,6 @@ theorem fib_pos {n : ℕ} (n_pos : 0 < n) : 0 < fib n :=
   calc
     0 < fib 1 := by decide
     _ ≤ fib n := fib_mono n_pos
-    
 #align nat.fib_pos Nat.fib_pos
 -/
 
@@ -153,7 +152,6 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n :=
     calc
       n ≤ fib n := IH
       _ < fib (n + 1) := fib_lt_fib_succ (le_trans (by decide) five_le_n)
-      
 #align nat.le_fib_self Nat.le_fib_self
 -/
 
@@ -305,7 +303,6 @@ theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (
       rw [add_comm, gcd_add_mul_right_right (fib m) _ (fib n.pred)]
     _ = gcd (fib m) (fib (n.pred + 1)) :=
       coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (coprime.symm (fib_coprime_fib_succ m))
-    
 #align nat.gcd_fib_add_self Nat.gcd_fib_add_self
 -/
 
@@ -357,7 +354,6 @@ theorem fib_succ_eq_succ_sum (n : ℕ) : fib (n + 1) = (∑ k in Finset.range n,
       fib (n + 2) = fib n + fib (n + 1) := fib_add_two
       _ = (fib n + ∑ k in Finset.range n, fib k) + 1 := by rw [ih, add_assoc]
       _ = (∑ k in Finset.range (n + 1), fib k) + 1 := by simp [Finset.range_add_one]
-      
 #align nat.fib_succ_eq_succ_sum Nat.fib_succ_eq_succ_sum
 -/

92ca63f0

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -177,7 +177,7 @@ theorem fib_add (m n : ℕ) : fib (m + n + 1) = fib m * fib n + fib (m + 1) * fi
   · simp
   · intros
     specialize ih (m + 1)
-    rw [add_assoc m 1 n, add_comm 1 n] at ih
+    rw [add_assoc m 1 n, add_comm 1 n] at ih 
     simp only [fib_add_two, ih]
     ring
 #align nat.fib_add Nat.fib_add
@@ -325,7 +325,7 @@ theorem fib_gcd (m n : ℕ) : fib (gcd m n) = gcd (fib m) (fib n) :=
   apply gcd.induction m n
   · simp
   intro m n mpos h
-  rw [← gcd_rec m n] at h
+  rw [← gcd_rec m n] at h 
   conv_rhs => rw [← mod_add_div' n m]
   rwa [gcd_fib_add_mul_self m (n % m) (n / m), gcd_comm (fib m) _]
 #align nat.fib_gcd Nat.fib_gcd

92ca63f0

bump to nightly-2023-05-28-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

8d353152

Diff

@@ -51,7 +51,7 @@ fib, fibonacci
 -/
 
 
-open BigOperators
+open scoped BigOperators
 
 namespace Nat

92ca63f0

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -195,10 +195,8 @@ theorem fib_two_mul (n : ℕ) : fib (2 * n) = fib n * (2 * fib (n + 1) - fib n)
 -/
 
 #print Nat.fib_two_mul_add_one /-
-theorem fib_two_mul_add_one (n : ℕ) : fib (2 * n + 1) = fib (n + 1) ^ 2 + fib n ^ 2 :=
-  by
-  rw [two_mul, fib_add]
-  ring
+theorem fib_two_mul_add_one (n : ℕ) : fib (2 * n + 1) = fib (n + 1) ^ 2 + fib n ^ 2 := by
+  rw [two_mul, fib_add]; ring
 #align nat.fib_two_mul_add_one Nat.fib_two_mul_add_one
 -/
 
@@ -297,15 +295,12 @@ theorem fast_fib_eq (n : ℕ) : fastFib n = fib n := by rw [fast_fib, fast_fib_a
 theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (fib n) :=
   by
   cases Nat.eq_zero_or_pos n
-  · rw [h]
-    simp
+  · rw [h]; simp
   replace h := Nat.succ_pred_eq_of_pos h; rw [← h, succ_eq_add_one]
   calc
     gcd (fib m) (fib (n.pred + 1 + m)) =
         gcd (fib m) (fib n.pred * fib m + fib (n.pred + 1) * fib (m + 1)) :=
-      by
-      rw [← fib_add n.pred _]
-      ring_nf
+      by rw [← fib_add n.pred _]; ring_nf
     _ = gcd (fib m) (fib (n.pred + 1) * fib (m + 1)) := by
       rw [add_comm, gcd_add_mul_right_right (fib m) _ (fib n.pred)]
     _ = gcd (fib m) (fib (n.pred + 1)) :=

92ca63f0

bump to nightly-2023-05-28-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6c6011cf

Diff

@@ -379,58 +379,46 @@ produces proofs of what `nat.fib` evaluates to.
 -/
 
 
-#print NormNum.IsFibAux /-
 /-- Auxiliary definition for `prove_fib` plugin. -/
 def IsFibAux (n a b : ℕ) :=
   fib n = a ∧ fib (n + 1) = b
 #align norm_num.is_fib_aux NormNum.IsFibAux
--/
 
-#print NormNum.is_fib_aux_one /-
-theorem is_fib_aux_one : IsFibAux 1 1 1 :=
+theorem isFibAux_one : IsFibAux 1 1 1 :=
   ⟨fib_one, fib_two⟩
-#align norm_num.is_fib_aux_one NormNum.is_fib_aux_one
--/
+#align norm_num.is_fib_aux_one NormNum.isFibAux_one
 
-#print NormNum.is_fib_aux_bit0 /-
-theorem is_fib_aux_bit0 {n a b c a2 b2 a' b' : ℕ} (H : IsFibAux n a b) (h1 : a + c = bit0 b)
+theorem isFibAux_bit0 {n a b c a2 b2 a' b' : ℕ} (H : IsFibAux n a b) (h1 : a + c = bit0 b)
     (h2 : a * c = a') (h3 : a * a = a2) (h4 : b * b = b2) (h5 : a2 + b2 = b') :
     IsFibAux (bit0 n) a' b' :=
   ⟨by
     rw [fib_bit0, H.1, H.2, ← bit0_eq_two_mul,
       show bit0 b - a = c by rw [← h1, Nat.add_sub_cancel_left], h2],
     by rw [fib_bit0_succ, H.1, H.2, pow_two, pow_two, h3, h4, add_comm, h5]⟩
-#align norm_num.is_fib_aux_bit0 NormNum.is_fib_aux_bit0
--/
+#align norm_num.is_fib_aux_bit0 NormNum.isFibAux_bit0
 
-#print NormNum.is_fib_aux_bit1 /-
-theorem is_fib_aux_bit1 {n a b c a2 b2 a' b' : ℕ} (H : IsFibAux n a b) (h1 : a * a = a2)
+theorem isFibAux_bit1 {n a b c a2 b2 a' b' : ℕ} (H : IsFibAux n a b) (h1 : a * a = a2)
     (h2 : b * b = b2) (h3 : a2 + b2 = a') (h4 : bit0 a + b = c) (h5 : b * c = b') :
     IsFibAux (bit1 n) a' b' :=
   ⟨by rw [fib_bit1, H.1, H.2, pow_two, pow_two, h1, h2, add_comm, h3], by
     rw [fib_bit1_succ, H.1, H.2, ← bit0_eq_two_mul, h4, h5]⟩
-#align norm_num.is_fib_aux_bit1 NormNum.is_fib_aux_bit1
--/
+#align norm_num.is_fib_aux_bit1 NormNum.isFibAux_bit1
 
-#print NormNum.is_fib_aux_bit0_done /-
-theorem is_fib_aux_bit0_done {n a b c a' : ℕ} (H : IsFibAux n a b) (h1 : a + c = bit0 b)
+theorem isFibAux_bit0_done {n a b c a' : ℕ} (H : IsFibAux n a b) (h1 : a + c = bit0 b)
     (h2 : a * c = a') : fib (bit0 n) = a' :=
-  (is_fib_aux_bit0 H h1 h2 rfl rfl rfl).1
-#align norm_num.is_fib_aux_bit0_done NormNum.is_fib_aux_bit0_done
--/
+  (isFibAux_bit0 H h1 h2 rfl rfl rfl).1
+#align norm_num.is_fib_aux_bit0_done NormNum.isFibAux_bit0_done
 
-#print NormNum.is_fib_aux_bit1_done /-
-theorem is_fib_aux_bit1_done {n a b a2 b2 a' : ℕ} (H : IsFibAux n a b) (h1 : a * a = a2)
+theorem isFibAux_bit1_done {n a b a2 b2 a' : ℕ} (H : IsFibAux n a b) (h1 : a * a = a2)
     (h2 : b * b = b2) (h3 : a2 + b2 = a') : fib (bit1 n) = a' :=
-  (is_fib_aux_bit1 H h1 h2 h3 rfl rfl).1
-#align norm_num.is_fib_aux_bit1_done NormNum.is_fib_aux_bit1_done
--/
+  (isFibAux_bit1 H h1 h2 h3 rfl rfl).1
+#align norm_num.is_fib_aux_bit1_done NormNum.isFibAux_bit1_done
 
 /-- `prove_fib_aux ic n` returns `(ic', a, b, ⊢ is_fib_aux n a b)`, where `n` is a numeral. -/
 unsafe def prove_fib_aux (ic : instance_cache) : expr → tactic (instance_cache × expr × expr × expr)
   | e =>
     match match_numeral e with
-    | match_numeral_result.one => pure (ic, q((1 : ℕ)), q((1 : ℕ)), q(is_fib_aux_one))
+    | match_numeral_result.one => pure (ic, q((1 : ℕ)), q((1 : ℕ)), q(isFibAux_one))
     | match_numeral_result.bit0 e => do
       let (ic, a, b, H) ← prove_fib_aux e
       let na ← a.toNat
@@ -442,8 +430,7 @@ unsafe def prove_fib_aux (ic : instance_cache) : expr → tactic (instance_cache
       let (ic, b2, h4) ← prove_mul_nat ic b b
       let (ic, b', h5) ← prove_add_nat' ic a2 b2
       pure
-          (ic, a', b',
-            q(@is_fib_aux_bit0).mk_app [e, a, b, c, a2, b2, a', b', H, h1, h2, h3, h4, h5])
+          (ic, a', b', q(@isFibAux_bit0).mk_app [e, a, b, c, a2, b2, a', b', H, h1, h2, h3, h4, h5])
     | match_numeral_result.bit1 e => do
       let (ic, a, b, H) ← prove_fib_aux e
       let na ← a.toNat
@@ -455,8 +442,7 @@ unsafe def prove_fib_aux (ic : instance_cache) : expr → tactic (instance_cache
       let (ic, h4) ← prove_add_nat ic (q((bit0 : ℕ → ℕ)).mk_app [a]) b c
       let (ic, b', h5) ← prove_mul_nat ic b c
       pure
-          (ic, a', b',
-            q(@is_fib_aux_bit1).mk_app [e, a, b, c, a2, b2, a', b', H, h1, h2, h3, h4, h5])
+          (ic, a', b', q(@isFibAux_bit1).mk_app [e, a, b, c, a2, b2, a', b', H, h1, h2, h3, h4, h5])
     | _ => failed
 #align norm_num.prove_fib_aux norm_num.prove_fib_aux
 
@@ -473,13 +459,13 @@ unsafe def prove_fib (ic : instance_cache) (e : expr) : tactic (instance_cache 
     let (ic, c) ← ic.ofNat (2 * nb - na)
     let (ic, h1) ← prove_add_nat ic a c (q((bit0 : ℕ → ℕ)).mk_app [b])
     let (ic, a', h2) ← prove_mul_nat ic a c
-    pure (ic, a', q(@is_fib_aux_bit0_done).mk_app [e, a, b, c, a', H, h1, h2])
+    pure (ic, a', q(@isFibAux_bit0_done).mk_app [e, a, b, c, a', H, h1, h2])
   | match_numeral_result.bit1 e => do
     let (ic, a, b, H) ← prove_fib_aux ic e
     let (ic, a2, h1) ← prove_mul_nat ic a a
     let (ic, b2, h2) ← prove_mul_nat ic b b
     let (ic, a', h3) ← prove_add_nat' ic a2 b2
-    pure (ic, a', q(@is_fib_aux_bit1_done).mk_app [e, a, b, a2, b2, a', H, h1, h2, h3])
+    pure (ic, a', q(@isFibAux_bit1_done).mk_app [e, a, b, a2, b2, a', H, h1, h2, h3])
   | _ => failed
 #align norm_num.prove_fib norm_num.prove_fib

92ca63f0

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

92ca63f0

chore: superfluous parentheses (#12116)

Co-authored-by: Moritz Firsching <firsching@google.com>

596d5eca

Diff

@@ -191,7 +191,7 @@ theorem fib_two_mul_add_two (n : ℕ) :
   rw [fib_add_two, fib_two_mul, fib_two_mul_add_one]
   -- Porting note: A bunch of issues similar to [this zulip thread](https://github.com/leanprover-community/mathlib4/pull/1576) with `zify`
   have : fib n ≤ 2 * fib (n + 1) :=
-    le_trans (fib_le_fib_succ) (mul_comm 2 _ ▸ Nat.le_mul_of_pos_right _ two_pos)
+    le_trans fib_le_fib_succ (mul_comm 2 _ ▸ Nat.le_mul_of_pos_right _ two_pos)
   zify [this]
   ring

92ca63f0

chore: Delete Init.Data.Nat.Bitwise and Init.Data.Int.Bitwise (#11898)

The lemmas can easily be moved to Data.Nat.Bits and Data.Int.Bitwise respectively.

bdd38972

Diff

@@ -4,7 +4,6 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kevin Kappelmann, Kyle Miller, Mario Carneiro
 -/
 import Mathlib.Init.Data.Nat.Lemmas
-import Mathlib.Init.Data.Nat.Bitwise
 import Mathlib.Data.Nat.GCD.Basic
 import Mathlib.Logic.Function.Iterate
 import Mathlib.Data.Finset.NatAntidiagonal

92ca63f0

chore: remove tactics (#11365)

More tactics that are not used, found using the linter at #11308.

The PR consists of tactic removals, whitespace changes and replacing a porting note by an explanation.

c33c2724

Diff

@@ -168,8 +168,7 @@ theorem fib_coprime_fib_succ (n : ℕ) : Nat.Coprime (fib n) (fib (n + 1)) := by
 theorem fib_add (m n : ℕ) : fib (m + n + 1) = fib m * fib n + fib (m + 1) * fib (n + 1) := by
   induction' n with n ih generalizing m
   · simp
-  · intros
-    specialize ih (m + 1)
+  · specialize ih (m + 1)
     rw [add_assoc m 1 n, add_comm 1 n] at ih
     simp only [fib_add_two, ih]
     ring

92ca63f0

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -191,7 +191,7 @@ theorem fib_two_mul_add_one (n : ℕ) : fib (2 * n + 1) = fib (n + 1) ^ 2 + fib
 theorem fib_two_mul_add_two (n : ℕ) :
     fib (2 * n + 2) = fib (n + 1) * (2 * fib n + fib (n + 1)) := by
   rw [fib_add_two, fib_two_mul, fib_two_mul_add_one]
-  -- porting note: A bunch of issues similar to [this zulip thread](https://github.com/leanprover-community/mathlib4/pull/1576) with `zify`
+  -- Porting note: A bunch of issues similar to [this zulip thread](https://github.com/leanprover-community/mathlib4/pull/1576) with `zify`
   have : fib n ≤ 2 * fib (n + 1) :=
     le_trans (fib_le_fib_succ) (mul_comm 2 _ ▸ Nat.le_mul_of_pos_right _ two_pos)
   zify [this]

92ca63f0

fix: patch for std4#198 (more mul lemmas for Nat) (#6204)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

2f63d25e

Diff

@@ -193,7 +193,7 @@ theorem fib_two_mul_add_two (n : ℕ) :
   rw [fib_add_two, fib_two_mul, fib_two_mul_add_one]
   -- porting note: A bunch of issues similar to [this zulip thread](https://github.com/leanprover-community/mathlib4/pull/1576) with `zify`
   have : fib n ≤ 2 * fib (n + 1) :=
-    le_trans (fib_le_fib_succ) (mul_comm 2 _ ▸ le_mul_of_pos_right two_pos)
+    le_trans (fib_le_fib_succ) (mul_comm 2 _ ▸ Nat.le_mul_of_pos_right _ two_pos)
   zify [this]
   ring

92ca63f0

chore(*): replace $ with <| (#9319)

See Zulip thread for the discussion.

9f6d3388

Diff

@@ -128,12 +128,12 @@ theorem fib_add_two_strictMono : StrictMono fun n => fib (n + 2) := by
 #align nat.fib_add_two_strict_mono Nat.fib_add_two_strictMono
 
 lemma fib_strictMonoOn : StrictMonoOn fib (Set.Ici 2)
-  | _m + 2, _, _n + 2, _, hmn => fib_add_two_strictMono $ lt_of_add_lt_add_right hmn
+  | _m + 2, _, _n + 2, _, hmn => fib_add_two_strictMono <| lt_of_add_lt_add_right hmn
 
 lemma fib_lt_fib {m : ℕ} (hm : 2 ≤ m) : ∀ {n}, fib m < fib n ↔ m < n
   | 0 => by simp [hm]
   | 1 => by simp [hm]
-  | n + 2 => fib_strictMonoOn.lt_iff_lt hm $ by simp
+  | n + 2 => fib_strictMonoOn.lt_iff_lt hm <| by simp
 
 theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
   induction' five_le_n with n five_le_n IH
@@ -152,7 +152,7 @@ lemma le_fib_add_one : ∀ n, n ≤ fib n + 1
   | 2 => le_rfl
   | 3 => le_rfl
   | 4 => le_rfl
-  | _n + 5 => (le_fib_self le_add_self).trans $ le_succ _
+  | _n + 5 => (le_fib_self le_add_self).trans <| le_succ _
 
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/

92ca63f0

chore: remove uses of cases' (#9171)

I literally went through and regex'd some uses of cases', replacing them with rcases; this is meant to be a low effort PR as I hope that tools can do this in the future.

rcases is an easier replacement than cases, though with better tools we could in future do a second pass converting simple rcases added here (and existing ones) to cases.

3fca282c

Diff

@@ -267,7 +267,7 @@ theorem fast_fib_eq (n : ℕ) : fastFib n = fib n := by rw [fastFib, fast_fib_au
 #align nat.fast_fib_eq Nat.fast_fib_eq
 
 theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (fib n) := by
-  cases' Nat.eq_zero_or_pos n with h h
+  rcases Nat.eq_zero_or_pos n with h | h
   · rw [h]
     simp
   replace h := Nat.succ_pred_eq_of_pos h; rw [← h, succ_eq_add_one]

92ca63f0

chore: space after ← (#8178)

Co-authored-by: Moritz Firsching <firsching@google.com>

5fb9beab

Diff

@@ -285,7 +285,7 @@ theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (
 theorem gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m)) = gcd (fib m) (fib n)
   | 0 => by simp
   | k + 1 => by
-    rw [←gcd_fib_add_mul_self m n k,
+    rw [← gcd_fib_add_mul_self m n k,
       add_mul,
       ← add_assoc,
       one_mul,

92ca63f0

feat(Data.Finset.Antidiagonal): generalize Finset.Nat.antidiagonal (#7486)

We define a type class Finset.HasAntidiagonal A which contains a function antidiagonal : A → Finset (A × A) such that antidiagonal n is the Finset of all pairs adding to n, as witnessed by mem_antidiagonal.

When A is a canonically ordered add monoid with locally finite order this typeclass can be instantiated with Finset.antidiagonalOfLocallyFinite. This applies in particular when A is ℕ, more generally or σ →₀ ℕ, or even ι →₀ A under the additional assumption OrderedSub A that make it a canonically ordered add monoid. (In fact, we would just need an AddMonoid with a compatible order, finite Iic, such that if a + b = n, then a, b ≤ n, and any finiteness condition would be OK.)

For computational reasons it is better to manually provide instances for ℕ and σ →₀ ℕ, to avoid quadratic runtime performance. These instances are provided as Finset.Nat.instHasAntidiagonal and Finsupp.instHasAntidiagonal. This is why Finset.antidiagonalOfLocallyFinite is an abbrev and not an instance.

This definition does not exactly match with that of Multiset.antidiagonal defined in Mathlib.Data.Multiset.Antidiagonal, because of the multiplicities. Indeed, by counting multiplicities, Multiset α is equivalent to α →₀ ℕ, but Finset.antidiagonal and Multiset.antidiagonal will return different objects. For example, for s : Multiset ℕ := {0,0,0}, Multiset.antidiagonal s has 8 elements but Finset.antidiagonal s has only 4.

def s : Multiset ℕ := {0, 0, 0}
#eval (Finset.antidiagonal s).card -- 4
#eval Multiset.card (Multiset.antidiagonal s) -- 8

TODO

Define HasMulAntidiagonal (for monoids). For PNat, we will recover the set of divisors of a strictly positive integer.

This closes #7917

Co-authored by: María Inés de Frutos-Fernández <mariaines.dff@gmail.com> and Eric Wieser <efw27@cam.ac.uk>

Co-authored-by: Antoine Chambert-Loir <antoine.chambert-loir@math.univ-paris-diderot.fr> Co-authored-by: Mario Carneiro <di.gama@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

85a1f28f

Diff

@@ -308,7 +308,7 @@ theorem fib_dvd (m n : ℕ) (h : m ∣ n) : fib m ∣ fib n := by
 #align nat.fib_dvd Nat.fib_dvd
 
 theorem fib_succ_eq_sum_choose :
-    ∀ n : ℕ, fib (n + 1) = ∑ p in Finset.Nat.antidiagonal n, choose p.1 p.2 :=
+    ∀ n : ℕ, fib (n + 1) = ∑ p in Finset.antidiagonal n, choose p.1 p.2 :=
   twoStepInduction rfl rfl fun n h1 h2 => by
     rw [fib_add_two, h1, h2, Finset.Nat.antidiagonal_succ_succ', Finset.Nat.antidiagonal_succ']
     simp [choose_succ_succ, Finset.sum_add_distrib, add_left_comm]

92ca63f0

chore: exactly 4 spaces in theorems (#7328)

Co-authored-by: Moritz Firsching <firsching@google.com>

d3263b23

Diff

@@ -92,7 +92,7 @@ theorem fib_add_two {n : ℕ} : fib (n + 2) = fib n + fib (n + 1) := by
 #align nat.fib_add_two Nat.fib_add_two
 
 lemma fib_add_one : ∀ {n}, n ≠ 0 → fib (n + 1) = fib (n - 1) + fib n
-| _n + 1, _ => fib_add_two
+  | _n + 1, _ => fib_add_two
 
 theorem fib_le_fib_succ {n : ℕ} : fib n ≤ fib (n + 1) := by cases n <;> simp [fib_add_two]
 #align nat.fib_le_fib_succ Nat.fib_le_fib_succ
@@ -128,12 +128,12 @@ theorem fib_add_two_strictMono : StrictMono fun n => fib (n + 2) := by
 #align nat.fib_add_two_strict_mono Nat.fib_add_two_strictMono
 
 lemma fib_strictMonoOn : StrictMonoOn fib (Set.Ici 2)
-| _m + 2, _, _n + 2, _, hmn => fib_add_two_strictMono $ lt_of_add_lt_add_right hmn
+  | _m + 2, _, _n + 2, _, hmn => fib_add_two_strictMono $ lt_of_add_lt_add_right hmn
 
 lemma fib_lt_fib {m : ℕ} (hm : 2 ≤ m) : ∀ {n}, fib m < fib n ↔ m < n
-| 0 => by simp [hm]
-| 1 => by simp [hm]
-| n + 2 => fib_strictMonoOn.lt_iff_lt hm $ by simp
+  | 0 => by simp [hm]
+  | 1 => by simp [hm]
+  | n + 2 => fib_strictMonoOn.lt_iff_lt hm $ by simp
 
 theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
   induction' five_le_n with n five_le_n IH
@@ -147,12 +147,12 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
 #align nat.le_fib_self Nat.le_fib_self
 
 lemma le_fib_add_one : ∀ n, n ≤ fib n + 1
-| 0 => zero_le_one
-| 1 => one_le_two
-| 2 => le_rfl
-| 3 => le_rfl
-| 4 => le_rfl
-| _n + 5 => (le_fib_self le_add_self).trans $ le_succ _
+  | 0 => zero_le_one
+  | 1 => one_le_two
+  | 2 => le_rfl
+  | 3 => le_rfl
+  | 4 => le_rfl
+  | _n + 5 => (le_fib_self le_add_self).trans $ le_succ _
 
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/

92ca63f0

feat: Zeckendorf's theorem (#6880)

Prove Zeckendorf's theorem: Every natural number can be written uniquely as a sum of distinct non-consecutive Fibonacci numbers.

Instead of proving an ExistsUnique statement, I define an equivalence between natural numbers and Zeckendorf representations.

Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>

1d02ef70

Diff

@@ -91,6 +91,9 @@ theorem fib_add_two {n : ℕ} : fib (n + 2) = fib n + fib (n + 1) := by
   simp [fib, Function.iterate_succ_apply']
 #align nat.fib_add_two Nat.fib_add_two
 
+lemma fib_add_one : ∀ {n}, n ≠ 0 → fib (n + 1) = fib (n - 1) + fib n
+| _n + 1, _ => fib_add_two
+
 theorem fib_le_fib_succ {n : ℕ} : fib n ≤ fib (n + 1) := by cases n <;> simp [fib_add_two]
 #align nat.fib_le_fib_succ Nat.fib_le_fib_succ
 
@@ -99,10 +102,12 @@ theorem fib_mono : Monotone fib :=
   monotone_nat_of_le_succ fun _ => fib_le_fib_succ
 #align nat.fib_mono Nat.fib_mono
 
-theorem fib_pos {n : ℕ} (n_pos : 0 < n) : 0 < fib n :=
-  calc
-    0 < fib 1 := by decide
-    _ ≤ fib n := fib_mono n_pos
+@[simp] lemma fib_eq_zero : ∀ {n}, fib n = 0 ↔ n = 0
+| 0 => Iff.rfl
+| 1 => Iff.rfl
+| n + 2 => by simp [fib_add_two, fib_eq_zero]
+
+@[simp] lemma fib_pos {n : ℕ} : 0 < fib n ↔ 0 < n := by simp [pos_iff_ne_zero]
 #align nat.fib_pos Nat.fib_pos
 
 theorem fib_add_two_sub_fib_add_one {n : ℕ} : fib (n + 2) - fib (n + 1) = fib n := by
@@ -111,8 +116,8 @@ theorem fib_add_two_sub_fib_add_one {n : ℕ} : fib (n + 2) - fib (n + 1) = fib
 
 theorem fib_lt_fib_succ {n : ℕ} (hn : 2 ≤ n) : fib n < fib (n + 1) := by
   rcases exists_add_of_le hn with ⟨n, rfl⟩
-  rw [← tsub_pos_iff_lt, add_comm 2, fib_add_two_sub_fib_add_one]
-  apply fib_pos (succ_pos n)
+  rw [← tsub_pos_iff_lt, add_comm 2, fib_add_two_sub_fib_add_one, fib_pos]
+  exact succ_pos n
 #align nat.fib_lt_fib_succ Nat.fib_lt_fib_succ
 
 /-- `fib (n + 2)` is strictly monotone. -/
@@ -122,6 +127,14 @@ theorem fib_add_two_strictMono : StrictMono fun n => fib (n + 2) := by
   exact fib_lt_fib_succ (self_le_add_left _ _)
 #align nat.fib_add_two_strict_mono Nat.fib_add_two_strictMono
 
+lemma fib_strictMonoOn : StrictMonoOn fib (Set.Ici 2)
+| _m + 2, _, _n + 2, _, hmn => fib_add_two_strictMono $ lt_of_add_lt_add_right hmn
+
+lemma fib_lt_fib {m : ℕ} (hm : 2 ≤ m) : ∀ {n}, fib m < fib n ↔ m < n
+| 0 => by simp [hm]
+| 1 => by simp [hm]
+| n + 2 => fib_strictMonoOn.lt_iff_lt hm $ by simp
+
 theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
   induction' five_le_n with n five_le_n IH
   ·-- 5 ≤ fib 5
@@ -133,6 +146,14 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
       _ < fib (n + 1) := fib_lt_fib_succ (le_trans (by decide) five_le_n)
 #align nat.le_fib_self Nat.le_fib_self
 
+lemma le_fib_add_one : ∀ n, n ≤ fib n + 1
+| 0 => zero_le_one
+| 1 => one_le_two
+| 2 => le_rfl
+| 3 => le_rfl
+| 4 => le_rfl
+| _n + 5 => (le_fib_self le_add_self).trans $ le_succ _
+
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/
 theorem fib_coprime_fib_succ (n : ℕ) : Nat.Coprime (fib n) (fib (n + 1)) := by

92ca63f0

chore: bump to v4.1.0-rc1 (2nd attempt) (#7216)

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

bfaffcf1

Diff

@@ -135,12 +135,12 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
 
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/
-theorem fib_coprime_fib_succ (n : ℕ) : Nat.coprime (fib n) (fib (n + 1)) := by
+theorem fib_coprime_fib_succ (n : ℕ) : Nat.Coprime (fib n) (fib (n + 1)) := by
   induction' n with n ih
   · simp
   · rw [fib_add_two]
     simp only [coprime_add_self_right]
-    simp [coprime, ih.symm]
+    simp [Coprime, ih.symm]
 #align nat.fib_coprime_fib_succ Nat.fib_coprime_fib_succ
 
 /-- See https://proofwiki.org/wiki/Fibonacci_Number_in_terms_of_Smaller_Fibonacci_Numbers -/
@@ -258,7 +258,7 @@ theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (
     _ = gcd (fib m) (fib (n.pred + 1) * fib (m + 1)) := by
         rw [add_comm, gcd_add_mul_right_right (fib m) _ (fib n.pred)]
     _ = gcd (fib m) (fib (n.pred + 1)) :=
-      coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (coprime.symm (fib_coprime_fib_succ m))
+      Coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (Coprime.symm (fib_coprime_fib_succ m))
 #align nat.gcd_fib_add_self Nat.gcd_fib_add_self
 
 theorem gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m)) = gcd (fib m) (fib n)

92ca63f0

Revert "chore: bump to v4.1.0-rc1 (#7174)" (#7198)

This reverts commit 6f8e8104. Unfortunately this bump was not linted correctly, as CI did not run runLinter Mathlib.

We can unrevert once that's fixed.

40b58304

Diff

@@ -135,12 +135,12 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
 
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/
-theorem fib_coprime_fib_succ (n : ℕ) : Nat.Coprime (fib n) (fib (n + 1)) := by
+theorem fib_coprime_fib_succ (n : ℕ) : Nat.coprime (fib n) (fib (n + 1)) := by
   induction' n with n ih
   · simp
   · rw [fib_add_two]
     simp only [coprime_add_self_right]
-    simp [Coprime, ih.symm]
+    simp [coprime, ih.symm]
 #align nat.fib_coprime_fib_succ Nat.fib_coprime_fib_succ
 
 /-- See https://proofwiki.org/wiki/Fibonacci_Number_in_terms_of_Smaller_Fibonacci_Numbers -/
@@ -258,7 +258,7 @@ theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (
     _ = gcd (fib m) (fib (n.pred + 1) * fib (m + 1)) := by
         rw [add_comm, gcd_add_mul_right_right (fib m) _ (fib n.pred)]
     _ = gcd (fib m) (fib (n.pred + 1)) :=
-      Coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (Coprime.symm (fib_coprime_fib_succ m))
+      coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (coprime.symm (fib_coprime_fib_succ m))
 #align nat.gcd_fib_add_self Nat.gcd_fib_add_self
 
 theorem gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m)) = gcd (fib m) (fib n)

92ca63f0

chore: bump to v4.1.0-rc1 (#7174)

Some changes have already been review and delegated in #6910 and #7148.

The diff that needs looking at is https://github.com/leanprover-community/mathlib4/pull/7174/commits/64d6d07ee18163627c8f517eb31455411921c5ac

The std bump PR was insta-merged already!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

6f8e8104

Diff

@@ -135,12 +135,12 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
 
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/
-theorem fib_coprime_fib_succ (n : ℕ) : Nat.coprime (fib n) (fib (n + 1)) := by
+theorem fib_coprime_fib_succ (n : ℕ) : Nat.Coprime (fib n) (fib (n + 1)) := by
   induction' n with n ih
   · simp
   · rw [fib_add_two]
     simp only [coprime_add_self_right]
-    simp [coprime, ih.symm]
+    simp [Coprime, ih.symm]
 #align nat.fib_coprime_fib_succ Nat.fib_coprime_fib_succ
 
 /-- See https://proofwiki.org/wiki/Fibonacci_Number_in_terms_of_Smaller_Fibonacci_Numbers -/
@@ -258,7 +258,7 @@ theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (
     _ = gcd (fib m) (fib (n.pred + 1) * fib (m + 1)) := by
         rw [add_comm, gcd_add_mul_right_right (fib m) _ (fib n.pred)]
     _ = gcd (fib m) (fib (n.pred + 1)) :=
-      coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (coprime.symm (fib_coprime_fib_succ m))
+      Coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (Coprime.symm (fib_coprime_fib_succ m))
 #align nat.gcd_fib_add_self Nat.gcd_fib_add_self
 
 theorem gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m)) = gcd (fib m) (fib n)

92ca63f0

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,11 +2,6 @@
 Copyright (c) 2019 Kevin Kappelmann. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kevin Kappelmann, Kyle Miller, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.fib
-! leanprover-community/mathlib commit 92ca63f0fb391a9ca5f22d2409a6080e786d99f7
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Init.Data.Nat.Lemmas
 import Mathlib.Init.Data.Nat.Bitwise
@@ -17,6 +12,8 @@ import Mathlib.Algebra.BigOperators.Basic
 import Mathlib.Tactic.Ring
 import Mathlib.Tactic.Zify
 
+#align_import data.nat.fib from "leanprover-community/mathlib"@"92ca63f0fb391a9ca5f22d2409a6080e786d99f7"
+
 /-!
 # Fibonacci Numbers

92ca63f0

feat: port Init.Data.Nat.Lemmas (#5782)

Previously this was an ad-hoc port

5a78ace7

Diff

@@ -291,7 +291,7 @@ theorem fib_dvd (m n : ℕ) (h : m ∣ n) : fib m ∣ fib n := by
 
 theorem fib_succ_eq_sum_choose :
     ∀ n : ℕ, fib (n + 1) = ∑ p in Finset.Nat.antidiagonal n, choose p.1 p.2 :=
-  two_step_induction rfl rfl fun n h1 h2 => by
+  twoStepInduction rfl rfl fun n h1 h2 => by
     rw [fib_add_two, h1, h2, Finset.Nat.antidiagonal_succ_succ', Finset.Nat.antidiagonal_succ']
     simp [choose_succ_succ, Finset.sum_add_distrib, add_left_comm]
 #align nat.fib_succ_eq_sum_choose Nat.fib_succ_eq_sum_choose

92ca63f0

fix precedence of Nat.iterate (#5589)

bd2fff86

Diff

@@ -71,7 +71,7 @@ implementation.
 -- Porting note: Lean cannot find pp_nodot at the time of this port.
 -- @[pp_nodot]
 def fib (n : ℕ) : ℕ :=
-  (((fun p : ℕ × ℕ => (p.snd, p.fst + p.snd))^[n]) (0, 1)).fst
+  ((fun p : ℕ × ℕ => (p.snd, p.fst + p.snd))^[n] (0, 1)).fst
 #align nat.fib Nat.fib
 
 @[simp]

92ca63f0

port: Nat.fib extension for norm_num (#4036)

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

67093cd0

Diff

@@ -170,6 +170,15 @@ theorem fib_two_mul_add_one (n : ℕ) : fib (2 * n + 1) = fib (n + 1) ^ 2 + fib
   ring
 #align nat.fib_two_mul_add_one Nat.fib_two_mul_add_one
 
+theorem fib_two_mul_add_two (n : ℕ) :
+    fib (2 * n + 2) = fib (n + 1) * (2 * fib n + fib (n + 1)) := by
+  rw [fib_add_two, fib_two_mul, fib_two_mul_add_one]
+  -- porting note: A bunch of issues similar to [this zulip thread](https://github.com/leanprover-community/mathlib4/pull/1576) with `zify`
+  have : fib n ≤ 2 * fib (n + 1) :=
+    le_trans (fib_le_fib_succ) (mul_comm 2 _ ▸ le_mul_of_pos_right two_pos)
+  zify [this]
+  ring
+
 section deprecated
 
 set_option linter.deprecated false
@@ -186,13 +195,8 @@ theorem fib_bit0_succ (n : ℕ) : fib (bit0 n + 1) = fib (n + 1) ^ 2 + fib n ^ 2
   fib_bit1 n
 #align nat.fib_bit0_succ Nat.fib_bit0_succ
 
--- porting note: A bunch of issues similar to [this zulip thread](https://github.com/leanprover-community/mathlib4/pull/1576) with `zify`
 theorem fib_bit1_succ (n : ℕ) : fib (bit1 n + 1) = fib (n + 1) * (2 * fib n + fib (n + 1)) := by
-  rw [Nat.bit1_eq_succ_bit0, fib_add_two, fib_bit0, fib_bit0_succ]
-  have : fib n ≤ 2 * fib (n + 1) :=
-    le_trans (fib_le_fib_succ) (mul_comm 2 _ ▸ le_mul_of_pos_right two_pos)
-  zify [this]
-  ring
+  rw [Nat.bit1_eq_succ_bit0, bit0_eq_two_mul, fib_two_mul_add_two]
 #align nat.fib_bit1_succ Nat.fib_bit1_succ
 
 end deprecated
@@ -302,136 +306,3 @@ theorem fib_succ_eq_succ_sum (n : ℕ) : fib (n + 1) = (∑ k in Finset.range n,
 #align nat.fib_succ_eq_succ_sum Nat.fib_succ_eq_succ_sum
 
 end Nat
-
-namespace NormNum
-
-open Tactic Nat
-
-/-! ### `norm_num` plugin for `fib`
-
-The `norm_num` plugin uses a strategy parallel to that of `Nat.fastFib`, but it instead
-produces proofs of what `Nat.fib` evaluates to.
--/
-/-
-expected ')'
--/
-
-section deprecated
-
-set_option linter.deprecated false
-
-/-- Auxiliary definition for `prove_fib` plugin. -/
-def IsFibAux (n a b : ℕ) :=
-  fib n = a ∧ fib (n + 1) = b
-#align norm_num.is_fib_aux NormNum.IsFibAux
-
-theorem is_fib_aux_one : IsFibAux 1 1 1 :=
-  ⟨fib_one, fib_two⟩
-#align norm_num.is_fib_aux_one NormNum.is_fib_aux_one
-
-theorem is_fib_aux_bit0 {n a b c a2 b2 a' b' : ℕ} (H : IsFibAux n a b) (h1 : a + c = bit0 b)
-    (h2 : a * c = a') (h3 : a * a = a2) (h4 : b * b = b2) (h5 : a2 + b2 = b') :
-    IsFibAux (bit0 n) a' b' :=
-  ⟨by
-    rw [fib_bit0, H.1, H.2, ← bit0_eq_two_mul,
-      show bit0 b - a = c by rw [← h1, Nat.add_sub_cancel_left], h2],
-    by rw [fib_bit0_succ, H.1, H.2, pow_two, pow_two, h3, h4, add_comm, h5]⟩
-#align norm_num.is_fib_aux_bit0 NormNum.is_fib_aux_bit0
-
-theorem is_fib_aux_bit1 {n a b c a2 b2 a' b' : ℕ} (H : IsFibAux n a b) (h1 : a * a = a2)
-    (h2 : b * b = b2) (h3 : a2 + b2 = a') (h4 : bit0 a + b = c) (h5 : b * c = b') :
-    IsFibAux (bit1 n) a' b' :=
-  ⟨by rw [fib_bit1, H.1, H.2, pow_two, pow_two, h1, h2, add_comm, h3], by
-    rw [fib_bit1_succ, H.1, H.2, ← bit0_eq_two_mul, h4, h5]⟩
-#align norm_num.is_fib_aux_bit1 NormNum.is_fib_aux_bit1
-
-theorem is_fib_aux_bit0_done {n a b c a' : ℕ} (H : IsFibAux n a b) (h1 : a + c = bit0 b)
-    (h2 : a * c = a') : fib (bit0 n) = a' :=
-  (is_fib_aux_bit0 H h1 h2 rfl rfl rfl).1
-#align norm_num.is_fib_aux_bit0_done NormNum.is_fib_aux_bit0_done
-
-theorem is_fib_aux_bit1_done {n a b a2 b2 a' : ℕ} (H : IsFibAux n a b) (h1 : a * a = a2)
-    (h2 : b * b = b2) (h3 : a2 + b2 = a') : fib (bit1 n) = a' :=
-  (is_fib_aux_bit1 H h1 h2 h3 rfl rfl).1
-#align norm_num.is_fib_aux_bit1_done NormNum.is_fib_aux_bit1_done
-
-end deprecated
--- Porting note: This part of the file is tactic related
-/-
-/-- `prove_fib_aux ic n` returns `(ic', a, b, ⊢ is_fib_aux n a b)`, where `n` is a numeral. -/
-unsafe def prove_fib_aux (ic : instance_cache) : expr → tactic (instance_cache × expr × expr × expr)
-  | e =>
-    match match_numeral e with
-    | match_numeral_result.one => pure (ic, q((1 : ℕ)), q((1 : ℕ)), q(is_fib_aux_one))
-    | match_numeral_result.bit0 e => do
-      let (ic, a, b, H) ← prove_fib_aux e
-      let na ← a.toNat
-      let nb ← b.toNat
-      let (ic, c) ← ic.ofNat (2 * nb - na)
-      let (ic, h1) ← prove_add_nat ic a c (q((bit0 : ℕ → ℕ)).mk_app [b])
-      let (ic, a', h2) ← prove_mul_nat ic a c
-      let (ic, a2, h3) ← prove_mul_nat ic a a
-      let (ic, b2, h4) ← prove_mul_nat ic b b
-      let (ic, b', h5) ← prove_add_nat' ic a2 b2
-      pure
-          (ic, a', b',
-            q(@is_fib_aux_bit0).mk_app [e, a, b, c, a2, b2, a', b', H, h1, h2, h3, h4, h5])
-    | match_numeral_result.bit1 e => do
-      let (ic, a, b, H) ← prove_fib_aux e
-      let na ← a.toNat
-      let nb ← b.toNat
-      let (ic, c) ← ic.ofNat (2 * na + nb)
-      let (ic, a2, h1) ← prove_mul_nat ic a a
-      let (ic, b2, h2) ← prove_mul_nat ic b b
-      let (ic, a', h3) ← prove_add_nat' ic a2 b2
-      let (ic, h4) ← prove_add_nat ic (q((bit0 : ℕ → ℕ)).mk_app [a]) b c
-      let (ic, b', h5) ← prove_mul_nat ic b c
-      pure
-          (ic, a', b',
-            q(@is_fib_aux_bit1).mk_app [e, a, b, c, a2, b2, a', b', H, h1, h2, h3, h4, h5])
-    | _ => failed
-#align norm_num.prove_fib_aux NormNum.prove_fib_aux
-
-/-- A `norm_num` plugin for `fib n` when `n` is a numeral.
-Uses the binary representation of `n` like `Nat.fastFib`. -/
-unsafe def prove_fib (ic : instance_cache) (e : expr) : tactic (instance_cache × expr × expr) :=
-  match match_numeral e with
-  | match_numeral_result.zero => pure (ic, q((0 : ℕ)), q(fib_zero))
-  | match_numeral_result.one => pure (ic, q((1 : ℕ)), q(fib_one))
-  | match_numeral_result.bit0 e => do
-    let (ic, a, b, H) ← prove_fib_aux ic e
-    let na ← a.toNat
-    let nb ← b.toNat
-    let (ic, c) ← ic.ofNat (2 * nb - na)
-    let (ic, h1) ← prove_add_nat ic a c (q((bit0 : ℕ → ℕ)).mk_app [b])
-    let (ic, a', h2) ← prove_mul_nat ic a c
-    pure (ic, a', q(@is_fib_aux_bit0_done).mk_app [e, a, b, c, a', H, h1, h2])
-  | match_numeral_result.bit1 e => do
-    let (ic, a, b, H) ← prove_fib_aux ic e
-    let (ic, a2, h1) ← prove_mul_nat ic a a
-    let (ic, b2, h2) ← prove_mul_nat ic b b
-    let (ic, a', h3) ← prove_add_nat' ic a2 b2
-    pure (ic, a', q(@is_fib_aux_bit1_done).mk_app [e, a, b, a2, b2, a', H, h1, h2, h3])
-  | _ => failed
-#align norm_num.prove_fib NormNum.prove_fib
-
-/-- A `norm_num` plugin for `fib n` when `n` is a numeral.
-/-
-unknown identifier ''
--/
-Uses the binary representation of `n` like `Nat.fastFib`. -/
-@[norm_num]
-unsafe def eval_fib : expr → tactic (expr × expr)
-  | (fib $(en)) => do
-    let n ← en.toNat
-    match n with
-      | 0 => pure (q((0 : ℕ)), q(fib_zero))
-      | 1 => pure (q((1 : ℕ)), q(fib_one))
-      | 2 => pure (q((1 : ℕ)), q(fib_two))
-      | _ => do
-        let c ← mk_instance_cache q(ℕ)
-        Prod.snd <$> prove_fib c en
-  | _ => failed
-#align norm_num.eval_fib NormNum.eval_fib
--/
-end NormNum

92ca63f0

chore: fix upper/lowercase in comments (#4360)

Run a non-interactive version of fix-comments.py on all files.
Go through the diff and manually add/discard/edit chunks.

27d257fc

Diff

@@ -41,10 +41,10 @@ Definition of the Fibonacci sequence `F₀ = 0, F₁ = 1, Fₙ₊₂ = Fₙ + F
 - `Nat.fib_gcd`: `fib n` is a strong divisibility sequence.
 - `Nat.fib_succ_eq_sum_choose`: `fib` is given by the sum of `Nat.choose` along an antidiagonal.
 - `Nat.fib_succ_eq_succ_sum`: shows that `F₀ + F₁ + ⋯ + Fₙ = Fₙ₊₂ - 1`.
-- `Nat.fib_two_mul` and `nat.fib_two_mul_add_one` are the basis for an efficient algorithm to
+- `Nat.fib_two_mul` and `Nat.fib_two_mul_add_one` are the basis for an efficient algorithm to
   compute `fib` (see `Nat.fastFib`). There are `bit0`/`bit1` variants of these can be used to
-  simplify `fib` expressions: `simp only [nat.fib_bit0, nat.fib_bit1, nat.fib_bit0_succ,
-  nat.fib_bit1_succ, nat.fib_one, nat.fib_two]`.
+  simplify `fib` expressions: `simp only [Nat.fib_bit0, Nat.fib_bit1, Nat.fib_bit0_succ,
+  Nat.fib_bit1_succ, Nat.fib_one, Nat.fib_two]`.
 
 ## Implementation Notes
 
@@ -197,16 +197,16 @@ theorem fib_bit1_succ (n : ℕ) : fib (bit1 n + 1) = fib (n + 1) * (2 * fib n +
 
 end deprecated
 
-/-- Computes `(nat.fib n, nat.fib (n + 1))` using the binary representation of `n`.
-Supports `nat.fast_fib`. -/
+/-- Computes `(Nat.fib n, Nat.fib (n + 1))` using the binary representation of `n`.
+Supports `Nat.fastFib`. -/
 def fastFibAux : ℕ → ℕ × ℕ :=
   Nat.binaryRec (fib 0, fib 1) fun b _ p =>
     if b then (p.2 ^ 2 + p.1 ^ 2, p.2 * (2 * p.1 + p.2))
     else (p.1 * (2 * p.2 - p.1), p.2 ^ 2 + p.1 ^ 2)
 #align nat.fast_fib_aux Nat.fastFibAux
 
-/-- Computes `nat.fib n` using the binary representation of `n`.
-Proved to be equal to `nat.fib` in `nat.fast_fib_eq`. -/
+/-- Computes `Nat.fib n` using the binary representation of `n`.
+Proved to be equal to `Nat.fib` in `Nat.fast_fib_eq`. -/
 def fastFib (n : ℕ) : ℕ :=
   (fastFibAux n).1
 #align nat.fast_fib Nat.fastFib
@@ -309,8 +309,8 @@ open Tactic Nat
 
 /-! ### `norm_num` plugin for `fib`
 
-The `norm_num` plugin uses a strategy parallel to that of `nat.fast_fib`, but it instead
-produces proofs of what `nat.fib` evaluates to.
+The `norm_num` plugin uses a strategy parallel to that of `Nat.fastFib`, but it instead
+produces proofs of what `Nat.fib` evaluates to.
 -/
 /-
 expected ')'
@@ -393,7 +393,7 @@ unsafe def prove_fib_aux (ic : instance_cache) : expr → tactic (instance_cache
 #align norm_num.prove_fib_aux NormNum.prove_fib_aux
 
 /-- A `norm_num` plugin for `fib n` when `n` is a numeral.
-Uses the binary representation of `n` like `nat.fast_fib`. -/
+Uses the binary representation of `n` like `Nat.fastFib`. -/
 unsafe def prove_fib (ic : instance_cache) (e : expr) : tactic (instance_cache × expr × expr) :=
   match match_numeral e with
   | match_numeral_result.zero => pure (ic, q((0 : ℕ)), q(fib_zero))

92ca63f0

feat: add Mathlib.Tactic.Common, and import (#4056)

This makes a mathlib4 version of mathlib3's tactic.basic, now called Mathlib.Tactic.Common, which imports all tactics which do not have significant theory requirements, and then is imported all across the base of the hierarchy.

This ensures that all common tactics are available nearly everywhere in the library, rather than having to be imported one-by-one as you need them.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

a4eaf1c4

Diff

@@ -15,7 +15,6 @@ import Mathlib.Logic.Function.Iterate
 import Mathlib.Data.Finset.NatAntidiagonal
 import Mathlib.Algebra.BigOperators.Basic
 import Mathlib.Tactic.Ring
-import Mathlib.Tactic.WLOG
 import Mathlib.Tactic.Zify
 
 /-!

92ca63f0

chore: fix #align lines (#3640)

This PR fixes two things:

Most align statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align). This is often seen in the mathport output after ending calc blocks.
All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)

2b42dc7c

Diff

@@ -107,30 +107,26 @@ theorem fib_pos {n : ℕ} (n_pos : 0 < n) : 0 < fib n :=
   calc
     0 < fib 1 := by decide
     _ ≤ fib n := fib_mono n_pos
-
 #align nat.fib_pos Nat.fib_pos
 
 theorem fib_add_two_sub_fib_add_one {n : ℕ} : fib (n + 2) - fib (n + 1) = fib n := by
   rw [fib_add_two, add_tsub_cancel_right]
 #align nat.fib_add_two_sub_fib_add_one Nat.fib_add_two_sub_fib_add_one
 
-theorem fib_lt_fib_succ {n : ℕ} (hn : 2 ≤ n) : fib n < fib (n + 1) :=
-  by
+theorem fib_lt_fib_succ {n : ℕ} (hn : 2 ≤ n) : fib n < fib (n + 1) := by
   rcases exists_add_of_le hn with ⟨n, rfl⟩
   rw [← tsub_pos_iff_lt, add_comm 2, fib_add_two_sub_fib_add_one]
   apply fib_pos (succ_pos n)
 #align nat.fib_lt_fib_succ Nat.fib_lt_fib_succ
 
 /-- `fib (n + 2)` is strictly monotone. -/
-theorem fib_add_two_strictMono : StrictMono fun n => fib (n + 2) :=
-  by
+theorem fib_add_two_strictMono : StrictMono fun n => fib (n + 2) := by
   refine' strictMono_nat_of_lt_succ fun n => _
   rw [add_right_comm]
   exact fib_lt_fib_succ (self_le_add_left _ _)
 #align nat.fib_add_two_strict_mono Nat.fib_add_two_strictMono
 
-theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n :=
-  by
+theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n := by
   induction' five_le_n with n five_le_n IH
   ·-- 5 ≤ fib 5
     rfl
@@ -139,13 +135,11 @@ theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n :=
     calc
       n ≤ fib n := IH
       _ < fib (n + 1) := fib_lt_fib_succ (le_trans (by decide) five_le_n)
-
 #align nat.le_fib_self Nat.le_fib_self
 
 /-- Subsequent Fibonacci numbers are coprime,
   see https://proofwiki.org/wiki/Consecutive_Fibonacci_Numbers_are_Coprime -/
-theorem fib_coprime_fib_succ (n : ℕ) : Nat.coprime (fib n) (fib (n + 1)) :=
-  by
+theorem fib_coprime_fib_succ (n : ℕ) : Nat.coprime (fib n) (fib (n + 1)) := by
   induction' n with n ih
   · simp
   · rw [fib_add_two]
@@ -154,8 +148,7 @@ theorem fib_coprime_fib_succ (n : ℕ) : Nat.coprime (fib n) (fib (n + 1)) :=
 #align nat.fib_coprime_fib_succ Nat.fib_coprime_fib_succ
 
 /-- See https://proofwiki.org/wiki/Fibonacci_Number_in_terms_of_Smaller_Fibonacci_Numbers -/
-theorem fib_add (m n : ℕ) : fib (m + n + 1) = fib m * fib n + fib (m + 1) * fib (n + 1) :=
-  by
+theorem fib_add (m n : ℕ) : fib (m + n + 1) = fib m * fib n + fib (m + 1) * fib (n + 1) := by
   induction' n with n ih generalizing m
   · simp
   · intros
@@ -165,8 +158,7 @@ theorem fib_add (m n : ℕ) : fib (m + n + 1) = fib m * fib n + fib (m + 1) * fi
     ring
 #align nat.fib_add Nat.fib_add
 
-theorem fib_two_mul (n : ℕ) : fib (2 * n) = fib n * (2 * fib (n + 1) - fib n) :=
-  by
+theorem fib_two_mul (n : ℕ) : fib (2 * n) = fib n * (2 * fib (n + 1) - fib n) := by
   cases n
   · simp
   · rw [Nat.succ_eq_add_one, two_mul, ← add_assoc, fib_add, fib_add_two, two_mul]
@@ -174,8 +166,7 @@ theorem fib_two_mul (n : ℕ) : fib (2 * n) = fib n * (2 * fib (n + 1) - fib n)
     ring
 #align nat.fib_two_mul Nat.fib_two_mul
 
-theorem fib_two_mul_add_one (n : ℕ) : fib (2 * n + 1) = fib (n + 1) ^ 2 + fib n ^ 2 :=
-  by
+theorem fib_two_mul_add_one (n : ℕ) : fib (2 * n + 1) = fib (n + 1) ^ 2 + fib n ^ 2 := by
   rw [two_mul, fib_add]
   ring
 #align nat.fib_two_mul_add_one Nat.fib_two_mul_add_one
@@ -224,8 +215,7 @@ def fastFib (n : ℕ) : ℕ :=
 theorem fast_fib_aux_bit_ff (n : ℕ) :
     fastFibAux (bit false n) =
       let p := fastFibAux n
-      (p.1 * (2 * p.2 - p.1), p.2 ^ 2 + p.1 ^ 2) :=
-  by
+      (p.1 * (2 * p.2 - p.1), p.2 ^ 2 + p.1 ^ 2) := by
   rw [fastFibAux, binaryRec_eq]
   · rfl
   · simp
@@ -234,15 +224,13 @@ theorem fast_fib_aux_bit_ff (n : ℕ) :
 theorem fast_fib_aux_bit_tt (n : ℕ) :
     fastFibAux (bit true n) =
       let p := fastFibAux n
-      (p.2 ^ 2 + p.1 ^ 2, p.2 * (2 * p.1 + p.2)) :=
-  by
+      (p.2 ^ 2 + p.1 ^ 2, p.2 * (2 * p.1 + p.2)) := by
   rw [fastFibAux, binaryRec_eq]
   · rfl
   · simp
 #align nat.fast_fib_aux_bit_tt Nat.fast_fib_aux_bit_tt
 
-theorem fast_fib_aux_eq (n : ℕ) : fastFibAux n = (fib n, fib (n + 1)) :=
-  by
+theorem fast_fib_aux_eq (n : ℕ) : fastFibAux n = (fib n, fib (n + 1)) := by
   apply Nat.binaryRec _ (fun b n' ih => _) n
   · simp [fastFibAux]
   · intro b
@@ -264,16 +252,13 @@ theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (
   replace h := Nat.succ_pred_eq_of_pos h; rw [← h, succ_eq_add_one]
   calc
     gcd (fib m) (fib (n.pred + 1 + m)) =
-        gcd (fib m) (fib n.pred * fib m + fib (n.pred + 1) * fib (m + 1)) :=
-      by
+        gcd (fib m) (fib n.pred * fib m + fib (n.pred + 1) * fib (m + 1)) := by
         rw [← fib_add n.pred _]
         ring_nf
-    _ = gcd (fib m) (fib (n.pred + 1) * fib (m + 1)) :=
-      by
+    _ = gcd (fib m) (fib (n.pred + 1) * fib (m + 1)) := by
         rw [add_comm, gcd_add_mul_right_right (fib m) _ (fib n.pred)]
     _ = gcd (fib m) (fib (n.pred + 1)) :=
       coprime.gcd_mul_right_cancel_right (fib (n.pred + 1)) (coprime.symm (fib_coprime_fib_succ m))
-
 #align nat.gcd_fib_add_self Nat.gcd_fib_add_self
 
 theorem gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m)) = gcd (fib m) (fib n)
@@ -303,22 +288,18 @@ theorem fib_dvd (m n : ℕ) (h : m ∣ n) : fib m ∣ fib n := by
 
 theorem fib_succ_eq_sum_choose :
     ∀ n : ℕ, fib (n + 1) = ∑ p in Finset.Nat.antidiagonal n, choose p.1 p.2 :=
-  two_step_induction rfl rfl fun n h1 h2 =>
-    by
+  two_step_induction rfl rfl fun n h1 h2 => by
     rw [fib_add_two, h1, h2, Finset.Nat.antidiagonal_succ_succ', Finset.Nat.antidiagonal_succ']
     simp [choose_succ_succ, Finset.sum_add_distrib, add_left_comm]
 #align nat.fib_succ_eq_sum_choose Nat.fib_succ_eq_sum_choose
 
-theorem fib_succ_eq_succ_sum (n : ℕ) : fib (n + 1) = (∑ k in Finset.range n, fib k) + 1 :=
-  by
+theorem fib_succ_eq_succ_sum (n : ℕ) : fib (n + 1) = (∑ k in Finset.range n, fib k) + 1 := by
   induction' n with n ih
   · simp
-  ·
-    calc
+  · calc
       fib (n + 2) = fib n + fib (n + 1) := fib_add_two
       _ = (fib n + ∑ k in Finset.range n, fib k) + 1 := by rw [ih, add_assoc]
       _ = (∑ k in Finset.range (n + 1), fib k) + 1 := by simp [Finset.range_add_one]
-
 #align nat.fib_succ_eq_succ_sum Nat.fib_succ_eq_succ_sum
 
 end Nat

92ca63f0

chore: bump to nightly-2023-04-11 (#3139)

1cd8b316

Diff

@@ -202,7 +202,7 @@ theorem fib_bit1_succ (n : ℕ) : fib (bit1 n + 1) = fib (n + 1) * (2 * fib n +
   have : fib n ≤ 2 * fib (n + 1) :=
     le_trans (fib_le_fib_succ) (mul_comm 2 _ ▸ le_mul_of_pos_right two_pos)
   zify [this]
-  ring_nf
+  ring
 #align nat.fib_bit1_succ Nat.fib_bit1_succ
 
 end deprecated

92ca63f0

chore: sync Data. Nat.Fib (#3150)

836642a3

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kevin Kappelmann, Kyle Miller, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.nat.fib
-! leanprover-community/mathlib commit 008205aa645b3f194c1da47025c5f110c8406eab
+! leanprover-community/mathlib commit 92ca63f0fb391a9ca5f22d2409a6080e786d99f7
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -15,17 +15,15 @@ import Mathlib.Logic.Function.Iterate
 import Mathlib.Data.Finset.NatAntidiagonal
 import Mathlib.Algebra.BigOperators.Basic
 import Mathlib.Tactic.Ring
+import Mathlib.Tactic.WLOG
 import Mathlib.Tactic.Zify
+
 /-!
 # Fibonacci Numbers
 
 This file defines the fibonacci series, proves results about it and introduces
 methods to compute it quickly.
 -/
--- porting note: Previously `Mathlib.Tactic.Wlog` was imported.
--- This is no longer needed because the `wlog` tactic was only used once
--- in the proof of `fib_gcd` in mathlib3. That occurrence has been rewritten using `cases`.
--- The reason : `wlog` has not yet been ported at the time of the porting of this file.
 
 /-!
 # The Fibonacci Sequence
@@ -291,25 +289,12 @@ theorem gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m))
 /-- `fib n` is a strong divisibility sequence,
   see https://proofwiki.org/wiki/GCD_of_Fibonacci_Numbers -/
 theorem fib_gcd (m n : ℕ) : fib (gcd m n) = gcd (fib m) (fib n) := by
-  cases' le_total m n with h h
-  case inl =>
-      apply @Nat.gcd.induction _ m n
-      case H0 => simp
-      intro n m _ h
-      rw [←gcd_rec n m] at h
-      conv_rhs =>
-        rw [← mod_add_div' m n]
-      rw [gcd_fib_add_mul_self n (m % n) (m / n)]
-      rwa [gcd_comm (fib n)]
-  case inr =>
-    apply @Nat.gcd.induction _ m n
-    case H0 => simp
-    intro n m _ h
-    rw [←gcd_rec n m] at h
-    conv_rhs =>
-      rw [← mod_add_div' m n]
-    rw [gcd_fib_add_mul_self n (m % n) (m / n)]
-    rwa [gcd_comm (fib n) _]
+  induction m, n using Nat.gcd.induction with
+  | H0 => simp
+  | H1 m n _ h' =>
+    rw [← gcd_rec m n] at h'
+    conv_rhs => rw [← mod_add_div' n m]
+    rwa [gcd_fib_add_mul_self m (n % m) (n / m), gcd_comm (fib m) _]
 #align nat.fib_gcd Nat.fib_gcd
 
 theorem fib_dvd (m n : ℕ) (h : m ∣ n) : fib m ∣ fib n := by

008205aa

Refactor uses to rename_i that have easy fixes (#2429)

ffbbaaae

Diff

@@ -260,11 +260,9 @@ theorem fast_fib_eq (n : ℕ) : fastFib n = fib n := by rw [fastFib, fast_fib_au
 #align nat.fast_fib_eq Nat.fast_fib_eq
 
 theorem gcd_fib_add_self (m n : ℕ) : gcd (fib m) (fib (n + m)) = gcd (fib m) (fib n) := by
-  cases Nat.eq_zero_or_pos n
-  · rename_i h
-    rw [h]
+  cases' Nat.eq_zero_or_pos n with h h
+  · rw [h]
     simp
-  rename_i h
   replace h := Nat.succ_pred_eq_of_pos h; rw [← h, succ_eq_add_one]
   calc
     gcd (fib m) (fib (n.pred + 1 + m)) =
@@ -293,7 +291,7 @@ theorem gcd_fib_add_mul_self (m n : ℕ) : ∀ k, gcd (fib m) (fib (n + k * m))
 /-- `fib n` is a strong divisibility sequence,
   see https://proofwiki.org/wiki/GCD_of_Fibonacci_Numbers -/
 theorem fib_gcd (m n : ℕ) : fib (gcd m n) = gcd (fib m) (fib n) := by
-  cases le_total m n <;> rename_i h
+  cases' le_total m n with h h
   case inl =>
       apply @Nat.gcd.induction _ m n
       case H0 => simp

008205aa

feat: quick version of mono tactic (#1740)

This is an extremely partial port of the mono* tactic from Lean 3, implemented as a macro on top of solve_by_elim. The original mono had many configuration options and no documentation, so quite a bit is missing (and almost all the Lean 3 tests fail). Nonetheless I think it's worth merging this, because

it will get rid of errors in mathport output which come from lemmas being tagged with a nonexistent attribute @[mono]
in most mathlib3 uses of mono, only the basic version was used, not the various configuration options; thus I would guess that this version of mono will succeed fairly often in the port even though it fails nearly all the tests

Co-authored-by: thorimur <68410468+thorimur@users.noreply.github.com>

cdd6d9c6

Diff

@@ -100,8 +100,7 @@ theorem fib_add_two {n : ℕ} : fib (n + 2) = fib n + fib (n + 1) := by
 theorem fib_le_fib_succ {n : ℕ} : fib n ≤ fib (n + 1) := by cases n <;> simp [fib_add_two]
 #align nat.fib_le_fib_succ Nat.fib_le_fib_succ
 
--- porting note: At the time of this port in time attribute @[mono] is unknown
--- @[mono]
+@[mono]
 theorem fib_mono : Monotone fib :=
   monotone_nat_of_le_succ fun _ => fib_le_fib_succ
 #align nat.fib_mono Nat.fib_mono

008205aa

chore: scoped BigOperators notation (#1952)

e707fa67

Diff

@@ -58,8 +58,7 @@ For efficiency purposes, the sequence is defined using `Stream.iterate`.
 fib, fibonacci
 -/
 
---Porting note: commented out
---open BigOperators
+open BigOperators
 
 namespace Nat

008205aa

chore: tidy various files (#1693)

cff6012d

Diff

@@ -126,12 +126,12 @@ theorem fib_lt_fib_succ {n : ℕ} (hn : 2 ≤ n) : fib n < fib (n + 1) :=
 #align nat.fib_lt_fib_succ Nat.fib_lt_fib_succ
 
 /-- `fib (n + 2)` is strictly monotone. -/
-theorem fib_add_two_strict_mono : StrictMono fun n => fib (n + 2) :=
+theorem fib_add_two_strictMono : StrictMono fun n => fib (n + 2) :=
   by
   refine' strictMono_nat_of_lt_succ fun n => _
   rw [add_right_comm]
   exact fib_lt_fib_succ (self_le_add_left _ _)
-#align nat.fib_add_two_strict_mono Nat.fib_add_two_strict_mono
+#align nat.fib_add_two_strict_mono Nat.fib_add_two_strictMono
 
 theorem le_fib_self {n : ℕ} (five_le_n : 5 ≤ n) : n ≤ fib n :=
   by

008205aa

feat: port Data.Nat.Fib (#1644)

Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com>

4260082a

`data.nat.fib` ⟷ `Mathlib.Data.Nat.Fib.Basic`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

TODO

Dependencies 3 + 192

data.nat.fib ⟷ Mathlib.Data.Nat.Fib.Basic

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

TODO

Dependencies 3 + 192

`data.nat.fib` ⟷ `Mathlib.Data.Nat.Fib.Basic`