A sequence $u\left(0\right)$, $u\left(1\right)$, $u\left(2\right)$, ... is holonomic if it satisfies a linear homogeneous recurrence relation with polynomial or rational function coefficients. Given a recurrence, the dependent variable, and sufficiently many initial terms to define a sequence, the command MinimalRecurrence computes the recurrence of provably minimal order that holds for all but finitely many terms. Key to the proof are generalized exponents, from which degree bounds are be computed that are used to prove that no lower order recurrence will be missed.

For a holonomic sequence $u\left(n\right)$, given by a recurrence relation and initial terms, SumDecompose writes $u\left(n\right)$ as a sum of holonomic sequences of lower order when possible: $u\left(n\right)$ = $u_1\left(n\right)$ + $u_2\left(n\right)$ + ... where each $u_i\left(n\right)$ is a holonomic sequence that can not be further decomposed as a sum of even lower order sequences. A holonomic sequence $u\left(n\right)$ has a non-trivial sum decomposition if and only if the minimal operator of $u\left(n\right)$ is an LCLM of lower order operators. SumDecompose computes an LCLM factorization of the minimal recurrence.

If $u\left(n\right)$ satisfies a recurrence $R$ that is an LCLM of lower order recurrences $R_1$, $R_2$ that have a non-trivial GCRD, then the sum decomposition $u\left(n\right)=u_1\left(n\right)+u_2\left(n\right)$ which writes $u\left(n\right)$ as a solution of $R_1$ plus a solution of $R_2$ is not unique because one can add any solution of the GCRD to $\mathrm{u1}\left(n\right)$, and subtract the same from $\mathrm{u2}\left(n\right)$. To express this non-uniqueness, parameters ${\mathrm{\_Z}}_i$ (i=1,2,...) will then appear in the optional output Values. Any choice for these parameters ${\mathrm{\_Z}}_i$ will give a correct sum decomposition.

If $u\left(n\right)$ is a holonomic sequence, and if $v$ is a list of sufficiently many initial terms of $u\left(n\right)$, then GuessRecurrence computes a recurrence for $u\left(n\right)$. Similar functionality is provided by gfun[`listtorec`], however, GuessRecurrence tries orders and degrees that are as high as possible for the number of specified terms (minus some terms set aside for checking). If a sequence is holonomic, and if sufficiently many terms are specified, then the output will be a correct recurrence. However, given only finitely many terms, it is not possible to prove that a sequence is holonomic, and if so, how many terms are needed to find the correct recurrence, hence the name GuessRecurrence.

The optional argument offset is needed when the first element of $v$ is not $u\left(0\right)$. For instance, if the sequence starts with $u\left(1\right)$, $u\left(2\right)$, ... then the offset is 1. The optional literal argument Minimize causes GuessRecurrence, if it finds a recurrence, to run a part of MinimalRecurrence. It skips steps that can be slow when the guessed recurrence is not correct, so if the guessed recurrence is correct, to check or prove that its order is minimal, call MinimalRecurrence.

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

$R≔u\left(n+2\right)-u\left(n+1\right)n+\left(n-1\right)u\left(n\right)=0$

$R≔u\left(n+2\right)-u\left(n+1\right)n+\left(n-1\right)u\left(n\right)=0$

$\mathrm{MinimalRecurrence}\left(R\,u\left(n\right)\,\left\{u\left(0\right)=1\,u\left(1\right)=2\right\}\right)$

$u\left(n+1\right)-u\left(n\right)=0,''Relation\; holds\; for'',2\le n,''Initial\; terms'',\left\{u\left(2\right)=1\right\}$

$R≔2\left(-252307n+1041077\right)a\left(n\right)+\left(504614n^2-3362985n+5118150\right)a\left(n-1\right)+\left(1280831n^2-7397886n+6461565\right)a\left(n-2\right)+\left(746598n^2-2913543n-1336090\right)a\left(n-3\right)+\left(-405481n^2+6175011n-15469320\right)a\left(n-4\right)+\left(-375862n^2+4098537n-8846430\right)a\left(n-5\right)+2\left(-187931n+560630\right)a\left(n-6\right)=0$

$R≔2\left(-252307n+1041077\right)a\left(n\right)+\left(504614n^2-3362985n+5118150\right)a\left(n-1\right)+\left(1280831n^2-7397886n+6461565\right)a\left(n-2\right)+\left(746598n^2-2913543n-1336090\right)a\left(n-3\right)+\left(-405481n^2+6175011n-15469320\right)a\left(n-4\right)+\left(-375862n^2+4098537n-8846430\right)a\left(n-5\right)+2\left(-187931n+560630\right)a\left(n-6\right)=0$

$v≔\left[2\,8\,20\,152\,994\,7888\,70152\,695760\right]$

$v≔\left[2\,8\,20\,152\,994\,7888\,70152\,695760\right]$

$\mathrm{offset}≔3$

$\mathrm{offset}≔3$

$\mathrm{init}≔\left\{\mathrm{seq}\left(a\left(i+\mathrm{offset}\right)=v\left[i+1\right]\,i=0..\mathrm{nops}\left(v\right)-1\right)\right\}$

$\mathrm{init}≔\left\{a\left(3\right)=2\,a\left(4\right)=8\,a\left(5\right)=20\,a\left(6\right)=152\,a\left(7\right)=994\,a\left(8\right)=7888\,a\left(9\right)=70152\,a\left(10\right)=695760\right\}$

$\mathrm{MinRec}≔\mathrm{MinimalRecurrence}\left(R\,a\left(n\right)\,\mathrm{init}\right)$

$\mathrm{MinRec}≔n\left(n+2\right)\left(n-1\right){\left(2n-1\right)}^{2}a\left(n+3\right)-\left(n-1\right)\left(2n+1\right)\left(n+3\right)\left(2n^3-n^2-6n+6\right)a\left(n+2\right)-\left(2n-1\right)\left(n+3\right)\left(n+2\right)\left(2n^3+n^2-6n-6\right)a\left(n+1\right)-\left(n+3\right)\left(n+2\right)\left(n+1\right){\left(2n+1\right)}^{2}a\left(n\right)=0,''Relation\; holds\; for'',3\le n,''Initial\; terms'',\left\{a\left(3\right)=2\,a\left(4\right)=8\,a\left(5\right)=20\right\}$

$v≔\left[1\,16\,181\,1821\,17557\,167449\,1604098\,15555398\,153315999\,1538907306\,15743413076\,164161815768\,1744049683213\,18865209953045\,207591285198178\,2321616416280982\,26362085777156567\,303635722412859447\,3544040394934246209\,41881891423602685193\,500690223797206725847\,6050434838705784406551\,73852382382545858737126\,909943177632220199263042\,11310232116090782070465841\,141740653186926189324638372\,1790036582998939530743648877\,22770455209205915603060025597\,291634367197743500729356426685\,3759180275300445999022196165965\,48750519654702845837670090343690\,635848553797809170295520418710782\,8338432923207513905107942840897207\,109913145478761588817424570169064291\,1455916882814340050784910924367005361\,19374962426023058076066772960412712729\,258979624482677760588598118094798186615\,3476327437847817541578871045524189487175\,46851360725326736422851309373608573753486\,633857940571765164166776008459212715340810\,8607097892030531766959008406359887257969457\,117286552938953817595159195919871584342485297\,1603623007332069507772874752316422357340842762\,21996762674368942915438738304929059321225086798\,302664294908715565330818633036974690001530040351\,4176922219912768041025272080018132501948775088287\,57808845662644153479643363699008882629886528423638\,802283219167808255381222688196525534650228123585138\,11163800149167922644844439353688236270618650367355161\,155741807964112273187678730231773629630772872894151753\,2178047448779761494253016767936757887129550255760546007\,30532382229662866143058035395061816620136483264523454767\,428992304879718047693575798315682771874889192666983370217\,6040874726749408043810961537174482718932561906717437996521\,85247065836795137741519089655948480065911416135277934186122\,1205473572310704760456166438628704554807892246934960123492974\,17080691328825216538079811628828842602913045806045692424793199\,242490618231277416363895463725311815053057447415805956401781074\,3449051981599752494976878291288265335774407317286658116086140292\,49146729874459740441919474443279449173330676418367247395292174104\,701545004460344542554347244732973635473253721108063985623413774493\,10031352489974488598965839409501869308563264624360941341155603315133\,143676099686733622553027802165808514225442825885288070049291479402458\,2061150250350872821775172625249417982149763747555391307060801829076558\,29615206122264489924249122928926530951101815751524692956745132636470263\right]$

$v≔\left[1\,16\,181\,1821\,17557\,167449\,1604098\,15555398\,153315999\,1538907306\,15743413076\,164161815768\,1744049683213\,18865209953045\,207591285198178\,2321616416280982\,26362085777156567\,303635722412859447\,3544040394934246209\,41881891423602685193\,500690223797206725847\,6050434838705784406551\,73852382382545858737126\,909943177632220199263042\,11310232116090782070465841\,141740653186926189324638372\,1790036582998939530743648877\,22770455209205915603060025597\,291634367197743500729356426685\,3759180275300445999022196165965\,48750519654702845837670090343690\,635848553797809170295520418710782\,8338432923207513905107942840897207\,109913145478761588817424570169064291\,1455916882814340050784910924367005361\,19374962426023058076066772960412712729\,258979624482677760588598118094798186615\,3476327437847817541578871045524189487175\,46851360725326736422851309373608573753486\,633857940571765164166776008459212715340810\,8607097892030531766959008406359887257969457\,117286552938953817595159195919871584342485297\,1603623007332069507772874752316422357340842762\,21996762674368942915438738304929059321225086798\,302664294908715565330818633036974690001530040351\,4176922219912768041025272080018132501948775088287\,57808845662644153479643363699008882629886528423638\,802283219167808255381222688196525534650228123585138\,11163800149167922644844439353688236270618650367355161\,155741807964112273187678730231773629630772872894151753\,2178047448779761494253016767936757887129550255760546007\,30532382229662866143058035395061816620136483264523454767\,428992304879718047693575798315682771874889192666983370217\,6040874726749408043810961537174482718932561906717437996521\,85247065836795137741519089655948480065911416135277934186122\,1205473572310704760456166438628704554807892246934960123492974\,17080691328825216538079811628828842602913045806045692424793199\,242490618231277416363895463725311815053057447415805956401781074\,3449051981599752494976878291288265335774407317286658116086140292\,49146729874459740441919474443279449173330676418367247395292174104\,701545004460344542554347244732973635473253721108063985623413774493\,10031352489974488598965839409501869308563264624360941341155603315133\,143676099686733622553027802165808514225442825885288070049291479402458\,2061150250350872821775172625249417982149763747555391307060801829076558\,29615206122264489924249122928926530951101815751524692956745132636470263\right]$

$\mathrm{offset}≔4$

$\mathrm{offset}≔4$

$R≔\mathrm{GuessRecurrence}\left(v\,u\left(n\right)\,\mathrm{offset}\,'\mathrm{Minimize}'\right)$

$R≔n\left(n+8\right)\left(225n^5+4320n^4+31407n^3+107518n^2+173854n+108052\right){\left(n+7\right)}^2{\left(n+6\right)}^{2}u\left(n+4\right)-\left(6750n^9+238500n^8+3615975n^7+30715368n^6+160015744n^5+525218164n^4+1069898799n^3+1267661576n^2+739767140n+123127200\right){\left(n+6\right)}^{2}u\left(n+3\right)+\left(n+3\right)\left(61425n^{10}+2417085n^9+41671026n^8+413620650n^7+2610729041n^6+10910664473n^5+30420114588n^4+55433353504n^3+62336195488n^2+38044196976n+8981078400\right)u\left(n+2\right)-2\left(n+3\right)\left(92250n^8+2863125n^7+37459200n^6+269470646n^5+1163725924n^4+3079221085n^3+4843780850n^2+4089668904n+1382141376\right){\left(n+2\right)}^{2}u\left(n+1\right)+576\left(n+3\right)\left(225n^5+5445n^4+50937n^3+229909n^2+501516n+425376\right){\left(n+1\right)}^2{\left(n+2\right)}^{3}u\left(n\right)=0$

$\mathrm{init}≔\left\{\mathrm{seq}\left(u\left(i+\mathrm{offset}\right)=v\left[i+1\right]\,i=0..5\right)\right\}$

$\mathrm{init}≔\left\{u\left(4\right)=1\,u\left(5\right)=16\,u\left(6\right)=181\,u\left(7\right)=1821\,u\left(8\right)=17557\,u\left(9\right)=167449\right\}$

$S≔\mathrm{SumDecompose}\left(R\,u\left(n\right)\,\mathrm{init}\,'\mathrm{Values}'\right)$

$S≔u\left(n\right)=\mathrm{u1}\left(n\right)+\mathrm{u2}\left(n\right),{\left(n+4\right)}^2\mathrm{u1}\left(n+2\right)+\left(-10n^2-42n-41\right)\mathrm{u1}\left(n+1\right)+9{\left(n+1\right)}^2\mathrm{u1}\left(n\right)=0,\left(n+6\right){\left(n+5\right)}^2\mathrm{u2}\left(n+2\right)+\left(-20n^3-182n^2-510n-428\right)\mathrm{u2}\left(n+1\right)+64\left(n+2\right){\left(n+1\right)}^2\mathrm{u2}\left(n\right)=0,''Relation\; holds\; for'',4\le n$

$\mathrm{seq}\left(\mathrm{Values}\left(1\,i\right)\,i=\mathrm{offset}..\mathrm{offset}+10\right)$

$\mathrm{-23},\mathrm{-103},\mathrm{-513},\mathrm{-2761},\mathrm{-15767},\mathrm{-94359},\mathrm{-586590},\mathrm{-3763290},\mathrm{-24792705},\mathrm{-167078577},\mathrm{-1148208090}$

$\mathrm{seq}\left(\mathrm{Values}\left(2\,i\right)\,i=\mathrm{offset}..\mathrm{offset}+10\right)$

$24,119,694,4582,33324,261808,2190688,19318688,178108704,1705985883,16891621166$

$\mathrm{ODE}≔x\left(16x-1\right)\left(x-1\right)\left(16x^3-25x^2+14x-1\right)\mathrm{diff}\left(y\left(x\right)\,x\,x\right)+\left(512x^5-1200x^4+1289x^3-531x^2+51x-1\right)\mathrm{diff}\left(y\left(x\right)\,x\right)+\left(64x^4-132x^3+131x^2-60x+5\right)y\left(x\right)=0$

$\mathrm{ODE}≔x\left(16x-1\right)\left(x-1\right)\left(16x^3-25x^2+14x-1\right)\left(\frac{{\ⅆ}^2}{\ⅆx^2}y\left(x\right)\right)+\left(512x^5-1200x^4+1289x^3-531x^2+51x-1\right)\left(\frac{\ⅆ}{\ⅆx}y\left(x\right)\right)+\left(64x^4-132x^3+131x^2-60x+5\right)y\left(x\right)=0$

$S≔\mathrm{gfun}\left[\mathrm{diffeqtorec}\right]\left(\left\{\mathrm{ODE}\,y\left(0\right)=1\right\}\,y\left(x\right)\,u\left(n\right)\right)$

$S≔\left\{\left(256n^2+256n+64\right)u\left(n\right)+\left(-672n^2-1872n-1332\right)u\left(n+1\right)+\left(665n^2+3284n+4039\right)u\left(n+2\right)+\left(-279n^2-1926n-3327\right)u\left(n+3\right)+\left(31n^2+268n+581\right)u\left(n+4\right)+\left(-n^2-10n-25\right)u\left(n+5\right)\,u\left(0\right)=1\,u\left(1\right)=5\,u\left(2\right)=55\,u\left(3\right)=719\,u\left(4\right)=10119\right\}$

$\mathrm{MinimalRecurrence}\left(S\right)$

$\left(4n^3+23n^2+19n+4\right){\left(n+2\right)}^{2}u\left(n+2\right)-\left(17n^2+34n+12\right)\left(4n^3+31n^2+49n+18\right)u\left(n+1\right)+4\left(4n^3+35n^2+77n+50\right){\left(2n+1\right)}^{2}u\left(n\right)=0,''Relation\; holds\; for'',0\le n,''Initial\; terms'',\left\{u\left(0\right)=1\,u\left(1\right)=5\right\}$

M. van Hoeij. "Factoring Linear Recurrence Operators." URL www.math.fsu.edu/~hoeij/2019/slides.pdf

The LREtools[MinimalRecurrence], LREtools[SumDecompose] and LREtools[GuessRecurrence] commands were introduced in Maple 2021.

For more information on Maple 2021 changes, see Updates in Maple 2021.