$2 \cdot 45$ A sequence of integers that is monotonically increasing, if its first term is odd, the second term is even, the third term is odd, the fourth term is even, $\cdots$, and so on, is called an alternating sequence. The empty set is also considered an alternating sequence. Let $A(n)$ denote the number of alternating sequences, where the integers are all taken from the set $\{1,2, \cdots, n\}$. Clearly, $A(1)=2, A(2)=3$. Find $A(20)$, and prove your conclusion.
[Solution] When $n=1$, $\phi$ and $\{1\}$ are two alternating sequences, so $A(1)=2$. When $n=2$, $\phi, \{1\}, \{1,2\}$ are three alternating sequences, so $A(2)=3$. If $\left\{a_{1}, a_{2}, a_{3}, \cdots, a_{m}\right\}$ is a non-empty alternating sequence taken from the set $\{1,2, \cdots, n\}$, then when $a_{1}=1$,
$$
\left\{a_{2}-1, a_{3}-1, \cdots, a_{m}-1\right\}
$$

is an alternating sequence taken from the set $\{1,2, \cdots, n-1\}$. And when $a_{1}=1$, the non-empty alternating sequence $\left\{a_{1}, a_{2}, a_{3}, \cdots, a_{m}\right\}$ taken from the set $\{1,2, \cdots, n\}$ corresponds one-to-one with the alternating sequence $\left\{a_{2}-1, a_{3}-1, \cdots, a_{m}-1\right\}$ taken from the set $\{1,2, \cdots, n-1\}$, so when $a_{1}=1$, the non-empty alternating sequence $\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}$ taken from the set $\{1,2, \cdots, n\}$ has $A(n-1)$ sequences.
When $a_{1} \geqslant 3$,
$$
\left\{a_{1}-2, a_{2}-2, \cdots, a_{m}-2\right\}
$$

is a non-empty alternating sequence taken from the set $\{1,2, \cdots, n-2\}$. And when $a_{1} \geqslant 3$, the non-empty alternating sequence $\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}$ taken from the set $\{1,2, \cdots, n\}$ corresponds one-to-one with the non-empty alternating sequence $\left\{a_{1}-2, a_{2}-2, \cdots, a_{m}-2\right\}$ taken from the set $\{1,2, \cdots, n-2\}$. So, when $a_{1} \geqslant 3$, the non-empty alternating sequence $\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}$ taken from the set $\{1,2, \cdots, n\}$ has $A(n-2)-1$ sequences.
From the above discussion, the number of alternating sequences taken from the set $\{1,2, \cdots, n\}$
$$
A(n)=A(n-1)+(A(n-2)-1)+1 \text {, }
$$

which is
$$
A(n)=A(n-1)+A(n-2) \text {. }
$$

Using the above equation, we calculate
$$
A(1)=2, A(2)=3, A(3)=A(1)+A(2)=5,
$$

Similarly, we get
$$
\begin{array}{llll}
A(4)=8, & A(5)=13, & A(6)=21, & A(7)=34 \\
A(8)=55, & A(9)=89, & A(10)=144, & A(11)=233 \\
A(12)=377, & A(13)=610, & A(14)=987, & A(15)=1597 \\
A(16)=2584, & A(17)=4181, & A(18)=6765, & A(19)=10946 \\
A(20)=17711 . & &
\end{array}
$$