3-Laboratoriyalıq jumıs. Tyuring mashinasın jasaw. Jumıstıń maqseti

Teorema 1. (Sızıqlı birdey bolmaǵan rekkurent qatnaslardıń sheshiminiń dúzilisi haqqında (1)). Meyli  bir tegis bolmaǵan rekkurent qatnaslarınıń(2),  - qálegen sızıqlı birdey rekkurent qatnaslarınıń ulıwma sheshimi (1) bolsın. Onda  - sızıqlı birdey bolmaǵan rekkurent qatnaslarınıń ulıwma sheshimi (1).
Teorema 2. (Sızıqlı birdey rekkurent qatnaslarınıń ulıwma sheshimi dúzilisi haqqında (2)). Eger kóbeymeniń  - xarakteristikalıq teńlemesiniń (3) haqıyqıy koreni bolsa , (2) sızıqlı birdey rekkurent qatnaslarınıń ulıwmalıq sheshimi formula menen esaplanadı, bul jerde  - kóbeytilgen dáreje  N ózgeriwshisindegi,  . Koeffitsientler  rekkurent qatnaslarınıń aldıńǵı mánislerinen anıqlanadı.
(2) Rekkurent qatnaslarınıń ulıwma sheshimi de hám (3) teńlemeniń haqıyqıy korenleri hám  kóriniske iye
, egerde  ,
, egerde  = .
Mısalı. Fibonachchi sanlarınıń izbe-izligin esaplaw ushın Bine formulasın alamız.
Sheshiliwi.  , 
- barlıq koeffitsientler menen sızıqlı birdey rekkurent qatnası  , baslanǵısh mánisleri  ,  .
Xarakteristikalıq teńlemeni dúzemiz hám xarakterli nomerlerdi tabıń и  . Xarakterli teńleme kóbeymeniń 1 diń eki túrli korenine iye, bul degenimiz,  . Keyin ulıwma sheshim , bul jerde  hám  qálegen birdeylikler ( ,  ). Biz belgilengen mánislerden paydalanamız  , eki belgisiz bolǵan eki teńlemeler sistemasın dúziń:

Sistemanıń sheshimi jup san hám  . Solay etip,  .
Alınǵan formula Bine formulası dep ataladı hám Fibonachchi izbe-izliginiń mánislerin, izbe-izliktiń aldıńǵı aǵzalarınan tısqarı, tek olardıń sanı boyınsha esaplaw ushın isletiledi.
Esletpe. Kóbinese izbe-izlik kórip shıǵıladı. .
Mısalı, Fibonachchi sanlarınıń izbe-izligi ushın 0, 1, 1, 2, 3, 5, … rekkurent qatnası tómendegishe jazıladı  ,  .