Numere Fibonacci

Problema iepurilor

Fie data o pereche de iepuri. Se stie ca fiecare pereche de iepuri produce in fiecare luna o noua pereche de iepuri, care la randul sau devine productiva la varsta de o luna. Sa se determine cate perechi de iepuri vor fi dupa n luni.

Initial vom remarca istoria acestei probleme si apoi solutia ei, precum si alte probleme ce tin de ea.

Vorbind de matematica din antichitate fiecare ar numi asa matematicieini ca Euclide, Pytagoras, Heron s.a. Unul dintre cei mai ilustri matematicieni a Evului Mediu, de rand cu Viete, ar fi Leonardo din Pisa, cunoscut sub numele Fibonacci (prescurtare de la filus Bonacci, adica fiul lui Bonacci).

Fibonacci, nascut in Italia, in 1175, a fost educat in Nordul Africii, unde tatal sau detine un post diplomatic. Revenind in Italia, in 1202 publica un tratat de matematica cu titlul �Liber abaci�. Acest tratat contine aproape toata informatia acelui timp, referitoare la aritmetica si algebra, si care a avut un rol important pe parcursul urmatoarelor secole in dezvoltarea matematicii in Europa. In particular, in baza acestui tratat, europenii au luat cunostinta de scrierea arabica a numerelor, adica de sistemul de numeratie pozitional arab. La fel, in 1220 publica �Practica geometrica�, in 1225 �Liber quadratorum�. Tratatul �Liber abaci� a fost reeditat in 1228. Una din problemele discutate in �Liber abaci� este anume �problema iepurilor�, (p. 123-124 in editia anului 1228) prezentata la inceputul acestui material.

Sa trecem la rezolvarea acestei probleme.

Fie f_{n} numarul de perechi de iepuri dupa n luni. Numarul de perechi de iepuri dupa n + 1, notat prin f_{n+1}, va fi numarul de perechi la luna n, adica f_{n}, plus numarul de iepuri nou-nascuti. Cum iepuri se nasc din pereche de iepuri cu varsta mai mare de o luna, iepuri nou-nascuti vor fi f_{n−1} perechi.

Prin urmare se obtine relatia

f_{n+1} = f_{n} + f_{n−1}.  (1)

In plus,

f_{0} = 0 si f_{1} = 1.  (2)

0 Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md

Asadar am obtinut un sir numeric definit in mod recurent. Scriind termenii acestui sir, determinam

0, 1, 1, 2, 3, 5, 8, …  (3)

numit sirul Fibonacci. Fiecare termen al sirului, incepand cu al treilea, este egal cu suma precedentilor doi termeni. Primii doi termeni se considera fiind dati, f_{0} = 0, f_{1} = 1.

Astfel �problema iepurilor� s-a redus la rezolvarea ecuatiei functionale (1), adica la determinarea termenului general f_{n} a sirului, care verifica relatia (1) in conditiile (2).

Presupunem ca sirul f_{n} are forma

f_{n} = λ^{n},  (4)

unde λ un parametru real.

Substituim f_{n} in (1), si obtinem

λ^{n+1} = λ^{n} + λ^{n−1},

sau echivalent

λ^{n−1}(λ^{2} − λ − 1) = 0.

Cum f_{n} ≠ 0 (∀n ∈ N^{∗}), ultima egalitate devine

λ^{2} − λ − 1,  (5)

care reprezinta o ecuatie patrata in raport cu parametrul real λ. Din (5) deducem

λ_{1} = \frac{1 + \sqrt{5}}{2},

λ_{2} = \frac{1 − \sqrt{5}}{2}.

Asadar, sirurile

f_{n} = (\frac{1 + \sqrt{5}}{2})^{n} , f_{n} = (\frac{1 − \sqrt{5}}{2})^{n} ,

verifica egalitatea (1). De aici, conchidem ca ecuatia (1) poseda mai multe solutii. In general exista o infinitate de siruri care verifica (1). Usor de observat ca sirul de forma

f_{n} = c_{1} (\frac{1 + \sqrt{5}}{2})^{n} + c_{2} (\frac{1 − \sqrt{5}}{2})^{n} ,  (6)

0 Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md

unde c_{1}, c_{2} - constante reale fixate, la fel verifica (1). Mai mult, se poate arata ca orice sir ce verifica egalitatea (1) are forma (6). Avand alte scopuri, nu vom demonstra acest fapt in cadrul acestei lucrari. Pentru cei interesanti in teoria generala de solutionare a ecuatiilor de forma (1), numite ecuatii cu diferente finite, recomandam sa consulte [1]-[4].

Revenind la sirul Fibonacci, constatam ca acest sir se determina univoc, si unicitatea este dictata de primii doi termeni, adica de conditiile initiale (2). Sunstituind n = 0 si n = 1 in (6), se obtine sistemul liniar

\{ \begin{matrix}c_{1} + c_{2} = 0, \\ c_{1} · \frac{1 + \sqrt{5}}{2} + c_{2} · \frac{1 − \sqrt{5}}{2} = 1, \end{matrix}

cu solutia c_{1} = \frac{1}{\sqrt{5}}, c_{2} = −\frac{1}{\sqrt{5}}.

In final, termenul de rang n al sirului Fibonacci are forma

f_{n} = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n} (n ∈ N).  (7)

Proprietati ale sirului Fibonacci.

1^{∘}.

f_{1} + f_{2} + … + f_{n} = f_{n+2} − 1.  (8)

Demonstratie.

f_{1} = f_{3} − f_{2}
f_{2} = f_{4} − f_{3}
…
f_{n−1} = f_{n+1} − f_{n}
f_{n} = f_{n+2} − f_{n+1}.

Sumand parte cu parte egalitatile anterioare se obtine

f_{1} + f_{2} + … + f_{n} = f_{n+2} − f_{2},

si cum f_{2} = 1 se obtine egalitatea (8).

0 Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md

2^{∘}. f_{1} + f_{3} + f_{5} + … + f_{2n−1} = f_{2n}. 3^{∘}. f_{2} + f_{4} + … + f_{2n} = f_{2n+1} − 1. Proprietatile 2^{∘} − 3^{∘} se demonstreaza similar cu 1^{∘}. 4^{∘}.

f_{1}^{2} + f_{2}^{2} + … + f_{n}^{2} = f_{n} · f_{n+1}.  (9)

Demonstratie. Se observa cu usurinta ca are loc relatia

f_{n} · f_{n+1} − f_{n−1}f_{n} = f_{n}(f_{n+1} − f_{n−1}) = f_{n}^{2} (n ∈ N).

Din aceasta relatie, deducem egalitatile

f_{1}^{2} = f_{1} · f_{2},
f_{2}^{2} = f_{2} · f_{3} − f_{1} · f_{2},
f_{3}^{2} = f_{3} · f_{4} − f_{2} · f_{3},
…
f_{n}^{2} = f_{n} · f_{n+1} − f_{n−1} · f_{n}.

Sumand parte cu parte egalitatile precedente se obtine egalitatea (9).

5^{∘}. Sa se arate ca

f_{n+m} = f_{n−1} · f_{m} + f_{n} · f_{m+1},  (10)

unde f_{n} desemneaza termenul de rang n al sirului Fibonacci.

Demonstratie. Desigur, cunoscand forma generala a termenului f_{n} (a se vedea (9) se poate de substituit in (10) si de aratat ca are loc egalitatea. Cu toate acestea, vom demonstra (10) utilizand metoda inductiei matematice. Vom face inductia dupa m ∈ N.

Pentru m = 1, egalitatea (10) devine

f_{n+1} = f_{n−1} · f_{1} + f_{n} · f_{2},

care este evidenta. Pentru m = 2 formula (10) la fel este evidenta. Intr-adevar,

f_{n+2} = f_{n−1}f_{2} + f_{n}f_{3} = f_{n−1} + 2f_{n} = f_{n−1} + f_{n} + f_{n} = f_{n+1} + f_{n}.

Astfel baza inductiei este verificata (m = 1; m = 2). Fie (10) este adevarata pentru m = k si m = k + 1 si vom demonstra ca este adevarata si pentru m = k + 2.

0 Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md

Asadar, fie sunt adevarate egalitatile

\begin{matrix}f_{n+k} = f_{n−1}f_{k} + f_{n}f_{k+1}, \\ f_{n+k+1} = f_{n−1}f_{k+1} + f_{n}f_{k+2}. \end{matrix}

Sumand parte cu parte ultimele egalitati, se obtine

f_{n+k+2} = f_{n−1} · f_{k+2} + f_{n} · f_{k+3},

care si reprezinta egalitatea (10) pentru m = k + 2.

6^{∘}. f_{2n} = f_{n−1}f_{n} + f_{n} · f_{n+1}. Demonstratia rezulta din (10) punand m = n. 7^{∘}. Termenul f_{2n} se diivide prin f_{n}. Demonstratie. Din 6^{∘} rezulta

f_{2n} = f_{n}(f_{n−1} + f_{n+1}),

de unde rezulta ca f_{2n}⋮f_{n}.

8^{∘}. f_{2n} = f_{n+1}^{2} − f_{n−1}^{2}. 9^{∘}. f_{3n} = f_{n+1}^{3} + f_{n}^{3} − f_{n−1}^{3}. Proprietatile 8^{∘} −9^{∘} fiind consecinte directe din 6^{∘}, raman sa fie demonstrate desinestatator. 10^{∘}.

f_{n}^{2} = f_{n−1}f_{n+1} + (−1)^{n+1}  (11)

Demonstratie. Vom demonstra egalitatea (11) prin inductie dupa n. Pentru n = 2 egalitatea (11) devine

f_{2}^{2} = f_{1} · f_{3} − 1,

care este adevarata.

Fie (11) este adevarata pentru n si vom demonstra ca este adevarata si pentru n+1. Asadar fie are loc egalitatea

f_{n}^{2} = f_{n−1} · f_{n+1} + (−1)^{n+1}.

Adunam la ambele parti a ultimei egalitati f_{n} · f_{n+1}. Ca rezultat se obtine

f_{n}^{2} + f_{n} · f_{n+1} = f_{n−1} · f_{n+1} + f_{n} · f_{n+1} + (−1)^{n+1},

0 Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md

sau echivalent

f_{n}(f_{n} + f_{n+1}) = f_{n+1}(f_{n−1} + f_{n}) + (−1)^{n+1},

si cum f_{n+2} = f_{n} + f_{n+1} (a se vedea definitia sirului Fibonacci) deducem

f_{n}f_{n+2} = f_{n+1}^{2} + (−1)^{n+1},

sau

f_{n+1}^{2} = f_{n} · f_{n+2} + (−1)^{n+2}.

Deci (11) este adevarata si pentru n + 1.

11. Sa se arate ca daca n este divizibil prin m atunci f_{n} este divizibil prin f_{m}.

Demonstratie. Fie n⋮m, adica n = mk. Vom demonstra proprietatea (11) prin inductie dupa k. Pentru k = 1, n = m, si deci, f_{n} evident este divizibil prin f_{m}. Presupunem ca f_{mk} este divizibil prin f_{m}. Sa examinam f_{m(k+1)}. Cum f_{m(k+1)} = f_{mk+m} si utilizand egalitatea (10) se obtine

f_{m(k+1)}^{2} = f_{mk−1}f_{m} + f_{mk} · f_{m+1}.

Primul termen al sumei din dreapta evident este divizibil prin f_{m}. Termenul al doilea este divizibil prin f_{m} conform presupunerii inductive. Prin urmare suma acestor termeni este divizibila prin f_{m}, si deci, f_{m(k+1)}⋮f_{m}. Proprietatea 11^{∘} este demonstrata.

Alte proprietati ce tin de divizibilitate, geometrie, teoria algoritmilor etc. pot fi consultate in Bibliografia indicata la sfarsitul acestei lucrari.

Exercitii pentru lucrul individual.

1. Fie (f_{n})_{n∈N} sirul Fibonacci. Sa se demonstreze ca

(a) f_{1}f_{2} + f_{2}f_{3} + f_{3}f_{4} + … + f_{2n−1} · f_{2n} = f_{2n}^{2}

(b) f_{1}f_{2} + f_{2}f_{3} + … + f_{2n}f_{2n+1} = f_{2n+1}^{2} − 1

(c) nf_{1} + (n − 1)f_{2} + … + 2f_{n−1} + f_{n} = f_{n+4} − (n + 3)

(d) f_{1} + 2f_{2} + 3f_{3} + … + nf_{n} = nf_{n+2} − f_{n+3} + 2 2. Sa se arate ca pentru orice m ∈ N, printre primele m^{2} − 1 numere Fibonacci exista unul

0 Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md

divizibil prin m.

3. Sa se demonstreze ca:

(a) Numarul Fibonacci f_{n} este par daca si numai daca n este divizibil prin 3;

(b) Numarul Fibonacci f_{n} este divizibil prin 3 daca si numai daca rangul lui este divizibil prin 4;

(c) f_{n}⋮4 daca si numai daca n⋮6;

(d) f_{n}⋮5 daca si numai daca n⋮5;

(e) f_{n}⋮7 daca si numai daca n⋮8;

(f) f_{n}⋮16 daca si numai daca n⋮12.

Bibliografie

1. A.I.Hincin, Fractii continue, Ed. Tehnica, Bucuresti 1960.

2. I.Munteanu, D.Popa, Metoda sirurilor recurente, Editura GIL, ZALAU.

3. Н.М.Вороб�ев, Числа Фибоначи, Москва, Наука, 1992.

4. А.У.Маркушевич, Возвратные последовательности, Москва, Наука, 1975.

0 Copyright\begin{matrix}c \\ ◯ \end{matrix}1999 ONG TCV Scoala Virtuala a Tanarului Matematician http://math.ournet.md