Let $n$ be a fixed positive integer. How many sequences $1 \leq a_{1}<a_{2}<\cdots<a_{k} \leq n$ are there, in which the terms with odd indices are odd, and the terms with even indices are even integers?
Let $A_{n}$ denote the desired number. We will show that for $n \geqslant 3$, $A_{n}=A_{n-1}+A_{n-2}+1$.

We categorize the sequences into three classes:

1. The number of sequences not ending in $n$ is $A_{n-1}$, because for these, it must be true that $1 \leqslant a_{1}<a_{2}<\ldots<a_{k} \leqslant n-1$, and each term must have the same parity as its index.
2. The sequence whose last term is $n$ and does not contain any element smaller than $(n-1)$. There is exactly one such sequence: for odd $n$, it is the sequence consisting of a single $n$, and for even $n$, it is the sequence $(n-1), n$.
3. The sequences whose last term is $n$ and contain an element smaller than $(n-1)$. These are obtained by taking a sequence of elements not greater than $(n-2)$ (the number of such sequences is $A_{n-2}$); if the largest element of this sequence has the same parity as $n$, then we append the numbers $(n-1)$ and $n$ to the sequence, and if the last element has the opposite parity to $n$, then we append the number $n$ (in either case, the sequence can be extended in only one way).

The total number of sequences from the three classes is $A_{n-1}+A_{n-2}+1$, thus proving the recursion.

Let $f_{n}$ be the $n$-th Fibonacci number $\left(f_{0}=0, f_{1}=1, f_{n+1}=f_{n}+f_{n-1}\right)$. We will prove by induction that $A_{n}=f_{n+2}-1$.

If $n=1$, there is 1 sequence: the single 1, so $A_{1}=1=f_{3}-1$.

If $n=2$, the sequences (1) and $(1,2)$ satisfy the condition, so $A_{2}=2=f_{4}-1$.

Thus, the statement holds for $n=1$ and $n=2$. Let $k \geqslant 3$ and assume the statement holds for $n=k-1$ and $n=k-2$. Then, by the proven recursion and the definition of the Fibonacci sequence,

$$
A_{k}=A_{k-1}+A_{k-2}+1=\left(f_{k+1}-1\right)+\left(f_{k}-1\right)+1=\left(f_{k+1}+f_{k}\right)-1=f_{k+2}-1
$$

so the statement is also true for $n=k$.

Therefore, the number of the desired sequences is $f_{n+2}-1$.

Remark. It is known that

$$
f_{n}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}
$$

Using this, we can derive an explicit formula for $A_{n}$:

$$
A_{n}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+2}}{\sqrt{5}}-1
$$

Krisztián Tichler (Fazekas M. Főv. Gyak. Gimn., IV. o. t.)