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.
Past exam of the mathematics course of the University of Cambridge 2001 ia Paper 2 5B Solution Created 2026-09-24 Updated 2026-10-14
For the homogeneous linear recurrence relation, substitute . Its characteristic equation of a linear recurrence is , with roots and . Taking real linear combinations givesThese 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 coefficientThe 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 , soSubtracting this particular solution from any other solution leaves a homogeneous recurrence. Thus the complete answer is
Past exam of the mathematics course of the University of Cambridge 2003 ia Paper 2 2D Solution Created 2026-09-24 Updated 2026-10-14
With , the central finite difference converts the decay equation toThe 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 aresoThere 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 .
Past exam of the mathematics course of the University of Cambridge 2004 ia Paper 2 6B Solution Created 2026-09-24 Updated 2026-10-14
Substitute the linear recurrence relation for each of and in the discrete Wronskian:Iterating givesNo 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 .
Past exam of the mathematics course of the University of Cambridge 2005 ia Paper 2 5B Solution Created 2026-09-24 Updated 2026-10-14
The characteristic equation of a linear recurrence isFor , 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 givesThe convergence here is for fixed ; it does not assert uniform convergence over all indices.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 2 8B i Solution Created 2026-09-24 Updated 2026-10-14
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 . HenceThe two independent constants supply arbitrary initial values for this second-order linear recurrence relation.
Past exam of the mathematics course of the University of Cambridge 2010 ia Paper 2 1A iii Solution Created 2026-09-24 Updated 2026-10-14
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 givesFor 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
Past exam of the mathematics course of the University of Cambridge 2010 ia Paper 2 1A i Solution Created 2026-09-24 Updated 2026-10-14
Substitution of gives the characteristic equation of a linear recurrenceThe 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
Past exam of the mathematics course of the University of Cambridge 2016 ia Paper 2 1A b Solution Created 2026-09-24 Updated 2026-10-06
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 areIn 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 .
Past exam of the mathematics course of the University of Cambridge 2019 ia Paper 2 10F Solution Created 2026-09-24 Updated 2026-09-29
Let be the probability that the simple random walk started at hits before zero. The first-step analysis recurrence and boundary conditions areIf , the characteristic equation of a linear recurrence has roots and , so the boundary conditions giveIf , 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 asFor , , 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, .
Past exam of the mathematics course of the University of Cambridge 2019 ia Paper 2 5C b Solution Created 2026-09-24 Updated 2026-09-29
The characteristic equation of a linear recurrence isIts repeated root givesSince , this can be written , exactly the discrete form of the continuous solution of .
The characteristic equation of a linear recurrence isIts distinct roots are and , so . The initial conditions are and , giving and . Hence , , and
The homogeneous characteristic equation of a linear recurrence isThe 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 . ThereforeIn 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 isThe 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 .
For a nonzero geometric sequence, substitute into the linear recurrence and cancel :The characteristic equation of a linear recurrence therefore has rootsThe 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 .