Number of subsets from an ordered set where adjacent elements may or may not be tied together Assume we have an ordered set $S$ with a finite number of elements $S=\{1,2,3,\ldots,N\}$. I need to know the number of subsets where adjacent elements from the original set may either be tied together as one "unit" shown with a "-" between them or separate elements shown as "," as normally in a subset.
For instance, with 2 elements, if $S=\{1,2\}$ this number is 5 where the 5 subsets are: $\{\},\{1\},\{2\},\{1,2\}$ and $\{1-2\}$.
And with 3 elements, if $S=\{1,2,3\}$ there are 13 subsets of this kind: $\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1-2\}, \{1,3\}, \{2,3\}, \{2-3\}, \{1,2,3\}, \{1-2,3\}, \{1,2-3\}$ and $\{1-2-3\}$.
With 4 elements I have counted this number to be 34. What is this number in the general case of $N$ elements, where $S=\{1,2,3,\ldots,N\}$ and can a formula be given?
 A: Let $a_n$ be the count of these listings for given $n$.
Then $a_n$ is obtained as sum of those listings not ending in $n$ (there are $a_{n-1}$ of these), those ending in "$,n$" (there are $a_{n-1}$ of these), and those anding in "${-}n$" (there are $a_{n-1}-a_{n-2}$ of these).
Hence we have the recursion
$$a_n=3a_{n-1}-a_{n-2}. $$
The general solution to this is 
$$a_n=\alpha_1 \lambda_1^n+\alpha_2\lambda_2^n $$
where $\lambda_{1,2}$ are the roots of $x^2-3x+1=0$. So $\lambda_{1,2}=\frac{3\pm\sqrt{5}}{2}$. We determine $\alpha_{1,2}$ so that the result matches $a_0=1$, $a_1=2$. This leads to $\alpha_{1,2}=\frac{5\pm\sqrt 5}{10}$ so that
$$ a_n=\frac{5+\sqrt 5}{10}\cdot\left(\frac{3+\sqrt{5}}{2}\right)^n+\frac{5-\sqrt 5}{10}\cdot\left(\frac{3-\sqrt{5}}{2}\right)^n.$$
As the second summand is always between $0$ and $1$, we might as well say
$$ a_n=\left\lceil\frac{5+\sqrt 5}{10}\cdot\left(\frac{3+\sqrt{5}}{2}\right)^n\right\rceil.$$

Remark. In particular, the formualas above lead to $a_4=34$, not $30$. Indeed, here's the list:
$$\begin{matrix}\{\}&
\{1\}&
\{2\}&
\{1,2\}&
\{1-2\}\\
\{3\}&
\{1,3\}&
\{2,3\}&
\{2-3\}&
\{1,2,3\}\\
\{1-2,3\}&
\{1,2-3\}&
\{1-2-3\}&
\{4\}&
\{1,4\}\\
\{2,4\}&
\{1,2,4\}&
\{1-2,4\}&
\{3,4\}&
\{3-4\}\\
\{1,3,4\}&
\{1,3-4\}&
\{2,3,4\}&
\{2-3,4\}&
\{2,3-4\}\\
\{2-3-4\}&
\{1,2,3,4\}&
\{1-2,3,4\}&
\{1,2-3,4\}&
\{1-2-3,4\}\\
\{1,2,3-4\}&
\{1-2,3-4\}&
\{1,2-3-4\}&
\{1-2-3-4\}& 
\end{matrix}$$
A: Here’s a slightly different way to approach the problem.
Let $\mathscr{A}$ be the family of such ‘subsets’ of $[n]$ (where $[0]$ is understood to be empty), and let $a_n=|\mathscr{A}_n|$. Clearly $a_0=1$ and $a_1=2$. Suppose that $n\ge 2$; $\mathscr{A}_n$ has $a_{n-1}$ members that do not contain $n$, so we’d like to know how many members of $\mathscr{A}_n$ do contain $n$. This suggests letting $\mathscr{B}_n$ be the set members of $\mathscr{A}_n$ that contain $n$ and letting $b_n=|\mathscr{B}_n|$; clearly $b_0=0$ and $b_1=1$, and $a_n=a_{n-1}+b_n$ for $n\ge 2$. 
Each member of $\mathscr{B}_n$ in which $n$ is tied to $n-1$ can be obtained uniquely by appending a tied $n$ to a member of $\mathscr{B}_{n-1}$. Every remaining member of $\mathscr{B}_n$ can be obtained uniquely by appending an untied $n$ to a member of $\mathscr{A}_{n-1}$. Thus, $b_n=b_{n-1}+a_{n-1}$.
Calculate a few values of $a_n$ and $b_n$:
$$\begin{array}{rcc}
n:&0&1&2&3&4&5\\ \hline
b_n:&0&1&3&8&21&55\\
a_n:&1&2&5&13&34&89
\end{array}$$
These numbers are instantly recognizable as the Fibonacci numbers. Moreover, if we arrange them in the order in which they are naturally calculated from the recurrences
$$\left\{\begin{align*}
b_n&=b_{n-1}+a_{n-1}\\
a_n&=a_{n-1}+b_n\;,
\end{align*}\right.$$
we get the ordinary Fibonacci sequence:
$$\begin{array}{ccc}
b_0&a_0&b_1&a_1&b_2&a_2&b_3&a_3&b_4&a_4&b_5&a_5\\
0&1&1&2&3&5&8&13&21&34&55&89\\
F_0&F_1&F_2&F_3&F_4&F_5&F_6&F_7&F_8&F_9&F_{10}&F_{11}
\end{array}$$
The obvious conjecture at this point is that in general $b_n=F_{2n}$ and $a_n=F_{2n+1}$. This is easily verified: the recurrences become
$$\left\{\begin{align*}
F_{2n}&=F_{2n-2}+F_{2n-1}\\
F_{2n+1}&=F_{2n-1}+F_{2n}\;,
\end{align*}\right.$$
which reduce to the single familiar Fibonacci recurrence $F_n=F_{n-1}+F_{n-2}$, and the initial values $F_0=b_0$ and $F_1=a_0$ are correct.
The problem is now reduced to standard results about the Fibonacci sequence. In particular, if $\varphi=\frac12\left(1+\sqrt5\right)$, it’s well known that $F_n$ is the integer nearest $\frac{\varphi^n}{\sqrt5}$, so $a_n$ is the integer nearest $\frac{\varphi^{2n+1}}{\sqrt5}$. Equivalently,
$$a_n=\left\lfloor\frac{\varphi^{2n+1}}{\sqrt5}+\frac12\right\rfloor\;.$$
Hagen von Eitzen’s closed form is easily derived from this and the observation that
$$\varphi^2=\frac{3+\sqrt5}2\;.$$
