Ciąg Fibonacciego

[Swider]

Mam problem z takim zadaniem, nie wiem jak takie coś rozwiązać, proszę o pomoc.

Rozważmy ciąg okreslony rekurencyjnie: \(\displaystyle{ a_{1} = 1, a_{2} = 1, a_{n+2} = a_{n+1} + a_{n}}\)(ciag Fibonacciego).
Udowodnij, ze:
(a) \(\displaystyle{ 2 | a_{3n}, 3 | a_{4n}, 5 | a_{5n}}\)

b) \(\displaystyle{ \frac{1}{ \sqrt{5} }\left[ \left( \frac{1+ \sqrt{5} }{2} \right)^{n} - \left( \frac{1- \sqrt{5} }{2} \right)^{n} \right]}\)

[szw1710]

b) Zadanie tego typu robiono tu wielokrotnie. Chodzi o rekurencje liniowe. Można np. przez równanie charakterystyczne. Przeszukaj forum.

[Zordon]

a) znany fakt: \(\displaystyle{ nwd(a_k,a_n)=a_{nwd(k,n)}}\)
wystarczy teraz zauważyć, że np. \(\displaystyle{ 3=a_4}\)

[Ponewor]

b) można również dowieść przez indukcję