If $x_1, x_2, \dots, x_n$ is sequence of non-negative integers (of any length including the empty sequence) then $s_k$ is the total number of such sequences such that $x_i \in [k]$ and $x_i \leq \frac{x_{i+1}}{2}$. We only know that $s_0 = 1, k \geq 1$ and I need to show that: $$s_{k-1} + s_{\lfloor k/2 \rfloor} = s_k$$
And, how can I convert the recurrence relation $s_n$ into the ordinary generating series $F(x)$ such that: $$\frac{F(x)}{F(x^2)} = \frac{(1+x)}{(1-x)}$$
Best Answer
Let $S_k$ be the set of sequences $\langle x_1,\ldots,x_n\rangle$ such that $x_i\in[k]$ for $i=1,\ldots,n$ and $x_i\le\frac{x_{i+1}}2$ for $i=1,\ldots,n-1$; $s_k=|S_k|$. Suppose that $\sigma=\langle x_1,\ldots,x_n\rangle\in S_k$. If $x_n<k$, then $\sigma\in S_{k-1}$. And $S_{k-1}\subseteq S_k$, so there are $s_{k-1}$ sequences in $S_k$ whose last term is less than $k$. If $x_n=k$, then $x_{n-1}\le\frac{x_n}2$, so $\langle x_1,\ldots,x_{n-1}\rangle\in S_{\lfloor k/2\rfloor}$. That is, every sequence in $S_k$ whose last term is $k$ is obtainted from a sequence in $S_{\lfloor k/2\rfloor}$ by appending a term $k$. Conversely, if $\langle x_1,\ldots,x_{n-1}\rangle\in S_{\lfloor k/2\rfloor}$, then $\langle x_1,\ldots,x_{n-1},k\rangle\in S_k$, so there are $s_{\lfloor k/2\rfloor}$ sequences in $S_k$ that end in $k$. Every $\sigma\in S_k$ either does or does not end in $k$, and none does both, so we’ve counted every sequence in $S_k$ once, and $s_k=s_{k-1}+s_{\lfloor k/2\rfloor}$.
We can infer the relationship
$$\frac{F(x)}{F(x^2)}=\frac{1+x}{1-x}\tag{1}$$
directly from the recurrence without determining the generating function $F(x)$ itself. Rewrite the recurrence as $s_k-s_{k-1}=s_{\lfloor k/2\rfloor}$, multiply through by $x^k$, and sum over $k\ge 0$:
$$\sum_{k\ge 0}s_kx^k-\sum_{k\ge 0}s_{k-1}x^k=\sum_{k\ge 0}s_{\lfloor k/2\rfloor}x^k\;.$$
The lefthand side is
$$\begin{align*} \sum_{k\ge 0}s_kx^k-\sum_{k\ge 0}s_{k-1}x^k&=F(x)-x\sum_{k\ge 0}s_{k-1}x^{k-1}\\ &=F(x)-x\sum_{k\ge 0}s_kx^k\\ &=(1-x)F(x)\;, \end{align*}$$
and the righthand side is
$$\begin{align*} \sum_{k\ge 0}s_{\lfloor k/2\rfloor}x^k&=\sum_{k\ge 1}s_k(x^{2k}+x^{2k+1})\\ &=(1+x)\sum_{k\ge 0}s_kx^{2k}\\ &=(1+x)F(x^2)\;, \end{align*}$$
so $(1-x)F(x)=(1+x)F(x^2)$, and $(1)$ follows immediately.
The sequence is OEIS A000123, and the generating function apparently does not have a nice form.