The rsolve command attempts to solve the recurrence relation(s) specified in eqns for the functions in fcns, returning an expression for the general term of the function.

The first argument must be a single recurrence relation or a set of recurrence relations and boundary conditions. Any expressions in eqns, which are not equations are understood to be equal to zero. Boundary conditions should be given in consecutive values of the indices, and for the case of multiple functions, all conditions should start at the same index.

The second argument fcns indicates the functions that rsolve must solve for. A function may be represented by a name or an unevaluated function call whose argument is a name. If the function is represented by a name, the index variable for the solution is deduced from the recurrence equations. If the function is represented by an unevaluated function call, the argument name is used as the solution index. If the solution index differs from the index name in a recurrence equation, then the equation must be independent of the solution index.

If fcns is a set, the solution is returned as a set of equations. The left-hand side of each equation is the function name. Otherwise, an expression for the solution is returned.

The rsolve command can solve linear recurrences with constant coefficients, systems of linear recurrences with constant coefficients, divide and conquer recurrences with constant coefficients, many first order linear recurrences, and some nonlinear first order recurrences.

If insufficient boundary conditions are given, rsolve uses symbolic function names as default values.

For linear recurrences with constant coefficients and systems of linear recurrences with constant coefficients, if no boundary conditions are given, symbolic function calls starting with index 0 are used.

Note: A solution of a recurrence can be completely different based on the starting point of the recurrence. If output is desired in terms of symbolic function calls starting at an index different from 0, use conditions of the form $u\left(i\right)=u\left(i\right),u\left(i+1\right)=u\left(i+1\right),...$ for a recurrence starting at i.

For divide and conquer recurrences, a symbolic function call at index 1 is used.

The ratio of the indices in divide and conquer recurrences must be an integer greater than 1 or a name. If the ratio is a name, it is understood to represent an integer greater than 1. It is assumed that the index variable is a non-negative power of the ratio.

Boundary conditions for linear recurrences with constant coefficients and systems of linear recurrences with constant coefficients may be specified in one of three ways:

- a and b are integers

- c is a constant with respect to the index variable for the sequence

- k is a name

- $f\left(k\right)$ is an expression of k.

The boundary condition $t\left(a..b\right)=c$ is equivalent to $t\left(a\right)=t\left(a+1\right)=\mathrm{...}=t\left(b\right)=c$ and the condition $t\left(k=a..b\right)=f\left(k\right)$ is equivalent to $t\left(a\right)=f\left(a\right),t\left(a+1\right)=f\left(a+1\right),...,t\left(b\right)=f\left(b\right)$.

The $'\mathrm{genfunc}'\left(z\right)$ option is valid for linear recurrences with constant coefficients and systems of linear recurrences with constant coefficients. In this case, rsolve returns the generating functions of the sequences defined by eqns. The name z is used as the generating function variable.

The makeproc option is valid for any single recurrence that can be uniquely isolated (solved) for the highest indexed function. In this case, rsolve returns a procedure body for evaluating the function defined by eqns.

The series option leads to finding formal series solution using LinearFunctionalSystems[SeriesSolution]. The truncation order of the series is determined by the global variable Order.

Setting infolevel['rsolve'] := 2 provides information about the choices rsolve makes to evaluate a recurrence.

If rsolve is unable to compute a solution, it returns the unevaluated function invocation.  This unevaluated rsolve invocation may be understood by other functions;  for example, the asympt function is able to compute an asymptotic series expansion for the solution in some cases.

$\mathrm{rsolve}\left(f\left(n\right)=-3f\left(n-1\right)-2f\left(n-2\right)\,f\left(k\right)\right)$

$\left(f\left(1\right)+2f\left(0\right)\right){\left(\mathrm{-1}\right)}^k+\left(-f\left(1\right)-f\left(0\right)\right){\left(\mathrm{-2}\right)}^k$

$\mathrm{rsolve}\left(\left\{f\left(n\right)=-3f\left(n-1\right)-2f\left(n-2\right)\,f\left(1..2\right)=1\right\}\,\left\{f\right\}\right)$

$\left\{f\left(n\right)={\left(\mathrm{-2}\right)}^n-3{\left(\mathrm{-1}\right)}^n\right\}$

$\mathrm{rsolve}\left(f\left(n\right)=3f\left(\frac{n}{2}\right)+5n\,f\left(n\right)\right)$

$f\left(1\right)n^{\frac{\ln \left(3\right)}{\ln \left(2\right)}}-10n+10n^{\frac{\ln \left(3\right)}{\ln \left(2\right)}}$

$\mathrm{rsolve}\left(t\left(bn\right)=at\left(n\right)+n\,t\left(m\right)\right)$

$m^{\frac{\ln \left(a\right)}{\ln \left(b\right)}}\left(t\left(1\right)+\frac{1-{\left(\frac{b}{a}\right)}^{\frac{\ln \left(m\right)}{\ln \left(b\right)}}}{-b+a}\right)$

$\mathrm{rsolve}\left(\left\{y\left(0\right)=1\,y\left(n\right)=ny\left(n-1\right)\right\}\,y\right)$

$\mathrm{\Gamma }\left(n+1\right)$

$\mathrm{rsolve}\left(\left\{y\left(n\right)y\left(n-1\right)+y\left(n\right)-y\left(n-1\right)=0\,y\left(0\right)=a\right\}\,y\right)$

$\frac{a}{na+1}$

$\mathrm{rsolve}\left(\left\{y\left(n+1\right)+f\left(n\right)=22^n+n\,f\left(n+1\right)-y\left(n\right)=n-2^n+3\,f\left(5\right)=6\,y\left(k=1..5\right)=2^k-1\right\}\,\left\{f\,y\right\}\right)$

$\left\{f\left(n\right)=n+1\,y\left(n\right)=2^n-1\right\}$

$\mathrm{rsolve}\left(\left\{F\left(n\right)=F\left(n-1\right)+F\left(n-2\right)\,F\left(1..2\right)=1\right\}\,F\,'\mathrm{genfunc}'\left(x\right)\right)$

$-\frac{x}{x^2+x-1}$

$\mathrm{rsolve}\left(\left\{s\left(0\right)=0\,s\left(n\right)=s\left(n-1\right)+t\left(n-1\right)\,t\left(0\right)=1\,t\left(n\right)=s\left(n\right)+t\left(n-1\right)\right\}\,\left\{s\,t\right\}\,'\mathrm{genfunc}'\left(z\right)\right)$

$\left\{s\left(z\right)=\frac{z}{z^2-3z+1}\,t\left(z\right)=-\frac{z-1}{z^2-3z+1}\right\}$

$\mathrm{rsolve}\left(\left\{s\left(0\right)=1\,s\left(n\right)=2s\left(n-1\right)\right\}\,s\,'\mathrm{makeproc}'\right)$

$\mathbf{proc}\left(n\right)\mathbf{if}1<\mathrm{nargs}\mathbf{then}\&apos;\mathrm{procname}\&apos;\left(\mathrm{args}\right)\mathbf{else}\mathrm{expand}\left(2\&Hat;n\right)\mathbf{end\; if}\mathbf{end\; proc}$

$\mathrm{rsolve}\left(nu\left(n+1\right)+u\left(n\right)\&comma;u\left(n\right)\right)$

$\left\{\begin{array}{cc}u\left(0\right)& n=0\\ \mathrm{undefined}& \mathrm{otherwise}\end{array}\right.$

$\mathrm{rsolve}\left(\left\{nu\left(n+1\right)+u\left(n\right)\&comma;u\left(1\right)=u\left(1\right)\right\}\&comma;u\left(n\right)\right)$

$-\frac{{\left(\mathrm{-1}\right)}^{n}u\left(1\right)}{\mathrm{\Gamma }\left(n\right)}$

$\mathrm{sys}≔\left\{\mathrm{y2}\left(x\right)x^2+3\mathrm{y2}\left(x\right)x+2\mathrm{y2}\left(x\right)-2\mathrm{y1}\left(x\right)x^2-4\mathrm{y1}\left(x\right)x+\mathrm{y1}\left(x+1\right)x^2+\mathrm{y1}\left(x+1\right)x\&comma;\mathrm{y2}\left(x+2\right)-\mathrm{y1}\left(x\right)\right\}\&colon;$

$\mathrm{vars}≔\left\{\mathrm{y1}\left(x\right)\&comma;\mathrm{y2}\left(x\right)\right\}\&colon;$

$\mathrm{rsolve}\left(\mathrm{sys}\&comma;\mathrm{vars}\&comma;'\mathrm{series}'\right)$

$\left\{\mathrm{y1}\left(x\right)=\frac{12916{\mathrm{\_c}}_1}{3}-736400{\mathrm{\_c}}_4-182480{\mathrm{\_c}}_3+13440{\mathrm{\_c}}_2+x\left(98000{\mathrm{\_c}}_4+25040{\mathrm{\_c}}_3-\frac{1732{\mathrm{\_c}}_1}{3}-1560{\mathrm{\_c}}_2\right)+x\left(x-1\right)\left(-7000{\mathrm{\_c}}_4-1480{\mathrm{\_c}}_3+\frac{170{\mathrm{\_c}}_1}{3}+240{\mathrm{\_c}}_2\right)+x\left(x-1\right)\left(x-2\right)\left(1400{\mathrm{\_c}}_4+440{\mathrm{\_c}}_3-\frac{10{\mathrm{\_c}}_1}{3}+20{\mathrm{\_c}}_2\right)+x\left(x-1\right)\left(x-2\right)\left(x-3\right)\left(30{\mathrm{\_c}}_3+{\mathrm{\_c}}_1+10{\mathrm{\_c}}_2\right)+x\left(x-1\right)\left(x-2\right)\left(x-3\right)\left(x-4\right)\left(12{\mathrm{\_c}}_3+{\mathrm{\_c}}_2+42{\mathrm{\_c}}_4\right)+\mathrm{O}\left(x^6\right)\&comma;\mathrm{y2}\left(x\right)=3600{\mathrm{\_c}}_1-604800{\mathrm{\_c}}_4-151200{\mathrm{\_c}}_3+10800{\mathrm{\_c}}_2+x\left(-2520{\mathrm{\_c}}_2+151200{\mathrm{\_c}}_4+38880{\mathrm{\_c}}_3-960{\mathrm{\_c}}_1\right)+x\left(x-1\right)\left(-4120{\mathrm{\_c}}_3-15400{\mathrm{\_c}}_4+\frac{338{\mathrm{\_c}}_1}{3}+240{\mathrm{\_c}}_2\right)+x\left(x-1\right)\left(x-2\right)\left(1400{\mathrm{\_c}}_4+440{\mathrm{\_c}}_3-\frac{34{\mathrm{\_c}}_1}{3}\right)+x\left(x-1\right)\left(x-2\right)\left(x-3\right){\mathrm{\_c}}_1+x\left(x-1\right)\left(x-2\right)\left(x-3\right)\left(x-4\right){\mathrm{\_c}}_2+\mathrm{O}\left(x^6\right)\right\}$