1

You can climb a staircase taking an odd number of steps at a time. Say, you can climb a staircase of 10 stairs taking any odd number of steps from $1$ to $9$ at a time. I think the recurrence relation for this is $U_n = U_{n-1} + U_{n-3} + U_{n-5} + ...$ But the material from which I am reading says the the recurrence reduces to the fibonacci one. $U_n=U_{n-1}+U_{n-2}$. I cannot understand this.

tomriddle99
  • 569
  • 1
    That's the recurrence relation if n is even, but if n is odd it's $U_n=1+U_{n-1}+U_{n-3}+...$ (because you could also take all the steps at once). If you try this out for small values with $U_1=U_2=1$, it does turn out to be the fibonacci relation. –  Aug 12 '19 at 11:12

1 Answers1

1

It is true that the sequence generated by that recurrence relation is identical to the Fibonacci sequence (given suitable base cases, of course). Basically, it is the identities that $$\sum_{k=0}^{n-1}F_{2k+1}=F_{2n}$$ and $$1+\sum_{k=1}^{n}F_{2k}=F_{2n+1}$$ which are pretty easy to prove by induction.