Pell number

Pell numbers form an integer sequence defined by the recurrence relation P_n = 2P_{n-1} + P_{n-2} for n \geq 2, with initial conditions P_0 = 0 and P_1 = 1, yielding the terms 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, and so on.^[1]^[2] These numbers arise as the companion sequence to the Pell-Lucas numbers within the broader family of Lucas sequences, specifically those parameterized by P = 2 and Q = -1, and they can also be expressed using the Fibonacci polynomials evaluated at 2, i.e., P_n = F_n(2).^[1] A closed-form expression, analogous to Binet's formula for Fibonacci numbers, is given by P_n = \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2\sqrt{2}}, which highlights their connection to the irrational number \sqrt{2}.^[1]^[2] Named after the English mathematician John Pell (1611–1685), though the sequence was first systematically studied by Édouard Lucas in 1878, Pell numbers play a central role in solving Pell's equation x^2 - 2y^2 = \pm 1, where the solutions (x_n, y_n) satisfy x_n + y_n \sqrt{2} = (1 + \sqrt{2})^n, with y_n = P_n.^[2] The denominators of the convergents in the continued fraction expansion of \sqrt{2} are precisely the Pell numbers, making them fundamental to rational approximations of this quadratic irrational.^[2] Key properties include their strong divisibility—\gcd(P_m, P_n) = P_{\gcd(m,n)}—and the fact that the ratio P_n / P_{n-1} approaches $1 + \sqrt{2} as n increases, reflecting the dominant root of the characteristic equation.^[2]^[1] Pell numbers appear in various combinatorial contexts, such as counting the number of lattice paths from (0,0) to the line x=n using steps (1,1), (1,-1), and (2,0) that do not go below the x-axis, or the number of ways to tile a cylindrical 2 × (n-1) board with dominoes.^[2] They also enumerate 132-avoiding two-stack sortable permutations of length n.^[2] While most Pell numbers are composite, those at prime indices can be prime, with the largest known probable prime Pell number occurring at index 90197, comprising 34,525 digits.^[1] The generating function for the sequence is \frac{x}{1 - 2x - x^2}, facilitating further algebraic manipulations and identities, such as the addition formula P_{m+n} = P_{m+1} P_n + P_m P_{n-1}.^[2]^[1]

Fundamentals

Definition

The Pell numbers P_n are defined by the initial values P_0 = 0, P_1 = 1, and the recurrence relation P_n = 2 P_{n-1} + P_{n-2} for n \geq 2.^[1]^[2] They form an infinite sequence of nonnegative integers that also arise as the denominators of the convergents in the continued fraction expansion of \sqrt{2}.^[2] Although the Pell numbers are named for the 17th-century English mathematician John Pell, the underlying concepts were known to ancient Indian mathematicians as early as the 7th century through the work of Brahmagupta.^[3] The naming convention stems from an erroneous attribution by Leonhard Euler, who in the mid-18th century credited Pell with earlier European contributions to the equation.^[4] Euler himself provided the first explicit modern description of the sequence in his investigations of continued fractions, notably in his 1737 dissertation and subsequent 1759 paper linking them to Diophantine equations.^[5] The first ten Pell numbers are listed below for illustration:

n	P_n
0	0
1	1
2	2
3	5
4	12
5	29
6	70
7	169
8	408
9	985

^[2]

Sequence and Examples

The Pell numbers P_n are defined for nonnegative integers n by the initial values P_0 = 0, P_1 = 1, and the recurrence relation P_n = 2 P_{n-1} + P_{n-2} for n \geq 2.^[1]^[2] To compute the first few terms, begin with P_2 = 2 \cdot 1 + 0 = 2, P_3 = 2 \cdot 2 + 1 = 5, P_4 = 2 \cdot 5 + 2 = 12, P_5 = 2 \cdot 12 + 5 = 29, and P_6 = 2 \cdot 29 + 12 = 70. This iterative addition process generates the sequence rapidly, with each term depending directly on the two preceding ones.^[1] The sequence extends to negative indices using the relation P_{-n} = (-1)^{n+1} P_n for positive integers n, which preserves the recurrence relation bidirectionally.^[6] For example, P_{-1} = (-1)^{2} \cdot 1 = 1, P_{-2} = (-1)^{3} \cdot 2 = -2, and P_{-3} = (-1)^{4} \cdot 5 = 5. The first 20 nonnegative Pell numbers, along with the first five negative ones for illustration, are listed below:

n	P_n
-5	29
-4	-12
-3	5
-2	-2
-1	1
0	0
1	1
2	2
3	5
4	12
5	29
6	70
7	169
8	408
9	985
10	2378
11	5741
12	13860
13	33461
14	80782
15	195025
16	470832
17	1136689
18	2744210
19	6625109

^[2] Observable patterns in the initial terms include a growth rate where each term is roughly 2.414 times the previous one, leading to exponential increase that approximately doubles the value every step or two.^[1] Regarding parity, the sequence alternates between even and odd starting from P_0 = 0 (even), with all even-indexed terms P_{2n} being even for n \geq 0.^[2] A simple identity for the sum of the first n Pell numbers (from k=0 to k=n, noting P_0 = 0) is \sum_{k=0}^{n} P_k = \frac{\alpha^{n+1} + \beta^{n+1} - 2}{4}, where \alpha = 1 + \sqrt{2} and \beta = 1 - \sqrt{2}. For instance, the sum up to n=5 is $0 + 1 + 2 + 5 + 12 + 29 = 49.^[7]

Analytic Properties

Recurrence Relation

The Pell numbers P_n are defined by the second-order linear homogeneous recurrence relation

P_n = 2P_{n-1} + P_{n-2}

for n \geq 2, with initial conditions P_0 = 0 and P_1 = 1. This relation derives from the structure of the continued fraction expansion of \sqrt{2}, which is [1; \overline{2}], an infinite periodic continued fraction with period length 1. The convergents to this expansion are p_n / q_n, where the denominators q_n correspond to the Pell numbers shifted by one index, specifically q_n = P_{n+1}. The general recurrence for denominators of convergents is q_n = a_n q_{n-1} + q_{n-2}, with initial values q_{-1} = 0 and q_0 = 1. Since the partial quotients satisfy a_0 = 1 and a_n = 2 for all n \geq 1, the relation simplifies to q_n = 2 q_{n-1} + q_{n-2} for n \geq 2, yielding the Pell recurrence upon reindexing.^[8]^[9] The validity of this recurrence for the Pell sequence can be proved by induction on the convergents. For the base cases, q_0 = 1 = P_1 and q_1 = 2 = P_2 hold directly from the continued fraction initialization. Assuming the relation holds for all denominators up to n-1, the inductive step follows from the convergent recurrence definition: q_n = 2 q_{n-1} + q_{n-2} = 2 P_n + P_{n-1}, but reindexing confirms P_{n+1} = 2 P_n + P_{n-1}, preserving the form. This induction leverages the property that consecutive convergents satisfy p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}, ensuring the recursive structure aligns with the periodic continued fraction.^[9]^[8] The recurrence is unique for the Pell sequence among second-order linear homogeneous relations with integer coefficients, as determined by its characteristic equation r^2 - 2r - 1 = 0. The roots are r = 1 + \sqrt{2} (approximately 2.414) and r = 1 - \sqrt{2} (approximately -0.414), which uniquely characterize the general solution P_n = A (1 + \sqrt{2})^n + B (1 - \sqrt{2})^n when fitted to the initial conditions. Any other second-order recurrence generating the same initial terms would share this characteristic equation, confirming the relation's specificity.^[8]^[9] Computationally, the recurrence enables efficient evaluation of P_n via forward iteration, requiring only O(n) additions and multiplications by 2, which is linear in the index and suitable for large n using arbitrary-precision arithmetic libraries to handle the exponential growth (since P_n \sim \frac{(1 + \sqrt{2})^{n}}{\sqrt{8}}). In floating-point arithmetic, the forward recurrence is numerically stable because the dominant root exceeds 1 in magnitude while the subordinate root has absolute value less than 1, preventing significant error amplification from rounding in subsequent steps; relative errors remain bounded by machine epsilon times a factor proportional to n, typically under $10^{-15} for double precision up to moderate n \approx 1000. Backward recurrence, however, would be unstable due to the smaller root's contribution dominating in reverse.^[8]

Closed-Form Expression

The Pell numbers satisfy the Binet-type closed-form expression

P_n = \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2 \sqrt{2}},

valid for all nonnegative integers n, with P_0 = 0 and P_1 = 1.^[2]^[1]^[10] This formula arises from solving the linear homogeneous recurrence P_n = 2P_{n-1} + P_{n-2} (for n \geq 2) via its characteristic equation r^2 - 2r - 1 = 0. The roots are \alpha = 1 + \sqrt{2} and \beta = 1 - \sqrt{2}, so the general solution is P_n = A \alpha^n + B \beta^n. Applying the initial conditions P_0 = 0 and P_1 = 1 yields A = 1/(2\sqrt{2}) and B = -1/(2\sqrt{2}), simplifying to the stated expression.^[10] Since |\beta| \approx 0.414 < 1, the term \beta^n/(2\sqrt{2}) decays exponentially and satisfies |\beta^n/(2\sqrt{2})| < 1/2 for n \geq 1. Thus, P_n is the nearest integer to \alpha^n/(2\sqrt{2}), with the error bound |P_n - \alpha^n/(2\sqrt{2})| < 1/2.^[2] The irrational components in the Binet formula nonetheless produce integers, as the expression satisfies the integer-valued recurrence and initial conditions. By mathematical induction, the base cases P_0 = 0 and P_1 = 1 are integers; assuming P_k and P_{k+1} are integers for some k \geq 1, then P_{k+2} = 2P_{k+1} + P_k is also an integer. Since the closed-form solution matches these values, it yields integers for all n.^[10]

Approximations and Continued Fractions

Relation to Square Root of Two

The continued fraction expansion of \sqrt{2} is [1; \overline{2}], meaning \sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cdots}}}. The convergents of this expansion are rational approximations p_n / q_n to \sqrt{2}, where the denominators q_n are the Pell numbers P_n (starting from P_1 = 1, P_2 = 2, etc.). For example, the first few convergents are $1/1, $3/2, $7/5, $17/12, and $41/29, with denominators 1, 2, 5, 12, and 29, respectively.^[2]^[11] These convergents provide the best rational approximations to \sqrt{2} in the sense that any rational with a smaller denominator cannot approximate \sqrt{2} as closely. The approximation error satisfies |\sqrt{2} - p_n / P_n| < 1 / (P_n P_{n+1}), which is tighter than the general bound of $1 / P_n^2 for continued fraction convergents. This property arises because the partial quotients are all 2, leading to rapid convergence compared to other irrationals.^[11]^[2] Asymptotically, the Pell numbers grow as P_n \sim \alpha^n / \sqrt{8}, where \alpha = 1 + \sqrt{2} is the dominant root of the characteristic equation from the recurrence. This reflects the exponential rate tied to the continued fraction's periodicity and the unit $1 + \sqrt{2} in the ring \mathbb{Z}[\sqrt{2}].^[2] Historically, these approximations to \sqrt{2} via Pell numbers were linked to ancient Indian mathematics, with Bhāskara II (12th century) advancing the chakravāla method for solving the associated Pell equation x^2 - 2y^2 = \pm 1, which generates the numerators and denominators of the convergents.^[3]

Pell's Equation Solutions

The Pell equation x^2 - 2y^2 = \pm 1 admits infinitely many positive integer solutions (x_n, y_n), where the y_n are the Pell numbers P_n (starting from n=1) and the x_n are the corresponding Pell-Lucas numbers Q_n. Specifically, these solutions satisfy Q_n^2 - 2 P_n^2 = (-1)^n, so the equation equals -1 for odd n and +1 for even n.^[12] The minimal solution to the negative case (x^2 - 2y^2 = -1) is (x_1, y_1) = (1, 1), while the minimal solution to the positive case (x^2 - 2y^2 = +1) is (x_2, y_2) = (3, 2). Subsequent solutions are generated recursively from any prior solution (x_k, y_k) via the relations

\begin{align*} x_{k+1} &= 3x_k + 4y_k, \\ y_{k+1} &= 2x_k + 3y_k. \end{align*}

This recursion arises from multiplying the corresponding units in the ring \mathbb{Z}[\sqrt{2}].^[13]^[12] All positive integer solutions to x^2 - 2y^2 = \pm 1 are obtained this way, as they correspond precisely to the coefficients of the powers of the fundamental unit $1 + \sqrt{2} (which has norm -1) in \mathbb{Z}[\sqrt{2}]; odd powers yield solutions to the equation with right-hand side -1, while even powers yield those with +1. The group of units of norm \pm 1 in this ring is infinite cyclic, generated by $1 + \sqrt{2}, ensuring the completeness of these solutions.^[13]

Pell-Lucas Numbers

The Pell-Lucas numbers, denoted Q_n, form a sequence that accompanies the Pell numbers P_n in the same manner as the Lucas numbers accompany the Fibonacci numbers. They are defined by the recurrence relation Q_n = 2 Q_{n-1} + Q_{n-2} for n \geq 2, with initial conditions Q_0 = 2 and Q_1 = 2.^[14]^[15] Equivalently, Q_n = P_{n-1} + P_{n+1} for n \geq 1, linking them directly to the Pell sequence.^[15] A closed-form expression for the Pell-Lucas numbers is given by the Binet-type formula

Q_n = (1 + \sqrt{2})^n + (1 - \sqrt{2})^n.

This expression arises from their position as the V_n terms in the Lucas sequence with parameters P = 2 and Q = -1.^[14]^[15] The Pell-Lucas numbers possess several notable properties. Each Q_n for n \geq 0 is an even integer, as observed from the sequence beginning 2, 2, 6, 14, 34, 82, ....^[14]^[15] They satisfy a divisibility condition where Q_n divides Q_{kn} for any positive integers n and k, a characteristic shared with companion sequences in linear recurrences.^[15] Additionally, Q_n = 2(P_n + P_{n-1}) for n \geq 1, providing a direct linear relation to the Pell numbers beyond the defining sum.^[15] The term "Pell-Lucas numbers" was introduced analogously to the Lucas numbers for the Fibonacci sequence, emphasizing their structural similarity, as noted in early studies of these recurrences.^[15] In the context of Pell's equation x^2 - 2 y^2 = (-1)^n, the solutions satisfy x_n = Q_n / 2 with y_n = P_n.^[14]

Companion Pell Sequences

Companion Pell sequences extend the standard Pell numbers and their Lucas companions to negative indices and related variants, preserving the underlying recurrence relation while introducing symmetric properties that allow the sequences to be defined bidirectionally over all integers. For the Pell numbers P_n, the extension to negative indices is given by P_{-n} = (-1)^{n+1} P_n for positive integers n, which ensures the recurrence P_n = 2P_{n-1} + P_{n-2} holds for all integers n.^[16]^[6] This formula reflects an alternating sign pattern: terms with odd positive indices remain positive when negated, while even-indexed terms change sign, creating a symmetric structure around zero. For example, P_{-1} = 1 = P_1, P_{-2} = -2 = -P_2, and P_{-3} = 5 = P_3.^[16] Similarly, for the Pell-Lucas numbers Q_n, the negative-index extension is Q_{-n} = (-1)^n Q_n, which also maintains the same recurrence Q_n = 2Q_{n-1} + Q_{n-2}.^[6] This yields a different symmetry: even-indexed terms retain their sign, while odd-indexed terms negate, as seen in Q_{-1} = -2 = -Q_1, Q_{-2} = 6 = Q_2, and Q_{-3} = -14 = -Q_3. These extensions transform the sequences into infinite bidirectional arrays, facilitating applications in identities that span positive and negative directions without breaking the linear recurrence structure.^[16] Another related companion sequence arises in the context of continued fraction approximations to \sqrt{2}, where the numerators of the convergents form the sequence $1, 1, 3, 7, 17, 41, \dots, which corresponds to Q_n / 2 for n \geq 0.^[16] This half-companion variant shares the same recurrence and exhibits similar symmetry properties when extended to negative indices, underscoring the interconnectedness of Pell-related sequences in approximating quadratic irrationals. These companions preserve key algebraic properties, such as generating functions and matrix representations, while enabling broader number-theoretic explorations.

Number-Theoretic Applications

Primes and Perfect Squares

Pell primes are those terms in the Pell sequence that are prime numbers. The sequence begins with small primes: the second Pell number P_2 = 2, the third P_3 = 5, and the fifth P_5 = 29. Larger known Pell primes include P_{11} = 5741 and P_{13} = 33461, with subsequent terms such as P_{17} = 44560482149 also verified as prime.^[17] These examples illustrate that Pell primes occur at prime indices, though not all prime indices yield primes, as seen with P_7 = 169 = 13^2, which is composite. Only finitely many Pell primes have been identified to date, and it remains an open question whether infinitely many exist.^[17] Most Pell numbers are composite, with factorizations revealing patterns of small prime factors for early terms. For instance, P_4 = 12 = 2^2 \times 3, P_6 = 70 = 2 \times 5 \times 7, P_8 = 408 = 2^3 \times 3 \times 17, and P_9 = 985 = 5 \times 197. These decompositions highlight the tendency of Pell numbers to factor non-trivially beyond the primes, often involving powers of 2 or products of distinct primes.^[2] Regarding perfect squares, the Pell sequence contains only three such terms: P_0 = 0 = 0^2, P_1 = 1 = 1^2, and P_7 = 169 = 13^2. No other Pell number P_n for n > 1 is a perfect square, a result established through analysis of Thue equations derived from the closed-form expression of Pell numbers and verified computationally for small indices.^[18] This scarcity underscores the rigid growth properties of the sequence, which prevent additional squareness except in these trivial cases.

Pythagorean Triples

Pell numbers generate an infinite family of primitive Pythagorean triples through the standard parametrization, where the parameters m and n are consecutive terms in the Pell sequence. Specifically, set m = P_{n+1} and n = P_n for n \geq 1, yielding the primitive triple

(a, b, c) = (P_{n+1}^2 - P_n^2, \, 2 P_{n+1} P_n, \, P_{n+1}^2 + P_n^2),

where P_k denotes the k-th Pell number. This construction satisfies the conditions for primitivity: \gcd(P_{n+1}, P_n) = 1, P_{n+1} and P_n have opposite parity (alternating odd and even starting from P_1 = 1 odd), and P_{n+1} - P_n is odd.^[19] The hypotenuse simplifies via the Pell identity P_{n+1}^2 + P_n^2 = P_{2n+1}, so c = P_{2n+1}, an odd-indexed Pell number. For example, with n=2, P_2 = 2 and P_3 = 5 give the triple (20, 21, 29), where $29 = P_5. Similarly, n=1 yields (3, 4, 5) with c = P_3 = 5, and n=3 gives (119, 120, 169) with c = P_7 = 169. These triples feature legs differing by 1, corresponding to solutions of the negative Pell equation x^2 - 2y^2 = -1.^[19]^[20] This family enumerates all primitive Pythagorean triples with consecutive integer legs, as the parameters arise uniquely from the solutions to the relevant Pell equation. Companion Pell numbers (Pell-Lucas numbers Q_k) generate another family of primitive triples, where certain hypotenuses are Q_{2n}/2 for even indices yielding integers congruent to 1 modulo 4 without square factors, such as Q_4/2 = 17 for the triple (8, 15, 17). Primitivity holds under analogous conditions: coprime parameters of opposite parity with odd difference.^[19]

Combinatorial Identities

Square Triangular Numbers

Square triangular numbers are positive integers that are both perfect squares and triangular numbers, satisfying the equation \frac{m(m+1)}{2} = k^2 for positive integers m and k. This Diophantine equation can be transformed into the Pell equation x^2 - 2y^2 = 1 by setting x = 2m + 1 and y = 2k, or more directly through the substitution leading to (2m + 1)^2 - 8k^2 = 1, whose solutions relate to the fundamental Pell equation for d=2. The positive integer solutions to x^2 - 2y^2 = 1 generate the pairs (m_n, k_n) with indices effectively doubling due to the powers of the fundamental unit $1 + \sqrt{2}.^[21] The nth square triangular number T_n = k_n^2 is explicitly given by T_n = \left( \frac{P_{2n}}{2} \right)^2, where P_j denotes the jth Pell number (with P_1 = 1, P_2 = 2), as the y-components of the Pell solutions are y_n = P_{2n}. This connection arises because the Binet-like formulas for Pell numbers yield the exact solutions: P_{2n} = \frac{(1 + \sqrt{2})^{2n} - (1 - \sqrt{2})^{2n}}{2\sqrt{2}}.^[21] The first few square triangular numbers illustrate this relation: T_1 = 1 = \left( \frac{P_2}{2} \right)^2 = \left( \frac{2}{2} \right)^2, T_2 = 36 = \left( \frac{P_4}{2} \right)^2 = \left( \frac{12}{2} \right)^2, and T_3 = 1225 = \left( \frac{P_6}{2} \right)^2 = \left( \frac{70}{2} \right)^2. These correspond to triangular indices m_1 = 1, m_2 = 8, m_3 = 49, generated recursively via the Pell recurrence.^[21] Asymptotically, T_n \sim \frac{ ((1 + \sqrt{2})^{2n})^2 }{32} = \frac{ (1 + \sqrt{2})^{4n} }{32}, reflecting the dominant term in the Binet formula for P_{2n} \approx \frac{(1 + \sqrt{2})^{2n}}{\sqrt{8}}, which establishes the exponential growth tied to the silver ratio $1 + \sqrt{2}. This ensures infinitely many such numbers, as proven by the infinitude of Pell equation solutions.^[21]

Cassini's Identity Analogs

One of the fundamental identities analogous to Cassini's identity for the Fibonacci sequence is the relation P_{n+1} P_{n-1} - P_n^2 = (-1)^n, which holds for all integers n \geq 1. This identity can be verified directly for small values of n and proven generally using the Binet formula for Pell numbers, P_n = \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2 \sqrt{2}}, by expanding the left side and simplifying the difference of powers. Alternatively, it arises as the determinant of the matrix associated with the Pell recurrence, though the details of that approach lie in matrix formulations.^[10] Pell numbers satisfy an addition formula P_{m+n} = P_{m+1} P_n + P_m P_{n-1} for nonnegative integers m and n, which facilitates the computation of terms at arbitrary indices and underscores the sequence's algebraic structure. This identity also admits a proof via the Binet formula, where the product expansions yield the desired combination after applying properties of the roots $1 + \sqrt{2} and $1 - \sqrt{2}. A related summation identity provides a closed form for the partial sums: \sum_{k=1}^n P_k = \frac{P_{n+2} + P_n - 2}{4}, expressible equivalently as \frac{Q_{n+1} - 2}{4} using the companion Pell-Lucas numbers Q_n. This sum formula is derived using the Binet expression by summing the geometric series for each root separately and simplifying.^[10] An identity of d'Ocagne type, involving products of Pell and Pell-Lucas numbers, states that P_{n+m} + (-1)^m P_{n-m} = P_n Q_m for integers n \geq m \geq 0. This relation highlights interconnections between the two sequences and can be established via the Binet formulas for both P_k and Q_k = (1 + \sqrt{2})^k + (1 - \sqrt{2})^k, leading to cancellation of cross terms. Such identities serve as tools in applications like identifying square triangular numbers, where specific cases align Pell terms with geometric constraints.^[1]

Computational Methods

Matrix Formulations

The companion matrix for the Pell numbers, derived from their defining recurrence P_n = 2P_{n-1} + P_{n-2}, is the $2 \times 2 matrix

M = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}.

Raising this matrix to the nth power yields

M^n = \begin{pmatrix} P_{n+1} & P_n \\ P_n & P_{n-1} \end{pmatrix},

providing a direct matrix-based generation of consecutive Pell numbers.^[22] The determinant of M is -1, so \det(M^n) = (-1)^n, which implies the fundamental identity P_{n+1} P_{n-1} - P_n^2 = (-1)^n.^[22] This matrix formulation extends naturally to the Pell-Lucas numbers Q_n, which obey the identical recurrence Q_n = 2Q_{n-1} + Q_{n-2} with initial conditions Q_0 = 2 and Q_1 = 2; thus, M^n initialized with the appropriate vector for Q_1 and Q_0 generates blocks of consecutive Q_n terms. For simultaneous computation of both sequences, extended representations such as $3 \times 3 matrices have been developed, where the entries of the nth power incorporate linear combinations of P_k and Q_k for relevant indices k.^[23]^[24] Matrix exponentiation of M enables the fast computation of Pell numbers for large n in O(\log n) time via repeated squaring, avoiding the exponential cost of iterative recurrence evaluation.^[23] The eigenvalues of M are $1 + \sqrt{2} and $1 - \sqrt{2}, linking the formulation to powers in the quadratic field \mathbb{Q}(\sqrt{2}); specifically, matrix exponentiation facilitates efficient calculation of (1 + \sqrt{2})^n = \frac{Q_n}{2} + P_n \sqrt{2}, representing the power in the basis \{1, \sqrt{2}\} of the ring \mathbb{Z}[\sqrt{2}].^[15]

Generating Functions

The ordinary generating function for the Pell numbers P_n, defined by P_0 = 0, P_1 = 1, and P_n = 2P_{n-1} + P_{n-2} for n \geq 2, is given by

G(x) = \sum_{n=0}^\infty P_n x^n = \frac{x}{1 - 2x - x^2}.

This formula arises directly from the recurrence relation. Let G(x) = \sum_{n=0}^\infty P_n x^n. Multiplying the recurrence by x^n and summing from n=2 to infinity yields

\sum_{n=2}^\infty P_n x^n = 2x \sum_{n=2}^\infty P_{n-1} x^{n-1} + x^2 \sum_{n=2}^\infty P_{n-2} x^{n-2}.

Adjusting indices, the right-hand side simplifies to $2x (G(x) - P_0) + x^2 G(x). Substituting the initial conditions and rearranging terms gives G(x) (1 - 2x - x^2) = x, solving for the closed form above. The generating function facilitates coefficient extraction through partial fraction decomposition, linking to the closed-form Binet expression for P_n. The denominator $1 - 2x - x^2 = 0 has roots r = 1 + \sqrt{2} and s = 1 - \sqrt{2}, so

G(x) = \frac{A}{1 - r x} + \frac{B}{1 - s x},

where A = \frac{1}{2\sqrt{2}} and B = -\frac{1}{2\sqrt{2}}. Expanding as geometric series, the coefficient of x^n is A r^n + B s^n = \frac{r^n - s^n}{2\sqrt{2}}, which is the Binet formula for P_n. This approach proves various identities by manipulating the series, such as summation formulas derived from the rational form. Singularity analysis of G(x) provides asymptotic behavior for P_n. The radius of convergence is determined by the dominant singularity at x = 1/r \approx 0.414, the reciprocal of the larger root r = 1 + \sqrt{2}. Near this pole, G(x) \sim \frac{c}{1 - r x} for some constant c, leading to the leading-term asymptotic P_n \sim \frac{r^n}{2\sqrt{2}} as n \to \infty, with relative error O(|s/r|^n). This growth rate underscores the exponential nature of Pell numbers, consistent with their role in approximating \sqrt{2}.