Bounded solution of a second-order constant-coefficient recurrence Created 2026-10-06 Updated 2026-10-14
For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots , the solution is . If , boundedness for forces , and fixes . This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor .
Exponential forcing in a linear recurrence Created 2026-10-14 Updated 2026-11-05
Let be the forward shift on sequences and the polynomial defining a constant-coefficient linear recurrence relation. For a nonzero base , , so is a particular solution when . At a simple root of the characteristic equation of a linear recurrence, the correct trial acquires a factor :
The identity follows by substituting into each shift term. A root of multiplicity analogously requires a degree- polynomial factor; the lower-degree homogeneous terms are supplied by the repeated characteristic root of a linear recurrence.
For the homogeneous linear recurrence relation, substitute . Its characteristic equation of a linear recurrence is , with roots and . Taking real linear combinations gives
These two real sequences are linearly independent: their values at form a matrix with determinant . Thus their two constants account uniquely for arbitrary first two values.
Let and reindex as . In , each term with has coefficient
The term is , and the remaining term is . This explicitly proves that is the required particular solution, a discrete Green convolution for the period-six recurrence.
The unit-response coefficients have the homogeneous form just found. The values give zero cosine coefficient and sine coefficient , so
Subtracting this particular solution from any other solution leaves a homogeneous recurrence. Thus the complete answer is
With , the central finite difference converts the decay equation to
The continuous ordinary differential equation has the general solution . The discrete linear recurrence is second order and requires two initial values, such as . Trying gives the characteristic equation of a linear recurrence . Its roots are
so
There are no repeated roots, and the same formula extends to negative integer if required.
To demonstrate the continuum limit, put . Then and , with . For ,
uniformly, since . More precisely , giving an error on a fixed interval. Thus , selects the physical discrete mode and corresponds to .
The other root is a parasitic amplification root:
For fixed , even and odd mesh points approach values differing by . Equivalently successive mesh values have a nonvanishing alternating jump despite their time separation tending to zero. This mode cannot converge uniformly to a continuous ODE solution; its limiting envelope also grows rather than decays.
For step-dependent initial data the precise result is the centered two-step discretization of exponential decay criterion:
Sufficiency follows from the two uniformly bounded exponential envelopes on a fixed interval. Necessity follows from convergence at the adjacent points : , , and the coefficient formulas force , . In particular a nonzero but vanishing starting error is not excluded. Starting with the exact value gives and still converges on each fixed interval. The assertion about “remaining” solutions therefore concerns a fixed nonzero parasitic amplitude, not every nonzero step-dependent amplitude. The method is nevertheless not damping-stable for arbitrarily long times because .
Substitute the linear recurrence relation for each of and in the discrete Wronskian:
Iterating gives
No division was used, so vanishing cause no exception.
For constant coefficients, seek a solution . The characteristic equation of a linear recurrence is . Choose with . Its roots are and , since . For the two resulting solutions,
It is independent of , exactly as the product identity predicts when .
When the roots are distinct and the discrete Wronskian is nonzero. At or , the two displayed solutions coincide and ; the identity still holds. If an independent pair is wanted at these endpoints, take and , where or respectively. Direct substitution verifies both, and their discrete Wronskian is .
The characteristic equation of a linear recurrence is
For , these characteristic roots are distinct. Two real solutions of the second-order difference equation are and . Their values at form a matrix with determinant , proving linear independence. Consequently they span the two-dimensional vector space of recurrence solutions.
At the two roots coalesce at one. The linear recurrence becomes , so its successive differences are constant. A basis is therefore , and every solution is .
For the specified initial conditions, the zero-angle solution is . For nonzero angle, it is convenient to center the basis at :
This gives and , and each summand obeys the linear recurrence. For every fixed integer , the elementary limit gives
The convergence here is for fixed ; it does not assert uniform convergence over all indices.
For the homogeneous linear recurrence relation, a trial gives the characteristic equation of a linear recurrence . Thus the two homogeneous sequences are and . Seek a particular solution ; substitution gives , so and . Hence
The two independent constants supply arbitrary initial values for this second-order linear recurrence relation.
The forcing base is a root of the characteristic equation of a linear recurrence, so a constant multiple of cannot be a particular solution. For , direct substitution gives
For the resonant case of exponential forcing in a linear recurrence, at , and . Hence is a particular solution of the inhomogeneous linear recurrence. The general solution is
Substitution of gives the characteristic equation of a linear recurrence
The repeated characteristic root of a linear recurrence supplies the solutions and , while the simple root supplies . They are linearly independent: their values at three consecutive indices have nonzero determinant. A third-order linear recurrence relation is uniquely determined by three consecutive initial values, so these three solutions span its solution space. The general solution is
Collecting the shifted terms gives a second-order difference equation with coefficients , and . Substitute to obtain its characteristic equation of a linear recurrence:
For real , the roots and general solution are
In the small-step regime, indeed for , the polynomial is positive at , negative at and positive for sufficiently large positive . Thus . The bounded solution of a second-order constant-coefficient recurrence discards the growing root, and fixes its remaining coefficient:
The Taylor series establishes the displayed approximation to the root. Raising that approximation to the th power is a leading approximation, rather than a uniform relative approximation for arbitrarily large : its relative error is controlled when is small. For completeness, the degenerate values give when , and when .
Let be the probability that the simple random walk started at hits before zero. The first-step analysis recurrence and boundary conditions are
If , the characteristic equation of a linear recurrence has roots and , so the boundary conditions give
If , the repeated root gives the limiting formula . This is the gambler's ruin probability.
For a fixed integer stake , the fact that divides lets us measure Patricia's wealth in units of £. She starts at and succeeds upon reaching . The formula above factors as
For , , so this probability increases as decreases. She should therefore choose the largest stake, . For , , so the probability increases as increases; she should choose the smallest stake, .
The characteristic equation of a linear recurrence is
Its repeated root gives
Since , this can be written , exactly the discrete form of the continuous solution of .
The characteristic equation of a linear recurrence is
Its distinct roots are and , so . The initial conditions are and , giving and . Hence , , and
The homogeneous characteristic equation of a linear recurrence is
The repeated characteristic root of a linear recurrence supplies the independent terms and . A constant particular solution is , since . Thus .
The scan prints , not . These initial conditions are consistent. They give from , then , so . Therefore
In particular and . Direct substitution verifies the recurrence relation. This is an example of nonconsecutive initial values for a linear recurrence; replacing the printed subscript by 1 would change the answer.
For the homogeneous linear recurrence relation, try . Its characteristic equation of a linear recurrence is
The distinct roots of a polynomial give the complementary terms . A constant cannot absorb the forcing because is already a root of a polynomial of the characteristic equation; try a particular solution . Substitution gives , hence . The general solution is .
The initial conditions give and . Hence , , and
For a nonzero geometric sequence, substitute into the linear recurrence and cancel :
The characteristic equation of a linear recurrence therefore has roots
The zero sequence is a degenerate solution for any for which the displayed expression is defined. A nonzero sequence with cannot satisfy the recurrence at , since it would require .