Recurrence relation for climbing a staircase

Question

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.

Answer 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.