Page 46 - MATINF Nr. 7

46 N. St˘aniloiu

Propozit , ia 2. Cu notat , iile anterioare avem urm˘atoarea relat , ie de recurent , ˘a:

2
L = L 2 n−1 + L 2 n−3 + L 2 n−5 + L 2 n−6 pentru n ≥ 6 (2)
n
ˆ
Demonstrat¸ie. Intr-adev˘ar, num˘arul n-cuvintelor dublu legate care ˆıncep cu 0 este L 2 n−1 .
Num˘arul n-cuvintelor dublu legate care ˆıncep cu 1 ˆıl calcul˘am astfel: Un astfel de n-cuvˆant are
ˆın mod obligatoriu ˆın pozit , iile 2 s , i 3 cifra 1. Dac˘a complet˘am aceste cuvinte cu (n − 3)-cuvinte
dublu legate se obt , in n-cuvinte dublu legate. Deasemenea n-cuvinte dublu legate se mai pot
obt , ine s , i dac˘a complet˘am pozit , iile 4 s , i 5 cu cifrele 1 s , i respectiv 0 s , i ˆın rest (n − 5)-cuvinte
dublu legate, sau dac˘a pozit , iile 4, 5 s , i 6 se completeaz˘a cu cifrele 1, 1 s , i respectiv 0 iar ˆın rest
cu (n − 6)-cuvinte dublu legate. Prin urmare num˘arul n-cuvintelor dublu legate care ˆıncep cu 1
si
este L 2 n−3 + L 2 n−5 + L 2 n−6 , deci relat , ia din propozit , ia 2 este acum justificat˘a.
2
Folosind calculatorul am creat o a doua funct , ie care determin˘a num˘arul L pentru 0 ≤ k ≤ 14
k
obt , inˆand urm˘atoarele rezultate:

k L 2
k
0 1
1 1
2 1
3 2
4 4
5 7
6 11
7 17
8 27
9 44
10 72
11 117
12 189
13 305
14 493

Observat ,ia 3. Relat , iile de recurent , ˘a deduse ˆın cele dou˘a propozit , ii permit determinarea unei
2
1
formule de calculpentru L , respective L .
n
n
Se observ˘a c˘a numerele obt , inute cu ajutorul calculatorului verific˘a relat , ia de recurent , ˘a.
Folosind relat , iile de recurent , ˘a deduse s , i un program corespunz˘ator pe calculator putem
1
2
calcula L s , i L pentru valori suficient de mari ale lui n.
n n
∗
Pentru calculul n-cuvintelor legate de ordin k, k ∈ N vom demonstra urm˘atoarea:
Propozit , ia 3. Cu notat , iile anterioare avem urm˘atoarea relat , ie de recurent , ˘a:
k
L = L k + L k + L k + L k + . . . + L k pentru n ≥ 2k + 2.
n n−1 n−k−1 n−k−3 n−k−4 n−2k−2
ˆ
Demonstrat¸ie. Intr-adev˘ar, num˘arul n-cuvintelor legate de ordin k care ˆıncep cu 0 este L k n−1 .
Num˘arul n-cuvintelor legate de ordin k care ˆıncep cu 1 ˆıl calcul˘am astfel: Un astfel den-cuvˆant
are ˆın mod obligatoriu ˆın toate pozit , iile ˆıncepˆand de la pozit , ia 2 s , i pˆan˘a la pozit , ia (k + 1) cifra
1. Dac˘a complet˘am aceste cuvinte cu (n − k − 1)-cuvinte legate de ordin kse obt , in n-cuvinte