solveRecurrence

Solve recurrence relations

Since R2026a

Syntax

sol = solveRecurrence(eqn,f)

sol = solveRecurrence(eqn,f,cond)

Description

sol = solveRecurrence(eqn,f) solves the symbolic recurrence relations in eqn for the functions f.

sol = solveRecurrence(eqn,f,cond) solves the recurrence relations with the initial conditions cond.

Examples

Gamma Function

Find the solution of the recurrence relation $f\left(n\right)=nf\left(n-1\right)$ for the gamma function.

Create a symbolic function f(n) and a symbolic equation eqn to represent the recurrence relation.

syms f(n)
eqn = f(n) == n*f(n-1);

Find the solution. The result is the gamma function with a constant multiplier.

sol = solveRecurrence(eqn,f)

sol = $$C_1\hspace{0.17em}\Gamma \text{<a href="matlab:doc symbolic/gamma">gamma</a>}\left(n+1\right)$$

Fibonacci and Lucas Numbers

Create a symbolic function f(n) and a symbolic equation eqn to represent the recurrence relation for the Fibonacci and Lucas sequences.

syms f(n)
eqn = f(n) == f(n-1) + f(n-2)

eqn = $$f\left(n\right)=f\left(n-1\right)+f\left(n-2\right)$$

Specify the initial conditions for the Fibonacci sequence.

cond = [f(0) == 0, f(1) == 1]

cond = $$\left(\begin{array}{cc}f\left(0\right)=0& f\left(1\right)=1\end{array}\right)$$

Solve the recurrence relation using these initial conditions.

sol = solveRecurrence(eqn,f,cond)

sol = 
$$\frac{\sqrt{5}\hspace{0.17em}{\left(\frac{\sqrt{5}}{2}+\frac{1}{2}\right)}^n}{5}-\frac{\sqrt{5}\hspace{0.17em}{\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)}^n}{5}$$

Find the 10th Fibonacci number.

sol10 = simplify(subs(sol,n,10))

sol10 = $$55$$

Next, specify the initial conditions for the Lucas sequence.

cond = [f(0) == 2, f(1) == 1]

cond = $$\left(\begin{array}{cc}f\left(0\right)=2& f\left(1\right)=1\end{array}\right)$$

Solve the recurrence relation using these initial conditions.

sol = solveRecurrence(eqn,f,cond)

sol = 
$${\left(\frac{1}{2}-\frac{\sqrt{5}}{2}\right)}^n+{\left(\frac{\sqrt{5}}{2}+\frac{1}{2}\right)}^n$$

Find the 10th Lucas number.

sol10 = simplify(subs(sol,n,10))

sol10 = $$123$$

System of Linear Recurrence Relations

Create a system of linear recurrence relations.

syms a(n) b(n)
eqn = [a(n+1) == a(n) + 2*b(n); ...
       b(n+1) == 3*a(n) + b(n)]

eqn = 
$$\left(\begin{array}{c}a\left(n+1\right)=a\left(n\right)+2\hspace{0.17em}b\left(n\right)\\ b\left(n+1\right)=3\hspace{0.17em}a\left(n\right)+b\left(n\right)\end{array}\right)$$

Specify the initial conditions for the functions a(0) and b(0).

cond = [a(0) == 2; b(0) == 3]

cond = 
$$\left(\begin{array}{c}a\left(0\right)=2\\ b\left(0\right)=3\end{array}\right)$$

Solve the system of recurrence relations using these initial conditions.

sol = solveRecurrence(eqn,[a b],cond)

sol = 
$$\begin{array}{l}\left(\begin{array}{c}{\sigma }_2+{\sigma }_4-{\sigma }_1+{\sigma }_3\\ {\sigma }_2+\frac{3\hspace{0.17em}{\sigma }_4}{2}-{\sigma }_1+\frac{3\hspace{0.17em}{\sigma }_3}{2}\end{array}\right)\\ \\ \mathrm{where}\\ \\ \mathrm{ }{\sigma }_1=\frac{\sqrt{6}\hspace{0.17em}{\sigma }_3}{2}\\ \\ \mathrm{ }{\sigma }_2=\frac{\sqrt{6}\hspace{0.17em}{\sigma }_4}{2}\\ \\ \mathrm{ }{\sigma }_3={\left(1-\sqrt{6}\right)}^n\\ \\ \mathrm{ }{\sigma }_4={\left(\sqrt{6}+1\right)}^n\end{array}$$

Check if the solutions for a(n) and b(n) satisfy the recurrence relations. Substitute [a; b] with sol, and use isAlways to determine if both sides of the recurrence relations are equal.

tf = isAlways(subs(eqn,[a; b],sol))

tf = 2×1 logical array

   1
   1

Check if the solutions also satisfy the initial conditions.

tf = isAlways(subs(cond,[a; b],sol))

tf = 2×1 logical array

   1
   1

Substitution to Solve Noncomputable Recurrence Relation

Create a recurrence relation for the Bessel functions.

syms J(n) z
eqn = J(n+1) == 2*n/z*J(n) - J(n-1)

eqn = 
$$J\left(n+1\right)=\frac{2\hspace{0.17em}n\hspace{0.17em}J\left(n\right)}{z}-J\left(n-1\right)$$

Specify the initial conditions using the Bessel function of the first kind.

cond = [J(0) == besselj(0,z); J(1) == besselj(1,z)]

cond = 
$$\left(\begin{array}{c}J\left(0\right)={\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_0\left(z\right)\\ J\left(1\right)={\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_1\left(z\right)\end{array}\right)$$

solveRecurrence cannot always solve recurrence relations with variable coefficients. In this case, the function returns an unevaluated call.

sol = solveRecurrence(eqn,J,cond)

sol = 
$$\mathrm{solveRecurrence}\left(J\left(n+1\right)=\frac{2\hspace{0.17em}n\hspace{0.17em}J\left(n\right)}{z}-J\left(n-1\right),J\left(n\right),\left[J\left(0\right)={\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_0\left(z\right),J\left(1\right)={\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_1\left(z\right)\right]\right)$$

However, if you substitute a specific value for the indexing parameter into the solution, the solver might be able to return an analytic solution. For example, substitute $n=4$. The analytic solution is in terms of the variable $z$ and the initial conditions $J_0\left(z\right)$ and $J_1\left(z\right)$.

soln4 = subs(sol,n,4)

soln4 = 
$$-\frac{8\hspace{0.17em}{z}^2\hspace{0.17em}{\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_1\left(z\right)-z^3\hspace{0.17em}{\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_0\left(z\right)+24\hspace{0.17em}z\hspace{0.17em}{\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_0\left(z\right)-48\hspace{0.17em}{\mathrm{J}\text{<a href="matlab:doc symbolic/besselj">besselj</a>}}_1\left(z\right)}{z^3}$$

Check if this solution is equal to the Bessel function of the first kind of order 4.

tf = isAlways(soln4 == besselj(4,z))

tf = logical
   1

Input Arguments

eqn — Recurrence relations to solve

symbolic equation | vector of symbolic equations

Recurrence relations to solve, specified as a symbolic equation or vector of symbolic equations. The symbolic equations must contain symbolic functions that depend on a single indexing parameter, or the function argument must have only one independent variable.

The solveRecurrence function consistently solves symbolic equations that define a system of linear recurrence relations with constant coefficients. In some cases, solveRecurrence can also solve linear recurrence relations with nonconstant coefficients or a system of nonlinear recurrence relations.

Example: syms f(n); eqn = f(n) == 3*f(n-1) - f(n-2)

Example: syms f(n); eqn = f(n+1)*f(n) == 2*f(n) + 1

f — Functions to solve for

symbolic function | vector of symbolic functions

Functions to solve for, specified as a symbolic function or vector of symbolic functions.

cond — Initial conditions

symbolic equation | vector of symbolic equations

Initial conditions, specified as a symbolic equation or vector of symbolic equations.

Output Arguments

sol — Solution of recurrence relations

symbolic expression | vector of symbolic expressions

Solution of the recurrence relations, returned as a symbolic expression or vector of symbolic expressions.

If the solveRecurrence function cannot solve the recurrence relations, then it returns an unevaluated call.

More About

Recurrence Relations

Recurrence relations are equations that relate the next term in a sequence $$f(n+1)$$ to the previous terms in the sequence $$f(n),\dots ,f(n-m)$$. These relations contain functions $$f(n)$$ that depend on an indexing parameter $$n$$.

The solveRecurrence function solves $$f(n)$$ in linear recurrence relations (or linear difference equations) with constant coefficients $$c_i$$ that have the form

$$f(n)=c_0+c_{1}f(n-1)+\dots +c_{k}f(n-k).$$

This form is considered homogeneous if $$c_0=0$$ and nonhomogeneous if $$c_o\ne 0$$. In some cases, the solveRecurrence function can also solve linear recurrence relations with nonconstant coefficients $$c_0,\dots ,c_k$$ that depend on $$n$$ or nonlinear recurrence relations, such as

$$f(n+1)f(n)=c_0+c_{1}f(n).$$

The solveRecurrence function also solves a system of linear recurrence relations that has the form

$$\left[\begin{array}{c}{f}_1(n+1)\\ f_2(n+1)\\ ⋮\\ f_k(n+1)\end{array}\right]=\left[\begin{array}{ccccc}{c}_{10}& c_{11}& c_{12}& \cdots & c_{1k}\\ c_{20}& c_{21}& c_{22}& \cdots & c_{2k}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ c_{k0}& c_{k1}& c_{k2}& \cdots & c_{kk}\end{array}\right]\left[\begin{array}{c}1\\ f_1(n)\\ f_2(n)\\ ⋮\\ f_k(n)\end{array}\right].$$

Version History

Introduced in R2026a