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.
Best Answer
Let $f_n(m)$ be the number of $m$-length sequences with first term $1$, last term $n$.
A sequence of length $m$ which ends at $n$ is precisely one of the following two disjoint possibilities:
The first case: there are $f_{n-1}(m-1)$ options for this.
The second case: there is one option for each of the $n-1$ ending points. Therefore, there are $f_1(m-1) + f_2(m-1) + \dots + f_{n-2}(m-1)$ options.
That is, $f_n(m) = \sum_{i=1}^{n-1} f_i(m-1)$.
The initial conditions are that $f_n(n) = 1$, $f_n(m) = 0$ if $m > n$, and $f_n(1) = 0$.
To be honest, I'm not really sure why they've asked you to split it into those two cases. It's a very artificial distinction.