this is the question
given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two? I need to include the number of ways for $n=1$ through $6$ as well.
My question : is step up two stairs and hop up two, is it the same thing? however, I tried to do the solution
$n=1$ stair No. of ways $ = 1 = f(2) $
$n= 2$ No. of ways $ = 2 = f(3) = f(2) + f(1) $
$n= 3$ No. of ways $ = 3 = f(4) = f(3) + f(2) $
$n= 4$ No. of ways $ = 5 = f(5) = f(4) + f(3) $
$n= 5$ No. of ways $ = 8 = f(6) = f(5) + f(4) $
$n= 6$ No. of ways $ = 13 =f(7) = f(6) + f(5) $
:
:
for $n$, No. of ways $ = f(n+1) $
because there is a hint saying I could use recursively defined.
Is there other way?
You have correctly observed your recursive pattern. Namely the Fibonacci Numbers defined by:
$$F(n+2)=F(n+1)+F(n),F(0)=1,F(1)=1$$ (Note different definitions define different start conditions, this is to fit into your situation)
Now it is possible to derive a formula who gives $F(n)$ only in terms of $n$ but the method is significantly harder than the recursive method above.
It is given by:
$$F(n)=\frac{\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n}{\sqrt5}$$
Note this one starts from 0,1 for the first two terms which is slightly different to your answer which has a zeroth term and starts 1,1.
Given that you only need to do up to $n=6$ this formula is a huge overkill and highly likely beyond what your teacher expected you to do.