Skip to content
Symi Docs
Rust

The Rust manual covers the recommended facade. The complete native crate is documented in the native Rust API reference.

On this page

Recurrence equations

A recurrence equation relates an unknown sequence to its own shifted values. It is the discrete analogue of an ordinary differential equation, and it is written the same way: the unknown sequence is an undefined function evaluated at an index, and a shift is that function evaluated at n + k.

Solving#

solve_linear_recurrence#

api::solving::Session method

pub fn solve_linear_recurrence<'a, VariableType>(
    &self,
    equation: &Expression,
    sequence_call: &Expression,
    index_variable: VariableType,
    initial_conditions: Option<&[(Expression, Expression)]>,
) -> Result<Expression, ApiError>
where
    VariableType: Into<VariableLike<'a>>,

Solve a linear recurrence for the unknown sequence named by sequence_call (e.g. a(n)). Backward shifts are normalised by translating the whole equation. Homogeneous recurrences with polynomial coefficients use Petkovšek's Hyper algorithm; the general solution carries one fresh symbolic constant per basis element. Constant-coefficient recurrences may be inhomogeneous when the forcing is a sum of polynomial-times-exponential terms, with resonant trials raised by the root multiplicity; recurrences whose coefficients are rational in n and c^n are solved in that mixed field when a rational solution exists. Other shapes return the unevaluated recurrence_equation placeholder. initial_conditions is a list of (index, value) pairs. WASM passes a flat interleaved array.

Constant coefficients. When every coefficient is a rational constant and Petkovšek's basis is incomplete, the characteristic polynomial is factored over Q\mathbb{Q} and each irreducible factor solved in radicals, giving the algebraic-exponential basis njroot⁡nn^j \operatorname{root}^n with the multiplicity factors included. This is what closes recurrences whose characteristic roots are irrational — a(n+2) = a(n+1) + a(n) with a(0) = 0, a(1) = 1 returns Binet's formula rather than the placeholder. Exact fitting is performed for irreducible factors up to degree two; a cubic or higher irreducible factor declines to the placeholder rather than eliminating over nested Cardano and Ferrari radicals.

Initial conditions. A complete window determines every constant, not just the first: the window gives a square linear system in the constants which is solved by exact symbolic elimination, and the fitted result is replayed against each supplied condition before it is returned. A window that does not determine the constants leaves the symbolic-constant general solution intact.

  • Ordinary differential equations — the continuous analogue, whose constant-coefficient route uses the same characteristic-polynomial reasoning.
  • Undefined functions — how the unknown sequence is named and called.
  • Polynomials — the factorization of the characteristic polynomial that produces the algebraic-exponential basis.