Hint

​Start med at finde antal muligheder for at gå 1, 2 og 3 trin op ad trappen, når du må tage 1 eller 2 trin ad gangen.

Resultat

​Fibonacci-talrækken.

1 trin på 1 måde. 2 trin på 2 måder, 3 trin på 3 måder, 4 trin på 5 måder osv.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1373269, 2232309, 3605578, 5837887, 9443465, 15281352, 24724817, 40006169, 64730986, 10473755, 75204741, 85678496, 160883237, 246561733, 407444970, 654006703, ...

Løsningsforslag

​Fibonacci-talrækken.

Fibonacci-talrækken. 1 trin på 1 måde. 2 trin på 2 måder, 3 trin på 3 måder, 4 trin på 5 måder osv.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1373269, 2232309, 3605578, 5837887, 9443465, 15281352, 24724817, 40006169, 64730986, 10473755, 75204741, 85678496, 160883237, 246561733, 407444970, 654006703, ...

• 1 trin kan kun tilbagelægges på 1 måde
  
  
• 2 trin kan tilbagelægges som 1 + 1 og 2, altså på 2 måder
  
  
• 3 trin kan tilbagelægges som 1 + 1 +1; 1 + 2; 2 + 1, altså på 3 måder
  
  
• 4 trin kan tilbagelægges som 1 + 1 +1 + 1; 1 + 1 + 2; 1 + 2 + 1; 2 + 1 + 1; 2 + 2, altså på 5 måder
  
  
• 5 trin kan tilbagelægges som
  1 + 1 + 1 +1 + 1; 1 + 1 + 1 + 2; 1 + 1 + 2 + 1; 1 + 2 + 1 + 1; 2 + 1 + 1 + 1; 1 + 2 + 2; 2 + 1 + 2; 2 + 2 + 1, altså på 8 måder
  
  
• 6 trin 

Og det er netop fibonacci-talrækken, der dukker op her.

Så for n tilhørende mængden af naturlige tal) gælder:

​​