Finding a set of sequences using a recurrence relation

Question

I was given the next question: I need to find the recurrence relation, $An$ , for the number of the finite strictly decreasing sequences which consist numbers that are smaller than $n$ or equal to $n$ and also the difference between two successive numbers is at least 2.

For exmaple, if n=3 the sequences are: (3,0) ,(3,1), (2,0) , (0), (1), (2), (3) therefore $A3$ equals to 7

I'm trying to figure out what's wrong with my solution. I suggested that the problem is similar to the problem of finding how many $n$ long binary strings are there such that between each $'1'$ there is at least one $'0'$ but the answer doesn't seem to be right...

Answer 1

For $n\geq 2$ we have $A_n=A_{n-1}+A_{n-2}+1$. Why?

The number of decreasing sequences that do not contain $n$ is clearly $A_{n-1}$. The number of sequences that contain $n$ is $A_{n-2}+1$, since each one is obtained by taking a decreasing sequence with a subset of the terms $\{n-2,n-1,\dots,1\}$ and adding $n$ at the beginning, the only one that cannot be obtained this way is the sequence that only contains $n$.

Using this we have the first few values are:

$A_0=1,A_1=2,A_2=4,A_3=7,A_5=12,\dots$

Answer 2

Your solution is almost right ... except for the fact that you need at least a $1$ in your binary string (the empty sequence does not qualify, or does it?), and your string is really $n+1$ bits long rather than $n$ bits long (because you count down from $n$ to $0$, inclusive, and that's $n+1$ numbers)! Can you write the recurrence relationship for your case?

Answer 3

This is sequence A000071 in the Online Encyclopedia of Integer Sequences. See: https://oeis.org/A000071 and the references therein for everything you could ever want to know about it.