Sabit özyinelemeli dizi - Constant-recursive sequence

Gelen matematik , bir sabit yinelemeli dizisi ya da Cı-sonlu dizisi doğrusal tatmin edici bir sekans nüks sabit katsayılar ile.

Tanım

Sabit katsayılı bir d dereceli homojen doğrusal yineleme , formun bir denklemidir.

${\displaystyle s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(nd),}$

burada d katsayıları sabittir. ${\displaystyle c_{1},c_{2},\dots ,c_{d}}$

Bir dizi , herkes için karşıladığı sabit katsayıları olan bir d dereceli homojen doğrusal yineleme varsa, sabit özyinelemeli bir dizidir . ${\görüntüleme stili s(0),s(1),s(2),\noktalar }$${\görüntüleme stili n\geq d}$

Eşdeğer olarak, diziler kümesi ise sabit özyinelemelidir. ${\displaystyle s(n)_{n\geq 0}}$

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

boyutu sonlu olan bir vektör uzayında bulunur .

Örnekler

Fibonacci Dizisi

Fibonacci sayılarının 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... dizisi yinelemeyi karşılar

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

ile başlangıç koşulları

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1.}$

Açıkça, yineleme değerleri verir

${\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}$

vb.

Lucas dizileri

Sekansı 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... (dizi A000032 içinde OEIS arasında) Lucas sayıları tatmin Fibonacci dizisi olarak, fakat başlangıç aynı nüks koşullar

${\görüntüleme stili L_{0}=2}$

${\görüntüleme stili L_{1}=1.}$

Daha genel olarak, her Lucas dizisi sabit özyinelemeli bir dizidir.

geometrik diziler

Geometrik dizi bu tatmin nüks için, sabit yinelemeli olduğu tüm . ${\displaystyle a,ar,ar^{2},\dots }$${\görüntüleme stili s(n)=rs(n-1)}$${\displaystyle n\geq 1}$

Sonunda periyodik diziler

Sonunda periyot uzunluğu ile periyodik olan bir dizi, bazıları için herkesi tatmin ettiğinden, sabit özyinelemelidir . ${\görüntüleme stili\el }$${\görüntüleme stili s(n)=s(n-\el )}$${\görüntüleme stili n\geq d}$${\görüntüleme stili d}$

polinom dizileri

Herhangi bir polinom s ( n ) için, değerlerinin dizisi sabit özyinelemeli bir dizidir. Polinomun derecesi d ise, dizi , binom dönüşümünün karşılık gelen elemanı tarafından verilen katsayılarla, bir sıra tekrarını sağlar . Bu tür ilk birkaç denklem ${\ Displaystyle d+1}$

${\displaystyle s(n)=1\cdot s(n-1)}$ 0 dereceli (yani sabit) bir polinom için,

${\displaystyle s(n)=2\cdot s(n-1)-1\cdot s(n-2)}$ derece 1 veya daha az polinom için,

${\displaystyle s(n)=3\cdot s(n-1)-3\cdot s(n-2)+1\cdot s(n-3)}$ derece 2 veya daha az polinom için ve

${\displaystyle s(n)=4\cdot s(n-1)-6\cdot s(n-2)+4\cdot s(n-3)-1\cdot s(n-4)}$ derece 3 veya daha az polinom için.

d mertebesinden denkleme uyan bir dizi aynı zamanda tüm yüksek mertebeden denklemlere de uyar. Bu kimlikler, sonlu farklar teorisi de dahil olmak üzere çeşitli yollarla kanıtlanabilir . Her bir denklem, derece- d polinomunun yerine konarak da doğrulanabilir.

${\displaystyle s(x)=\sum _{k=0}^{d}a_{k}x^{k},}$

katsayıların sembolik olduğu yer. Herhangi bir tamsayı, gerçek veya karmaşık değerler dizisi, sabit özyinelemeli bir düzen dizisi için başlangıç ​​koşulları olarak kullanılabilir . Başlangıç ​​koşulları derece veya daha düşük bir polinom üzerinde bulunuyorsa , sabit özyinelemeli dizi ayrıca daha düşük dereceli bir denkleme uyar. ${\ Displaystyle a_{k}}$${\ Displaystyle d+1}$${\ Displaystyle d+1}$${\görüntüleme stili d-1}$

Normal bir dilde kelimelerin numaralandırılması

Izin bir olmak düzenli dil ve izin uzunlukta kelime sayısı olmak içinde . Sonra sürekli özyinelemeli. ${\görüntüleme stili L}$${\görüntüleme stili s(n)}$${\görüntüleme stili n}$${\görüntüleme stili L}$${\displaystyle s(n)_{n\geq 0}}$

Diğer örnekler

Jacobsthal sayıları , Padovan sayıları ve Pell sayılarının dizileri sabit özyinelemelidir.

Üstel polinomlar açısından karakterizasyon

Karakteristik polinom nüks (veya "yardımcı polinom") polinom

${\displaystyle x^{d}-c_{1}x^{d-1}-\dots -c_{d-1}x-c_{d}}$

katsayıları yinelemeninkilerle aynıdır. N terimi inci sabit yinelemeli dizisinin açısından yazılabilir kökleri karakteristik polinomu. Eğer d kökleri olan tüm farklı, daha sonra n- dizisinin inci terimdir ${\görüntüleme stili s(n)}$${\displaystyle r_{1},r_{2},\dots ,r_{d}}$

${\displaystyle s(n)=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\dots +k_{d}r_{d}^{n}}$

burada k _i katsayıları , başlangıç ​​koşullarından belirlenebilen sabitlerdir.

Fibonacci dizisi için, kökleri ve Binet formülünde görünen karakteristik polinomdur.${\displaystyle x^{2}-x-1}$${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}}$${\displaystyle {\bar {\phi }}={\frac {1-{\sqrt {5}}}{2}}}$

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

Daha genel olarak, karakteristik polinomun bir r kökü m çokluğuna sahipse, terim n cinsinden bir derece- polinom ile çarpılır . Yani, karakteristik polinomun farklı kökleri olsun . Sonra ${\görüntüleme stili r^{n}}$${\görüntüleme stili (m-1)}$${\displaystyle r_{1},\dots ,r_{e}}$

${\displaystyle s(n)=k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\dots +k_{e}(n) r_{e}^{n}}$

derece polinomu nerede . Gibi karakteristik polinom faktörler Örneğin, aynı kök ile, r üç kez ortaya çıkan, daha sonra n- inci terimi formda olan ${\görüntüleme stili k_{i}(n)}$${\displaystyle m_{i}-1}$${\görüntüleme stili (xr)^{3}}$

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

Tersine, eğer böyle polinomlar varsa , ${\görüntüleme stili k_{i}(n)}$

${\displaystyle s(n)=k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\dots +k_{e}(n) r_{e}^{n},}$

o zaman sabit özyinelemeli. ${\displaystyle s(n)_{n\geq 0}}$

Rasyonel üretici fonksiyonlar açısından karakterizasyon

Bir dizi, tam olarak üretme işlevi olduğunda sabit özyinelemelidir

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

Bir olan rasyonel fonksiyon . Payda, yardımcı polinomdan katsayıların sırası ters çevrilerek elde edilen polinomdur ve pay, dizinin başlangıç ​​değerleri ile belirlenir.

Fibonacci dizisinin üretici fonksiyonu,

${\displaystyle {\frac {x}{1-xx^{2}}}.}$

Genel olarak, bir üretim fonksiyonunu polinomla çarpmak

${\displaystyle 1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}$

bir dizi verir

${\displaystyle \left(s(0)+s(1)x^{1}+s(2)x^{2}+\cdots \sağ)\left(1-c_{1}x^{1} -c_{2}x^{2}-\dots -c_{d}x^{d}\sağ)=\left(b_{0}+b_{1}x^{1}+b_{2}x ^{2}+\cdots \sağ),}$

nerede

${\displaystyle b_{n}=s(n)-c_{1}s(n-1)-c_{2}s(n-2)-\dots -c_{d}s(nd).}$

Eğer yineleme ilişkisini sağlıyorsa ${\görüntüleme stili s(n)}$

${\displaystyle s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(nd),}$

sonra hepsi için . Diğer bir deyişle, ${\displaystyle b_{n}=0}$${\görüntüleme stili n\geq d}$

${\displaystyle \left(s(0)+s(1)x^{1}+s(2)x^{2}+\cdots \sağ)\left(1-c_{1}x^{1} -c_{2}x^{2}-\dots -c_{d}x^{d}\sağ)=\left(b_{0}+b_{1}x^{1}+b_{2}x ^{2}+\dots +b_{d-1}x^{d-1}\sağ),}$

böylece rasyonel fonksiyonu elde ederiz

${\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}}}.}$

için sağlayan periyodik bir dizinin özel durumunda , üreten fonksiyon şudur: ${\görüntüleme stili s(n)=s(nd)}$${\görüntüleme stili n\geq d}$

${\displaystyle {\begin{hizalanmış}{\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}\sağ)+\left(s( 0)+s(1)x^{1}+\dots +s(d-1)x^{d-1}\sağ)x^{d}+{}\\&\left(s(0) +s(1)x^{1}+\dots +s(d-1)x^{d-1}\sağ)x^{2d}+\cdots \end{hizalı}}}$

geometrik seriyi genişleterek

Katalanca numaralarının üretici fonksiyon anlamına gelir rasyonel işlevi değil, Katalanca numaraları sabit katsayılar ile bir lineer nüks karşılamamaktadır.

Kapatma özellikleri

İki sabit özyinelemeli dizinin terimsel olarak eklenmesi veya çarpımı yine sabit özyinelemelidir. Bu, üstel polinomlar cinsinden karakterizasyondan kaynaklanmaktadır.

Cauchy ürün iki sabit yinelemeli dizilerin sabit özyinelemeli. Bu, rasyonel üretici fonksiyonlar açısından karakterizasyondan kaynaklanmaktadır.

Homojen olmayan yinelemeleri karşılayan diziler

Sabit katsayılı homojen olmayan bir doğrusal yineleme sağlayan bir dizi, sabit özyinelemelidir.

Bunun nedeni nüks

${\displaystyle s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(nd)+c}$

elde etmek için çözülebilir${\görüntüleme stili c}$

${\displaystyle c=s(n)-c_{1}s(n-1)-c_{2}s(n-2)-\dots -c_{d}s(nd).}$

Bunu denklemde yerine koyarsak

${\displaystyle s(n+1)=c_{1}s(n)+c_{2}s(n-1)+\dots +c_{d}s(n+1-d)+c}$

homojen yinelemeyi sağladığını gösterir${\görüntüleme stili s(n)}$

${\displaystyle s(n+1)=(c_{1}+1)s(n)+(c_{2}-c_{1})s(n-1)+\dots +(c_{d}- c_{d-1})s(n+1-d)-c_{d}s(nd)}$

sipariş . ${\ Displaystyle d+1}$

genellemeler

Yineleme katsayılarının sabit olduğu koşulu gevşetilerek doğal bir genelleme elde edilir. Katsayıların polinom olmasına izin verilirse, holonomik diziler elde edilir .

Bir -düzenli dizi , sabit katsayılı doğrusal yinelemeleri karşılar, ancak yinelemeler farklı bir biçim alır. 'ye yakın olan bazı tam sayıların doğrusal bir birleşimi olmak yerine , -düzenli bir dizideki her terim , taban temsilleri 'ye yakın olan bazı tam sayıların doğrusal bir birleşimidir . Sabit yinelemeli dizileri düşünülebilir -Normal dizileri, baz-1 gösterimi arasında oluşur basamağının kopyaları . ${\görüntüleme stili k}$${\görüntüleme stili s(n)}$${\görüntüleme stili s(m)}$${\görüntüleme stili m}$${\görüntüleme stili n}$${\görüntüleme stili s(n)}$${\görüntüleme stili k}$${\görüntüleme stili s(m)}$${\görüntüleme stili m}$${\görüntüleme stili k}$${\görüntüleme stili n}$${\görüntüleme stili 1}$${\görüntüleme stili n}$${\görüntüleme stili n}$${\görüntüleme stili 1}$

Notlar

Referanslar

• Brousseau, Alfred (1971). Doğrusal Özyineleme ve Fibonacci Dizileri . Fibonacci Derneği.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Ören (1994). Somut Matematik: Bilgisayar Bilimi Vakfı (2 ed.). Addison-Wesley. ISBN'si 978-0-201-55802-9.

Ayrıca bakınız

• tamamlayıcı matris

Dış bağlantılar

• "OEIS Dizin Kaydı" . Sıraya (terim sayısı) ve imzaya (sabit katsayıların değerlerinin vektörü) göre sıralanmış birkaç bin doğrusal yineleme örneğine OEIS endeksi