"Gesloten" formulier voor Motzkin en gerelateerde nummers

Ik vraag me af of het onmogelijk is om het nde Motzkin-nummer te schrijven als een som van een vast aantal van bijvoorbeeld hypergeometrische termen. Om te illustreren wat ik bedoel: $ n! + (2n)! $ Is geen hypergeometrische term, maar het is geschreven als een optelsom van twee hypergeometrische termen.

Ik zou ook andere voorbeelden waarderen, vooral als ze afkomstig zijn van het tellen van gewogen Motzkin-paden.

3
Begrijp ik de juiste formule (10) op mathworld.wolfram.com/MotzkinNumber.html voor het $ n $ th Motzkin-nummer als een hypergeometrische $ \ textit {function} $ is een som van $ n/2 $ hypergeometric $ \ textit {terms} $?
toegevoegd de auteur Edward Nunn, de bron
Martin, ik heb de tag toegevoegd. De eenvoudigste formule die ik heb gevonden voor uw nummers is $ a_n = \ dfrac1 {n + 1} \ sum_i \ dfrac {(n + 1)!} {I! (I + 1)! (N-2 * i)!} $ . Maar er zijn zoveel andere voorbeelden (praktisch alles wat ik weet! :-)), zoals de nummers van Apery $ \ sum_k {\ dbinom {n + k} {k}} ^ 2 {\ dbinom {n} {k}} ^ 2 $, of Domb-nummers, of wat dan ook. Bewijzen dat er geen eindige hypergeometrische som is, is het onderwerp van het algoritme van Petkovcek in $ A = B $.
toegevoegd de auteur xecaps12, de bron
Victor, ja dat doe je, maar eindig aantal hypergeometrische termen betekent eindig en onafhankelijk van $ n $.
toegevoegd de auteur xecaps12, de bron

1 antwoord

Hoofdstuk 8 van Petkovsek - Wilf - Zeilberger $ A = B $ begint als volgt:

"Als je een gegeven som in gesloten vorm wilt evalueren, tot nu toe de gereedschappen die zijn geweest beschreven in dit boek hebben u in staat gesteld om een ​​herhalingsrelatie met polynoom te vinden coëfficiënten die uw som voldoet. Als die herhaling van orde 1 is, dan ben je klaar; je hebt de gewenste gesloten vorm voor je som gevonden, als een enkele hypergeometrische termijn. Als, aan de andere kant, de herhaling van order $ \ ge2 $ is, dan is er meer werk Te doen. Hoe kunnen we herkennen wanneer een dergelijke herhaling hypergeometrische oplossingen heeft, en hoe kunnen we ze allemaal vinden? "

"In dit hoofdstuk bespreken we de vraag hoe te herkennen wanneer een bepaalde herhaling relatie met polynomiale coëfficiënten heeft een gesloten vorm-oplossing. We nemen eerst de mogelijkheid om de term gesloten formulier te definiëren. "

"Een functie $ f (n) $ is naar verluidt van gesloten vorm als deze gelijk is aan een lineaire combinatie van een vast getal, $ r $, bijvoorbeeld, van hypergeometrische termen. Het aantal $ r $ moet een absolute constante zijn, d.w.z. deze moet onafhankelijk zijn van alle variabelen en parameters van het probleem."

"Neem een ​​definitieve som van de vorm $ f (n) = \ sum_k F (n; k) $ waar de summand $ F (n; k) $ is hypergeometrisch in beide argumenten. Heeft dit bedrag een gesloten vorm? De materiaal van dit hoofdstuk, samen met het algoritme van Hoofdstuk 6, biedt een complete algoritmische oplossing van dit probleem. "

Er zijn veel voorbeelden in dit hoofdstuk die het algoritme illustreren, zoals Ap \ 'ery's nummers $$ \ Sum_k {\ Binom {n + k} k} 2 {^ \ Binom {n}} k ^ 2. $$ Jouw specifieke volgorde $$ \ Sum_k \ frac {n?} {I! (I + 1)? (N-2i)!} $$ valt in de groep die valt onder het algoritme van hoofdstuk 8.

4
toegevoegd
heel erg bedankt voor dat zeer precieze antwoord! Ik geef toe dat ik een beetje beschaamd ben - ik denk dat ik mijn huiswerk niet goed heb gedaan :-) Tot vandaag dacht ik dat hyper alleen (dis) bewijst dat iets een hypergeometrische term is ... Nogmaals hartelijk dank!
toegevoegd de auteur Scott W, de bron
Ondertussen besefte ik wat ik al lang geleden had moeten leren, maar niet, namelijk Stelling 8.7.1 van A = B: Laat L een lineair herhalingsexploitant zijn met polynomiale coëf fi ciënten en h ∈ L (H_K) zodanig dat Lh = 0. Als h = som h_i waar h_i paarsgewijze ongelijke hypergeometrische termen zijn dan Lh_i = 0, voor i = 1, 2, ..., k.
toegevoegd de auteur Scott W, de bron
En de 3-term relatie, voor zover ik de OEIS-link volg, is $ (n + 2) a_n = (2n + 1) a_ {n-1} + (3n-3) a_ {n-2} $.
toegevoegd de auteur xecaps12, de bron
Graag gedaan, Martin! $ A = B $ is een nuttige bron. Aan iedereen.
toegevoegd de auteur xecaps12, de bron