For anybody unsure of how to prove this, a strong inductive proof follows easily.
Base: n=1 has one solution and n=2 has two solutions (2 single steps or a double step) which are Fib(1) and Fib(2), respectively.
Step: In order to get to step n+1, you must've originated from step n (and then single stepped) or step n-1 (and double stepped). Therefore summing all ways to get to n and n-1 will get you how many ways to get to n+1. Invoking the strong hypothesis, the number of ways to get to step n-1 is the Fib(n-1) and the number of ways to get to step n is Fib(n). Summing Fib(n) and Fib(n-1) gets you Fib(n+1) by the definition of the Fibonacci sequence.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Could use a proof that this indeed makes a Fibonacci sequence. Couting to 5 and concluding it must be that sequence is wrong. Just look at how many possible (named) sequences are there:
https://oeis.org/search?q=0%2C1%2C2%2C3%2C4%2C8&language=english&go=Search
Your input into that search bar is 0,1,2,3,4,8.
We're looking for 0,1,2,3, "5" ,8.
....
For anybody unsure of how to prove this, a strong inductive proof follows easily.
Base: n=1 has one solution and n=2 has two solutions (2 single steps or a double step) which are Fib(1) and Fib(2), respectively.
Step: In order to get to step n+1, you must've originated from step n (and then single stepped) or step n-1 (and double stepped). Therefore summing all ways to get to n and n-1 will get you how many ways to get to n+1. Invoking the strong hypothesis, the number of ways to get to step n-1 is the Fib(n-1) and the number of ways to get to step n is Fib(n). Summing Fib(n) and Fib(n-1) gets you Fib(n+1) by the definition of the Fibonacci sequence.