Find a recurrence relation which describes the number of possible differences routes which bring the man to the roof

Question

A man interesting to climb a tower with $n$ floors. Each step he can jump one floor or two floors at once. The man can stop at most one time for rest (but he does not have to). Find a recurrence relation which describes the number of possible differences routes which bring the man to the roof.

My attempt: If the men can not stop at most one time so $A_n=A_{n-1}+A_{n-2}$ but I don`t know how to take into account the possibility of stopping.

EDIT: An example for the problem: A rest is one of the steps in the route to the roof. The following routs are not equivalent: 1-2-3, 1-2-2-3, 1-1-2-3, 1-2-3-3, when the first number indicates the floor which the man came after one step, the second after two steps and so on..

Answer 1

That's tricky. I think you'd need to separate families to count the number of ways to climb $k$ floors with no stop (which I'll call $N_k$) and the number of ways to climb $k$ floors with one stop (which I'll call $S_k$). Then we'd have: $$N_k=N_{k-1}+N_{k-2}\\S_k=S_{k-1}+S_{k-2}+N_k$$I think $S_k$ would be the number you're looking for, since getting to the top without a break would "look" like getting to the top and then taking a break at the top. But double-check for small values of $k$ to be sure.

Answer 2

One possible way to solve it would be to deduce first a generating function for the problem without resting:

Let $F(x,y)= \sum_{n,k\ge0 } a_{n,k} x^ny^k$, where $k$ counts the number of decisions you make, and $a_{n,k}$ therefore is the number of ways to arrive at the desired $n$-th floor with exactly $k$ decisions.

(We'll assume that you start at floor $0$)

We can then deduce the generating function via the recurrence $$ a_{n,k} = a_{n-1,k-1} + a_{n-2,k-1} $$

After that, modify $F(x,y)$ to take resting once into account: Let's take a random decision-sequence of $k$ decisions that takes you to the desired floor. Then we have $k+1$ ways to inject our single resting-decisions into this sequence.

A little more thought gives you then that we generate any sequence in which we rest, and we generate each of those sequences exactly once.

So, we get that the generating function we're looking for is $$\sum_{n,k\ge0 } a_{n,k} x^ny^k + \sum_{n,k\ge0 }(k+1) a_{n,k} x^ny^k = F(x,y) + \frac d{dx} yF(x,y)$$

As we don't care about how many decisions it takes, we set $y=1$ and obtain the generating function for your problem.

If you did everything right, you'll end up with this generating function: $$ - \frac{x^2 + x - 2}{(x^2 + x - 1)^2} $$

Which produces the sequence $(2,3,7,13,25,...)$.

To argue for the first two values:
$n=0$ has the solutions: a)Do nothing, or b) Rest once.
$n=1$ has the solutions: a) Go one floor up, b) Go one floor up, Rest, c) Rest, go one floor up.