Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 1993. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 21)
Zay Béla: Egy rekurzív sorozatról
adódik. Összevetve ezeket a (7) egyenlőséggel, azt kapjuk, hogy vagy ami a teljes indukció gondolatmenete miatt bizonyítja az állítást 3. Lemma: A G k J(n) sorozat növekvő és szomszédos tagjainak a különbsége 0 vagy 1, azaz (8') G k,(n + l) = G k J(n) vagy (8") G ki t(n + l) = G k> l(n) + l minden n > 0 esetén. Bizonyítás: Ismét teljes indukcióval bizonyítunk. n - 0,1,..., t -1 esetén az (1) definíció szerint G k J(n) = n, így n = 0,1,..., t - 2 re a (8") teljesül. Szintén az (1) alapján G k l (t) = t - Gff (0) = t és G^r + l) = r + l-Gf;(l) = í, tehát n = t - l-re (8"), n = /-re pedig (8') áll fenn. Legyen n>t és tegyük fel, hogy minden /' természetes számra, amelyre 0<i <n, teljesül a 3. Lemma állítása, azaz illetve G k J(i + l) = G k J(i) + l egyike fennáll. így teljesülnek a 2. Lemma feltételei. Alkalmazzuk j ^k-r&K 2. Lemmát! Ha 33
