Ilość sposobów eqq: Na ile sposobów można pokonać drogę złożoną z n schodków, gdy za każdym razem przeskakujemy jeden stopień lub dwa? Rozwiązując to zadanie na dwa sposoby wykaż, że zachodzi tożsamość

	n 0		n−1 1		n−2 2
Fn+1=		+		+		+...

Nie mam pojęcia jak to zrobić, w ogóle nie dostrzegam tu związku z ciągiem Fibonacciego

Adamm: 1. wykonujemy 0 podwójnych jest tylko 1 sposób 2. wykonujemy 1 podwójny

	n−1 1
jest		sposobów, bo z n−1 skoków wybieramy który jest podwójny

3. wykonujemy 2 podwójne itd.

	n 0		n−1 1		n−[n/2] [n/2]
stąd wzór		+		+...+

Adamm: możemy też zrobić tak albo przeskakujemy n−1 schodków, i potem skok o jeden albo n−2, i potem skok o dwa mamy rekurencję a_n=a_n−1+a_n−2 trzeba wykazać że to w jakiś sposób zależy od ciągu Fibonacciego, sprawdzając pierwsze wyrazy