# Recurrence relation for increasing sequence of numbers

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, 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.

• @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. Jul 26 '20 at 18:05