Konstantní rekurzivní sekvence - Constant-recursive sequence

v matematika, a konstantní rekurzivní sekvence nebo C-konečná posloupnost je sekvence splňující lineár opakování s konstantními koeficienty.

Definice

Objednávka-d homogenní lineární rekurence s konstantními koeficienty je rovnice tvaru

{ displaystyle s (n) = c_ {1} s (n-1) + c_ {2} s (n-2) + tečky + c_ {d} s (n-d),}

Kde d koeficienty ${ displaystyle c_ {1}, c_ {2}, tečky, c_ {d}}$ jsou konstanty.

Sekvence ${ displaystyle s (0), s (1), s (2), tečky}$ je konstantní rekurzivní sekvence pokud existuje objednávkad homogenní lineární opakování s konstantními koeficienty, které uspokojí pro všechny ${ displaystyle n geq d}$ .

Ekvivalentně ${ displaystyle s (n) _ {n geq 0}}$ je konstantní rekurzivní, pokud je množina sekvencí

{ displaystyle {s (n + r) _ {n geq 0}: r geq 0 }}

je obsažen v a vektorový prostor jehož rozměr je konečný.

Příklady

Fibonacciho sekvence

Posloupnost 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... z Fibonacciho čísla uspokojuje opakování

{ displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}

s počáteční podmínky

{ displaystyle F_ {0} = 0}

{ displaystyle F_ {1} = 1.}

Explicitně, opakování přináší hodnoty

{ displaystyle F_ {2} = F_ {1} + F_ {0} = 1}

{ displaystyle F_ {3} = F_ {2} + F_ {1} = 2}

{ displaystyle F_ {4} = F_ {3} + F_ {2} = 3}

{ displaystyle F_ {5} = F_ {4} + F_ {3} = 5}

atd.

Lucasovy sekvence

Sekvence 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... (sekvence A000032 v OEIS ) z Lucasova čísla uspokojuje stejnou recidivu jako Fibonacciho sekvence, ale s počátečními podmínkami

{ displaystyle L_ {0} = 2}

{ displaystyle L_ {1} = 1.}

Obecněji, každý Lucasova sekvence je konstantní rekurzivní sekvence.

Geometrické posloupnosti

The geometrická posloupnost ${ displaystyle a, ar, ar ^ {2}, dots}$ je konstantní rekurzivní, protože uspokojuje opakování ${ displaystyle s (n) = rs (n-1)}$ pro všechny ${ displaystyle n geq 1}$ .

Nakonec periodické sekvence

Sekvence, která je nakonec periodická s délkou období ${ displaystyle ell}$ je konstantní rekurzivní, protože uspokojuje ${ displaystyle s (n) = s (n- ell)}$ pro všechny ${ displaystyle n geq d}$ pro některé ${ displaystyle d}$ .

Polynomiální sekvence

Pro libovolný polynom s(n), posloupnost jeho hodnot je konstantní rekurzivní posloupnost. Pokud je stupeň polynomu dposloupnost splňuje opakování objednávky ${ displaystyle d + 1}$ , s koeficienty danými odpovídajícím prvkem binomická transformace.^[1] Prvních pár takových rovnic je

{ displaystyle s (n) = 1 cdot s (n-1)}

pro polynomial stupně 0 (tj. konstantní),

{ displaystyle s (n) = 2 cdot s (n-1) -1 cdot s (n-2)}

pro polynom 1 stupně nebo méně,

{ Displaystyle s (n) = 3 cdot s (n-1) -3 cdot s (n-2) +1 cdot s (n-3)}

pro polynom 2 stupně nebo méně a

{ Displaystyle s (n) = 4 cdot s (n-1) -6 cdot s (n-2) +4 cdot s (n-3) -1 cdot s (n-4)}

pro polynom stupně 3 nebo méně.

Posloupnost poslouchající příkaz -d rovnice se rovněž řídí všemi rovnicemi vyššího řádu. Tyto identity lze prokázat mnoha způsoby, mimo jiné prostřednictvím teorie konečné rozdíly.^{[Citace je zapotřebí ]} Každá jednotlivá rovnice může být také ověřena nahrazením stupněd polynomiální

{ displaystyle s (x) = součet _ {k = 0} ^ {d} a_ {k} x ^ {k},}

kde koeficienty ${ displaystyle a_ {k}}$ jsou symbolické. Jakákoli posloupnost ${ displaystyle d + 1}$ celočíselné, skutečné nebo komplexní hodnoty lze použít jako počáteční podmínky pro konstantní rekurzivní posloupnost pořadí ${ displaystyle d + 1}$ . Pokud počáteční podmínky leží na polynomu stupně ${ displaystyle d-1}$ nebo méně, pak se konstantní rekurzivní sekvence také řídí rovnicí nižšího řádu.

Výčet slov v běžném jazyce

Nechat ${ displaystyle L}$ být běžný jazyk a nechte ${ displaystyle s (n)}$ být počet slov délky ${ displaystyle n}$ v ${ displaystyle L}$ . Pak ${ displaystyle s (n) _ {n geq 0}}$ je konstantní rekurzivní.

Další příklady

Sekvence Jacobsthal čísla, Padovanská čísla, a Pell čísla jsou konstantní rekurzivní.

Charakterizace z hlediska exponenciálních polynomů

The charakteristický polynom (nebo „pomocný polynom“) rekurence je polynom

{ displaystyle x ^ {d} -c_ {1} x ^ {d-1} - tečky -c_ {d-1} x-c_ {d}}

jejichž koeficienty jsou stejné jako koeficienty opakování nth termín ${ displaystyle s (n)}$ konstantní rekurzivní sekvence lze zapsat z hlediska kořeny jeho charakteristického polynomu d kořeny ${ displaystyle r_ {1}, r_ {2}, tečky, r_ {d}}$ jsou všechny odlišné, pak nth termín posloupnosti je

{ displaystyle s (n) = k_ {1} r_ {1} ^ {n} + k_ {2} r_ {2} ^ {n} + tečky + k_ {d} r_ {d} ^ {n}}

kde koeficienty k_i jsou konstanty, které lze určit z počátečních podmínek.

Pro Fibonacciho sekvenci je charakteristický polynom ${ displaystyle x ^ {2} -x-1}$ , jehož kořeny ${ displaystyle phi = { frac {1 + { sqrt {5}}} {2}}}$ a ${ displaystyle { bar { phi}} = { frac {1 - { sqrt {5}}} {2}}}$ objevit v Binetův vzorec

{ displaystyle F_ {n} = { frac { phi ^ {n} - { bar { phi}} ^ {n}} { sqrt {5}}}.}

Obecněji, pokud kořen r charakteristického polynomu má multiplicitu m, pak termín ${ displaystyle r ^ {n}}$ se vynásobí stupněm ${ displaystyle (m-1)}$ polynom v n. To je, pojďme ${ displaystyle r_ {1}, tečky, r_ {e}}$ být zřetelnými kořeny charakteristického polynomu. Pak

{ displaystyle s (n) = k_ {1} (n) r_ {1} ^ {n} + k_ {2} (n) r_ {2} ^ {n} + tečky + k_ {e} (n) r_ {e} ^ {n}}

kde ${ displaystyle k_ {i} (n)}$ je polynom stupně ${ displaystyle m_ {i} -1}$ Například pokud jsou charakteristické polynomické faktory jako ${ displaystyle (x-r) ^ {3}}$ , se stejným kořenem r vyskytující se třikrát, pak nth termín je ve formě

{ displaystyle s (n) = (a + bn + cn ^ {2}) r ^ {n}.}

^[2]

Naopak, pokud existují polynomy ${ displaystyle k_ {i} (n)}$ takhle

{ displaystyle s (n) = k_ {1} (n) r_ {1} ^ {n} + k_ {2} (n) r_ {2} ^ {n} + tečky + k_ {e} (n) r_ {e} ^ {n},}

pak ${ displaystyle s (n) _ {n geq 0}}$ je konstantní rekurzivní.

Charakterizace z hlediska racionálních generujících funkcí

Sekvence je konstantní rekurzivní přesně tehdy, když je generující funkce

{ displaystyle sum _ {n geq 0} s (n) x ^ {n} = s (0) + s (1) x ^ {1} + s (2) x ^ {2} + s (3 ) x ^ {3} + cdots}

je racionální funkce. Jmenovatel je polynom získaný z pomocného polynomu obrácením pořadí koeficientů a čitatel je určen počátečními hodnotami posloupnosti.^[3]

Generující funkce Fibonacciho sekvence je

{ displaystyle { frac {x} {1-x-x ^ {2}}}.}

Obecně platí, že vynásobení generující funkce polynomem

{ displaystyle 1-c_ {1} x ^ {1} -c_ {2} x ^ {2} - tečky -c_ {d} x ^ {d}}

získá řadu

{ displaystyle left (s (0) + s (1) x ^ {1} + s (2) x ^ {2} + cdots right) left (1-c_ {1} x ^ {1} -c_ {2} x ^ {2} - dots -c_ {d} x ^ {d} doprava) = doleva (b_ {0} + b_ {1} x ^ {1} + b_ {2} x ^ {2} + cdots right),}

kde

{ displaystyle b_ {n} = s (n) -c_ {1} s (n-1) -c_ {2} s (n-2) - tečky -c_ {d} s (n-d).}

Li ${ displaystyle s (n)}$ uspokojuje relaci opakování

{ displaystyle s (n) = c_ {1} s (n-1) + c_ {2} s (n-2) + tečky + c_ {d} s (n-d),}

pak ${ displaystyle b_ {n} = 0}$ pro všechny ${ displaystyle n geq d}$ . Jinými slovy,

{ displaystyle left (s (0) + s (1) x ^ {1} + s (2) x ^ {2} + cdots right) left (1-c_ {1} x ^ {1} -c_ {2} x ^ {2} - dots -c_ {d} x ^ {d} doprava) = doleva (b_ {0} + b_ {1} x ^ {1} + b_ {2} x ^ {2} + dots + b_ {d-1} x ^ {d-1} right),}

takže získáme racionální funkci

{ displaystyle sum _ {n geq 0} s (n) x ^ {n} = { frac {b_ {0} + b_ {1} x ^ {1} + b_ {2} x ^ {2} + dots + b_ {d-1} x ^ {d-1}} {1-c_ {1} x ^ {1} -c_ {2} x ^ {2} - dots -c_ {d} x ^ {d}}}.}

Ve zvláštním případě uspokojivé periodické sekvence ${ displaystyle s (n) = s (n-d)}$ pro ${ displaystyle n geq d}$ , generující funkce je

{ displaystyle { begin {aligned} { frac {s (0) + s (1) x ^ {1} + dots + s (d-1) x ^ {d-1}} {1-x ^ {d}}} = & left (s (0) + s (1) x ^ {1} + dots + s (d-1) x ^ {d-1} right) + left (s ( 0) + s (1) x ^ {1} + dots + s (d-1) x ^ {d-1} right) x ^ {d} + {} & left (s (0) + s (1) x ^ {1} + dots + s (d-1) x ^ {d-1} vpravo) x ^ {2d} + cdots end {zarovnáno}}}

rozšířením geometrické řady.

The generující funkce katalánských čísel není racionální funkce, což znamená, že Katalánská čísla nevyhovují lineárnímu opakování s konstantními koeficienty.

Vlastnosti uzavření

Termické sčítání nebo násobení dvou konstantní rekurzivních sekvencí je opět konstantní rekurzivní. To vyplývá z charakterizace z hlediska exponenciálních polynomů.

The Cauchyho produkt dvou konstantních rekurzivních sekvencí je konstantní rekurzivní. To vyplývá z charakterizace z hlediska racionálních generujících funkcí.

Sekvence uspokojující nehomogenní opakování

Sekvence splňující nehomogenní lineární opakování s konstantními koeficienty je konstantní rekurzivní.

Důvodem je opakování

{ displaystyle s (n) = c_ {1} s (n-1) + c_ {2} s (n-2) + tečky + c_ {d} s (n-d) + c}

lze vyřešit pro ${ displaystyle c}$ získat

{ displaystyle c = s (n) -c_ {1} s (n-1) -c_ {2} s (n-2) - tečky -c_ {d} s (n-d).}

Dosazením do rovnice

{ displaystyle s (n + 1) = c_ {1} s (n) + c_ {2} s (n-1) + tečky + c_ {d} s (n + 1-d) + c}

ukázat to ${ displaystyle s (n)}$ uspokojuje homogenní opakování

{ displaystyle s (n + 1) = (c_ {1} +1) s (n) + (c_ {2} -c_ {1}) s (n-1) + tečky + (c_ {d} - c_ {d-1}) s (n + 1-d) -c_ {d} s (nd)}

řádu ${ displaystyle d + 1}$ .

Zobecnění

Přirozené zobecnění se získá uvolněním podmínky, že koeficienty rekurence jsou konstanty. Pokud je dovoleno, aby koeficienty byly polynomy, pak jeden získá holonomické sekvence.

A ${ displaystyle k}$ -pravidelná posloupnost uspokojuje lineární rekurence s konstantními koeficienty, ale rekurence mají jinou formu. Spíše než ${ displaystyle s (n)}$ je lineární kombinací ${ displaystyle s (m)}$ pro některá celá čísla ${ displaystyle m}$ které jsou blízké ${ displaystyle n}$ , každý termín ${ displaystyle s (n)}$ v ${ displaystyle k}$ -pravidelná sekvence je lineární kombinace ${ displaystyle s (m)}$ pro některá celá čísla ${ displaystyle m}$ jehož základna ${ displaystyle k}$ reprezentace jsou blízké reprezentaci ${ displaystyle n}$ . Konstantní rekurzivní sekvence lze považovat za ${ displaystyle 1}$ -pravidelné sekvence, kde reprezentace base-1 z ${ displaystyle n}$ skládá se z ${ displaystyle n}$ kopie číslice ${ displaystyle 1}$ .

Poznámky

^ Boyadzhiev, Boyad (2012). „Blízká setkání se Stirlingovými čísly druhého druhu“ (PDF). Matematika. Mag. 85: 252–266.
^ Greene, Daniel H .; Knuth, Donald E. (1982), „2.1.1 Konstantní koeficienty - A) Homogenní rovnice“, Matematika pro analýzu algoritmů (2. vyd.), Birkhäuser, str. 17.
^ Martino, Ivan; Martino, Luca (2013-11-14). Msgstr "O rozmanitosti lineárních opakování a numerických semigroupů". Semigroup Forum. 88 (3): 569–574. arXiv:1207.0111. doi:10.1007 / s00233-013-9551-2. ISSN 0037-1912.

Reference

Brousseau, Alfred (1971). Lineární rekurze a Fibonacciho sekvence. Sdružení Fibonacci.
Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2. vyd.). Addison-Wesley. ISBN 978-0-201-55802-9.

externí odkazy

„OEIS Index Rec“. OEIS index k několika tisícům příkladů lineárních opakování, seřazených podle pořadí (počet termínů) a podpisu (vektor hodnot konstantních koeficientů)

[1] Boyadzhiev, Boyad (2012). „Blízká setkání se Stirlingovými čísly druhého druhu“ (PDF). Matematika. Mag. 85: 252–266.

[2] Greene, Daniel H .; Knuth, Donald E. (1982), „2.1.1 Konstantní koeficienty - A) Homogenní rovnice“, Matematika pro analýzu algoritmů (2. vyd.), Birkhäuser, str. 17.

[3] Martino, Ivan; Martino, Luca (2013-11-14). Msgstr "O rozmanitosti lineárních opakování a numerických semigroupů". Semigroup Forum. 88 (3): 569–574. arXiv:1207.0111. doi:10.1007 / s00233-013-9551-2. ISSN 0037-1912.

[1]

[2]

[3]