CareerCup

I think fib is correct. This is the simple observation:
Let f(i) be the number of ways that can be taken to reach step i.
f(2) = 1
f(i) = f(i-1) + f(i-2)
That is, if we assume that we are about to take the last step for reaching i, either we are at step i-1 or at step i-2. Coming to step (i-1) we could have taken f(i-1) ways, for coming to i-2, we could have taken f(i-2) different ways.

Hi Guys, can you please help me understand how were u able to relate this problem to fibanocci series..

Now, the number of ways to reach step 2 from 1 is 1 and to reach every step from 3 to n, there are 2 ways, either from n-2 nd step or n-1st step.
Therefore, there are 2^(n-2)ways for steps 3 to n. And there is one way to reach step 2.

Thus, the answer shud be 2^(n-2)+1.

Yes Fibonacci no. for the nth step is the right answer.

If N is Even x = N/2
If N is odd X = N/2-1
Answer is :
Xc0+Xc1+Xc2....+Xcx
Correct me if my answer is wrong.

Guys!!!

who ever not willing to accept fibonacci series as answer, try to use mathematical induction and you'll get the answer as Fibonacci series.....

already at step-1 : hence if n=1 , no.of ways=1
if n=2, already at step-1: hence only 1 way possible hence-> 1
n=3 (1,1) or (2) -> 2 ways

f(3)=f(2)+f(1);
...............n=4,5,6,....please try out

Fibonacci is the correct solution.
But the defination should be as below:
f(n) = f(n-1) + f(n-2) +1
f(1) = 0
f(2) = 1

F(4) should be equal to 3 bt the above formula is giving 4. There are 3 ways
1->2->3->4
1->2->4
1->3->4.

it should be defined as
F(1)=1;
F(2)=1;
F(n)=F(n-1)+F(n-2)

f(0) = 1 [Possible ways of reaching the step on which ur already there]
f(1) = 1 (1)
f(2) = 2 (1,1) (2)
f(3) = 3 (1,1,1) (1,2) (2,1)
f(4) = 5 (1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2)
...

it's a kind of dp problem,if ny one thoroughly looks into that then it can be seen easily
idea is that initialize an array a[n+1] with a[0]=1,a[1]=1
i=2
loop:
if i <=n
a[i]=a[i-1]+a[i-2]
else
break
i++
goto loop
print a[n+1]

f(n) = 2 + f(n-1) + f(n-2)

Which is basically the fibonacci series.

f(n) = f(n-1) + f(n-2) + f(n-3)

F(n) = total number of ways