Finding a set of sequences using a recurrence relation 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...
 A: 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$
A: 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?
A: 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.
