偶数项不小于相邻的奇数项的数列个数

O-17

求符合以下条件的序列 $a_1,a_2,\ldots,a_n$ 的个数,
(1) $a_i\in\{0,1\}$ 对正整数 $i$ 恒成立.
(2) $a_k\geqslant\max\{a_{k-1},a_{k+1}\}$ 对正偶数 $k$ 恒成立.

爪机专用

让我想起了这题：forum.php?mod=viewthread&tid=4545

kuing

设长度为 `n` 的满足要求的序列中，尾数是 0 的个数为 `x(n)`，尾数是 1 的个数为 `y(n)`，则所求个数为 `x(n)+y(n)`，显然 `x(1)=y(1)=1`。现在我们往最后添加一数使之仍然满足要求，分类讨论如下。

（1）当 `n=2k-1` 时：
若尾数是 0，则可添加 0 或 1；
若尾数是 1，则只能添加 1。
于是得到递推关系
\begin{align*}
x(2k)&=x(2k-1),\\
y(2k)&=x(2k-1)+y(2k-1);
\end{align*}

（2）当 `n=2k` 时：
若尾数是 0，则只能添加 0；
若尾数是 1，则可添加 0 或 1。
于是得到递推关系
\begin{align*}
x(2k+1)&=x(2k)+y(2k),\\
y(2k+1)&=y(2k).
\end{align*}

设 `z(n)=x(n)+y(n)`，那么根据以上两式，有
\begin{align*}
z(2k+1)&=x(2k+1)+y(2k+1)\\
&=x(2k)+2y(2k)\\
&=x(2k)+y(2k)+x(2k-1)+y(2k-1)\\
&=z(2k)+z(2k-1),
\end{align*}
O(∩_∩)O哈！竟然是肥波拉鸡数列喔😃，`z(1)=2`, `z(2)=3`，所以 `z(n)=F_{n+2}`。

这么好的结果，或许还能有更简洁的解释🤔