AFTD Auto-Formalizing Theoretical Domains

pell_number_closed_form

theoremverifiedformalization

For every natural number m, twice the m-th Pell number equals ((1 + Real.sqrt 2) ^ m - (1 - Real.sqrt 2) ^ m) / Real.sqrt 2.

Statement

theorem pell_number_closed_form (m : ℕ) :
    (2 * (pell_number m : ℝ)) =
      ((1 + Real.sqrt 2) ^ m - (1 - Real.sqrt 2) ^ m) / Real.sqrt 2
Formalizes
arXiv:2610.08525 Appendix A
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • pell_numberThe Pell numbers are defined by P(0) = 0, P(1) = 1, and P(m+2) = P(m) + 2 P(m+1).

Read back from the Lean

For every natural number $m$, twice the value of pell_number m (cast to the real numbers) is equal to $\frac{(1 + \sqrt{2})^m - (1 - \sqrt{2})^m}{\sqrt{2}}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof establishes the Binet-style formula P(m) = ((1 + √2)^m - (1 - √2)^m) / (2√2) for all m by two-step induction on ℕ. The base cases m = 0 and m = 1 are verified directly from the definition of the Pell numbers. In the induction step, the recurrence relation P(k + 2) = 2 P(k + 1) + P(k) is matched to the characteristic equation x^2 = 2x + 1 satisfied by both 1 + √2 and 1 - √2. Finally, multiplying the closed form by 2 and canceling 2 from the denominator yields the desired result.

  1. The characteristic roots a = 1 + √2 and b = 1 - √2 satisfy a^2 = 2a + 1 and b^2 = 2b + 1, and 2√2 ≠ 0.

    Using the fact that (√2)^2 = 2 (by `Real.sq_sqrt`), we define the roots a = 1 + √2 and b = 1 - √2. Positivity verifies that 2√2 ≠ 0. Expanding (1 ± √2)^2 shows that both roots satisfy the characteristic polynomial equation x^2 = 2x + 1.

    lines 5–10

    uses Real.sq_sqrt

      have hsq2 : Real.sqrt 2 ^ 2 = 2 := Real.sq_sqrt (by norm_num)
      set a : ℝ := 1 + Real.sqrt 2 with ha_def
      set b : ℝ := 1 - Real.sqrt 2 with hb_def
      have hsqrt2_ne : (2 * Real.sqrt 2 : ℝ) ≠ 0 := by positivity
      have a_sq : a ^ 2 = 2 * a + 1 := by rw [ha_def]; nlinarith
      have b_sq : b ^ 2 = 2 * b + 1 := by rw [hb_def]; nlinarith
  2. The closed form P(n) = (a^n - b^n) / (2√2) holds for the base case n = 0.

    We set up a two-step induction on n via `Nat.twoStepInduction`. For n = 0, P(0) = 0 by `pell_number.eq_1`, and the numerator is a^0 - b^0 = 1 - 1 = 0, so both sides vanish.

    lines 11–14

    uses Nat.twoStepInduction, pell_number.eq_1

      have closed_form : ∀ m : ℕ, (pell_number m : ℝ) = (a ^ m - b ^ m) / (2 * Real.sqrt 2) := by
        intro n
        induction n using Nat.twoStepInduction with
        | zero => simp [pell_number.eq_1]
  3. The closed form holds for the base case n = 1.

    For n = 1, using `pow_one` gives a^1 - b^1 = a - b = (1 + √2) - (1 - √2) = 2√2. Since P(1) = 1 by `pell_number.eq_2` and 2√2 ≠ 0, the right-hand side simplifies to (2√2) / (2√2) = 1 via `div_self`.

    lines 15–19

    uses pow_one, pell_number.eq_2, div_self

        | one =>
          have h1 : a ^ 1 - b ^ 1 = 2 * Real.sqrt 2 := by
            rw [pow_one, pow_one, ha_def, hb_def]; ring
          rw [pell_number.eq_2, h1, div_self hsqrt2_ne]
          norm_num
  4. Assuming the closed form holds for k and k + 1, it holds for k + 2.

    Using the characteristic identities a^2 = 2a + 1 and b^2 = 2b + 1 together with the law of exponents (`pow_add`), algebra confirms that a^(k+2) - b^(k+2) = 2(a^(k+1) - b^(k+1)) + (a^k - b^k). Rewriting P(k + 2) via the recurrence relation `pell_number.eq_3`, casting to real numbers, and substituting the induction hypotheses (`ih1` and `ih2`), ring arithmetic shows that the linear combination of the closed forms for k and k + 1 matches the closed form for k + 2.

    lines 20–28

    uses pow_add, pell_number.eq_3

        | more k ih1 ih2 =>
          have hstep : a ^ (k + 2) - b ^ (k + 2) = 2 * (a ^ (k + 1) - b ^ (k + 1)) + (a ^ k - b ^ k) := by
            rw [pow_add, pow_add, pow_add, pow_add, a_sq, b_sq]
            ring
          change ((pell_number (k + 2) : ℕ) : ℝ) = (a ^ (k + 2) - b ^ (k + 2)) / (2 * Real.sqrt 2)
          rw [show k + 2 = k.succ.succ from rfl, pell_number.eq_3, hstep]
          push_cast
          rw [ih1, ih2]
          ring
  5. Twice the m-th Pell number equals ((1 + √2)^m - (1 - √2)^m) / √2.

    Applying the closed form `closed_form m` expresses 2 * P(m) as 2 * ((a^m - b^m) / (2√2)). Associating 2 into the numerator with `mul_div_assoc'` and canceling the common factor of 2 from the numerator and denominator using `mul_div_mul_left` completes the proof.

    lines 29–32

    uses mul_div_assoc', mul_div_mul_left

      rw [closed_form m]
      calc 2 * ((a ^ m - b ^ m) / (2 * Real.sqrt 2))
        _ = (2 * (a ^ m - b ^ m)) / (2 * Real.sqrt 2) := mul_div_assoc' 2 (a ^ m - b ^ m) (2 * Real.sqrt 2)
        _ = (a ^ m - b ^ m) / Real.sqrt 2 := mul_div_mul_left (a ^ m - b ^ m) (Real.sqrt 2) (by norm_num)
Real.sq_sqrt
The square of the square root of a non-negative real number x is x: (√x)^2 = x.
Nat.twoStepInduction
Principle of two-step mathematical induction on ℕ: to prove a property for all n, it suffices to establish it for 0 and 1, and show that it holds for n + 2 whenever it holds for n and n + 1.
pell_number.eq_1
The 0-th Pell number equals 0.
pow_one
Any element raised to the power 1 equals itself: a^1 = a.
pell_number.eq_2
The 1st Pell number equals 1.
div_self
Any non-zero element divided by itself equals 1: a / a = 1.
pow_add
Exponents add when multiplying powers of the same base: a^(m + n) = a^m * a^n.
pell_number.eq_3
The defining recurrence for Pell numbers: P(m + 2) = P(m) + 2 * P(m + 1).
mul_div_assoc'
Multiplying by a fraction equals multiplying its numerator: a * (b / c) = (a * b) / c.
mul_div_mul_left
A non-zero factor c in the numerator and denominator can be cancelled: (c * a) / (c * b) = a / b.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Closed-form Binet-type expression for the Pell numbers in terms of 1 ± √2. -/theorem pell_number_closed_form (m : ℕ) :    (2 * (pell_number m : ℝ)) =      ((1 + Real.sqrt 2) ^ m - (1 - Real.sqrt 2) ^ m) / Real.sqrt 2 := by  have hsq2 : Real.sqrt 2 ^ 2 = 2 := Real.sq_sqrt (by norm_num)  set a : ℝ := 1 + Real.sqrt 2 with ha_def  set b : ℝ := 1 - Real.sqrt 2 with hb_def  have hsqrt2_ne : (2 * Real.sqrt 2 : ℝ) ≠ 0 := by positivity  have a_sq : a ^ 2 = 2 * a + 1 := by rw [ha_def]; nlinarith  have b_sq : b ^ 2 = 2 * b + 1 := by rw [hb_def]; nlinarith  have closed_form : ∀ m : ℕ, (pell_number m : ℝ) = (a ^ m - b ^ m) / (2 * Real.sqrt 2) := by    intro n    induction n using Nat.twoStepInduction with    | zero => simp [pell_number.eq_1]    | one =>      have h1 : a ^ 1 - b ^ 1 = 2 * Real.sqrt 2 := by        rw [pow_one, pow_one, ha_def, hb_def]; ring      rw [pell_number.eq_2, h1, div_self hsqrt2_ne]      norm_num    | more k ih1 ih2 =>      have hstep : a ^ (k + 2) - b ^ (k + 2) = 2 * (a ^ (k + 1) - b ^ (k + 1)) + (a ^ k - b ^ k) := by        rw [pow_add, pow_add, pow_add, pow_add, a_sq, b_sq]        ring      change ((pell_number (k + 2) : ℕ) : ℝ) = (a ^ (k + 2) - b ^ (k + 2)) / (2 * Real.sqrt 2)      rw [show k + 2 = k.succ.succ from rfl, pell_number.eq_3, hstep]      push_cast      rw [ih1, ih2]      ring  rw [closed_form m]  calc 2 * ((a ^ m - b ^ m) / (2 * Real.sqrt 2))    _ = (2 * (a ^ m - b ^ m)) / (2 * Real.sqrt 2) := mul_div_assoc' 2 (a ^ m - b ^ m) (2 * Real.sqrt 2)    _ = (a ^ m - b ^ m) / Real.sqrt 2 := mul_div_mul_left (a ^ m - b ^ m) (Real.sqrt 2) (by norm_num)
See it in the graphDiscuss this resultChallenge it