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)}$$


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


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.

  • $\begingroup$ @Puzzled123: That’s something that you might try to do if you had a closed form for $s_k$, but without that, I don’t see any way to prove it by induction; I think that you probably really do need to analyze the structure of these sequences. $\endgroup$ Jul 26 '20 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.