Recurrence Relations and Generating Functions

Vocabulary flashcards covering sequences, generating functions, formal power series properties, binomial expansions, and recurrence relation solving techniques (substitution, characteristic roots, undetermined coefficients, and generating functions).

Sequence

An ordered set of real numbers denoted by $\langle a_n \rangle$ or $\{a_n\} = \{a_0, a_1, a_2, \dots\}$, or in general, a function from the set of non-negative integers to real numbers ($f: \mathbb{Z} \rightarrow \mathbb{R}$).

Generating Function (Formal Power Series)

A formal series associated with a sequence $a_0, a_1, a_2, \dots$ denoted by $A(x)$ and defined as $A(x) = \sum_{r=0}^{\infty} a_r x^r = a_0 x^0 + a_1 x^1 + a_2 x^2 + \dots + a_n x^n + \dots$, where $a_r$ is the coefficient of $x^r$.

Addition Property of Generating Functions

If $A(x) = \sum_{r=0}^{\infty} a_r x^r$ and $B(x) = \sum_{r=0}^{\infty} b_r x^r$, then their sum is given by $A(x) + B(x) = \sum_{n=0}^{\infty} (a_n + b_n) x^n$.

Multiplication Property of Generating Functions

The Cauchy product $A(x) \cdot B(x) = \sum_{r=0}^{\infty} c_r x^r$, where the coefficient of $x^r$ is given by $c_r = \sum_{k=0}^r a_k b_{r-k} = a_0 b_r + a_1 b_{r-1} + a_2 b_{r-2} + \dots + a_r b_0$.

Generating Function Model for Integer Solutions

A method where the number of non-negative integral solutions to an equation $e_1 + e_2 + \dots + e_k = r$ subject to constraints on $e_i$ is represented by the coefficient of $x^r$ in the product of polynomials or series whose exponents represent the allowed values for each $e_i$.

Binomial Generating Series for $(1-x)^{-n}$

The power series expansion $\frac{1}{(1-x)^n} = (1-x)^{-n} = \sum_{r=0}^{\infty} \binom{n-1+r}{r} x^r$.

Binomial Generating Series for $(1+x)^{-n}$

The power series expansion $\frac{1}{(1+x)^n} = (1+x)^{-n} = \sum_{r=0}^{\infty} \binom{n-1+r}{r} (-1)^r x^r$.

Geometric Generating Series for $(1-ax)^{-1}$

The power series expansion $\frac{1}{1-ax} = (1-ax)^{-1} = \sum_{r=0}^{\infty} a^r x^r = 1 + ax + a^2 x^2 + a^3 x^3 + \dots$.

Recurrence Relation

An equation that expresses the $n^{\text{th}}$ term of a sequence, $a_n$, in terms of one or more of its preceding terms $a_0, a_1, \dots, a_{n-1}$.

Solution of a Recurrence Relation

A sequence $A = \{a_n\}$ whose terms make the recurrence relation a true mathematical statement for every non-negative integer $n$.

Linear Recurrence Relation

A relation of the form $C_0 a_n + C_1 a_{n-1} + C_2 a_{n-2} + \dots + C_k a_{n-k} = f(n)$, where $n$ and $k$ are non-negative integers.

Linear Recurrence Relation with Constant Coefficients

A linear recurrence relation in which the coefficients $C_0, C_1, C_2, \dots, C_k$ are constant values rather than functions of $n$.

Homogeneous Linear Recurrence Relation

A linear recurrence relation in which $f(n) = 0$, taking the form $C_0 a_n + C_1 a_{n-1} + C_2 a_{n-2} + \dots + C_k a_{n-k} = 0$.

Non-Homogeneous Linear Recurrence Relation

A linear recurrence relation in which the non-homogeneous term $f(n) \neq 0$.

Degree (Order) of a Linear Recurrence Relation

The non-negative integer $k$ representing the difference between the highest and lowest subscripts of the sequence terms in the relation, provided $C_0 \neq 0$ and $C_k \neq 0$.

Substitution Method

A technique for solving a recurrence relation by recursively computing successive terms (or performing backward substitution) from the initial conditions until a general summation or closed-form formula in terms of $n$ emerges.

Auxiliary Equation (Characteristic Equation)

The algebraic equation $C_0 m^k + C_1 m^{k-1} + C_2 m^{k-2} + \dots + C_k = 0$ associated with a homogeneous linear recurrence relation with constant coefficients, whose roots determine the complementary function.

Complementary Function (Real and Distinct Roots)

The general solution to a homogeneous recurrence relation when the characteristic roots $m_1, m_2, \dots, m_k$ are real and distinct: $a_n = C_1 (m_1)^n + C_2 (m_2)^n + \dots + C_k (m_k)^n$.

Complementary Function (Repeated Real Roots)

The solution component for repeated characteristic roots; for example, if $m_1 = m_2 = m_3$, the corresponding terms are $(C_1 + C_2 n + C_3 n^2)(m_1)^n$.

Complementary Function (Complex Conjugate Roots)

The solution when characteristic roots are complex conjugates $m = \alpha \pm i\beta$, given by $a_n = r^n [C_1 \cos(n\theta) + C_2 \sin(n\theta)]$, where $r = \sqrt{\alpha^2 + \beta^2}$ and $\theta = \tan^{-1}\left(\frac{\beta}{\alpha}\right)$.

Method of Undetermined Coefficients

A technique used to find the particular integral ($\text{P.I.}$) of a non-homogeneous recurrence relation by assuming a trial solution based on the form of $f(n)$ with unknown constants and solving for those constants by substitution.

Complete Solution of a Linear Recurrence Relation

The sum of the complementary function and the particular integral: $a_n = \text{C.F.} + \text{P.I.}$.

Modification Rule for Particular Solutions

The rule stating that if any term of the trial particular solution appears in the complementary function, the trial solution must be multiplied by the lowest power of $n$ (e.g., $n$ or $n^2$) such that no duplication remains.

Generating Function Method for Recurrence Relations

A method where the recurrence relation is multiplied by $x^n$, summed over $n$, rewritten in terms of the generating function $A(x)$, solved algebraically for $A(x)$, and decomposed via partial fractions to find the closed-form sequence formula.

Generating Function Index Shift Property

The property used to represent lagged sequence terms, such as $\sum_{n=k}^{\infty} a_{n-k} x^n = x^k A(x)$ when summed from appropriate indices, allowing algebraic conversion of recurrence relations into polynomial equations in $A(x)$.