The commands find the polynomial, rational, hypergeometric and d'Alembertian solutions of linear recurrence equations with rational polynomial coefficients.

Note that only LREtools[polysols] and LREtools[ratpolysols] are capable of finding solutions for a system of recurrences. Both LREtools[hypergeomsols] and LREtools[dAlembertiansols] can obtain recurrence solutions only for a single equation in a single recurrence variable.

Optionally, you can specify output=basis, output=basis[var], output=onesol, output=gensol, or output=anysol.

output=basis

Requests that independent solutions be provided in the form of a list of independent solutions (the basis). If the input recurrence is homogeneous, then the independent solutions are output in a list as $\[\mathrm{sol1},\mathrm{sol2},...,\mathrm{soln}\]$. If the input recurrence is inhomogeneous, then the output is a list containing the list of independent solutions in the first element, and a particular solution in the second, as $\[\[\mathrm{sol1},\mathrm{sol2},...,\mathrm{soln}\],\mathrm{part}\]$.

output=basis[var]

This is related to the output=basis form, but rather than providing the output in list form, it is provided as a single algebraic expression that is a var-linear combination of the independent solutions plus any particular solution for the inhomogeneous case. The independent solutions will have indexed coefficients of the form ${\mathrm{var}}_0,{\mathrm{var}}_1,...,{\mathrm{var}}_n$, where var is as provided in the output=basis[var] option. This is primarily provided for backward compatibility, as the default operation of the basis output used to be as though output=basis[_C] was provided.

output=onesol

This specifies that only a single solution be provided as output. In general, for inhomogeneous recurrences this is a particular solution for the problem, while for homogeneous recurrences this is simply one of the independent solutions for the recurrence.

output=gensol

This specifies that the fully general solution should be obtained for the problem, and will fail if unable to obtain as many independent solutions as the order of the recurrence (regardless of initial conditions). This is the default for systems of recurrences, and for any single recurrences specified in RESol form. The initial conditions are applied once the full solution is obtained.

output=anysol

This specifies that if a solution can be obtained that satisfies the initial conditions, then it should be returned regardless of the number of independent solutions obtained. For example, if no independent solutions can be obtained, but no initial conditions have been specified, then the particular solution is output. This is the default for any single recurrences that are not specified in RESol form.

For the definition of the format of a problem, see the help page for LREtools[REcreate].

As mentioned, the functions polysols and ratpolysols can also solve problems when the input is a system of recurrence relations. They invoke LinearFunctionalSystems[PolynomialSolution] and LinearFunctionalSystems[RationalSolution], respectively.

$\mathrm{with}\left(\mathrm{LREtools}\right)\:$

$\mathrm{rec}≔n\left(n+1\right)a\left(n+2\right)-2n\left(n+10\right)a\left(n+1\right)+\left(n+9\right)\left(n+10\right)a\left(n\right)=0\:$

$\mathrm{polysols}\left(\mathrm{rec}\,a\left(n\right)\,\varnothing \,\mathrm{output}=\mathrm{basis}\right)$

$\left[n^{10}-750n^8-15120n^7-140847n^6-740880n^5-2304100n^4-4142880n^3-3904704n^2-1451520n\,n^9+36n^8+546n^7+4536n^6+22449n^5+67284n^4+118124n^3+109584n^2+40320n\right]$

$\mathrm{rec}≔a\left(n+2\right)-\frac{\left(2n+1\right)a\left(n+1\right)}{n}+\frac{na\left(n\right)}{n-1}=n\left(n+1\right)\:$

$\mathrm{polysols}\left(\mathrm{rec}\,a\left(n\right)\,\varnothing \,\mathrm{output}=\mathrm{onesol}\right)$

$\frac{1}{9}{n}^4-\frac{5}{18}{n}^3-\frac{1}{9}{n}^2+\frac{5}{18}$

$\mathrm{polysols}\left(\mathrm{rec}\,a\left(n\right)\,\varnothing \,\mathrm{output}=\mathrm{gensol}\right)$

$\mathrm{polysols}\left(\mathrm{rec}\,a\left(n\right)\,\varnothing \right)$

$\frac{n^4}{9}-\frac{5n^3}{18}-\frac{n^2}{9}+\left(\frac{11}{18}+a\left(2\right)\right)n-\frac{1}{3}-a\left(2\right)$

$\mathrm{rec}≔\left(n+1\right)\left(n+3\right)a\left(n+1\right)-2n\left(n+2\right)a\left(n\right)+n^{2}a\left(n-1\right)=a\left(n\right)\:$

$\mathrm{ratpolysols}\left(\mathrm{rec}\,a\left(n\right)\,\varnothing \,\mathrm{output}=\mathrm{basis}\right)$

$\left[\frac{1}{\left(n+2\right)\left(n+1\right)}\right]$

$\mathrm{rec}≔\left(n+4\right)a\left(n+2\right)+a\left(n+1\right)-\left(n+1\right)a\left(n\right)\:$

$\mathrm{hypergeomsols}\left(\mathrm{rec}\,a\left(n\right)\,\left\{a\left(0\right)=1\,a\left(1\right)=3\right\}\right)$

$\frac{8}{\left(n+2\right)\left(n+1\right)}-\frac{2{\left(\mathrm{-1}\right)}^n\left(2n+3\right)}{\left(n+1\right)\left(n+2\right)}$

$\mathrm{rec}≔\left(-n-1\right)a\left(n\right)+\left(3+2n\right)a\left(n+1\right)+\left(-n-2\right)a\left(n+2\right)=\frac{1}{n+2}\:$

$\mathrm{dAlembertiansols}\left(\mathrm{rec}\,a\left(n\right)\,\varnothing \,\mathrm{output}=\mathrm{basis}\right)$

$\left[\left[1\,\sum _{\mathrm{n1}=0}^{n-1}\frac{1}{\mathrm{n1}+1}\right]\,-\left(\sum _{\mathrm{n1}=0}^{n-1}\frac{\sum _{\mathrm{n2}=0}^{\mathrm{n1}-1}\frac{1}{\mathrm{n2}+2}}{\mathrm{n1}+1}\right)\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\,\mathrm{y2}\left(x+1\right)-\mathrm{y1}\left(x\right)\right]\:$

$\mathrm{vars}≔\left[\mathrm{y1}\left(x\right)\,\mathrm{y2}\left(x\right)\right]\:$

$\mathrm{polysols}\left(\mathrm{sys}\,\mathrm{vars}\,\varnothing \,\mathrm{output}=\mathrm{basis}\right)$

$\left[{\mathrm{\_C}}_1+x\left({\mathrm{\_C}}_1+2{\mathrm{\_C}}_2\right)+x\left(x-1\right){\mathrm{\_C}}_2\,x{\mathrm{\_C}}_1+x\left(x-1\right){\mathrm{\_C}}_2\right]$

The algorithm Maple uses to compute hypergeometric solutions is based on the following paper.

van Hoeij, M. "Finite Singularities and Hypergeometric Solutions of Linear Recurrence Equations." J. Pure Appl. Algebra. Vol. 139. (1999): 109-131.