Example 5 Let $p$ be a given positive integer, $A$ is a subset of $X=\left\{1,2,3,4, \cdots, 2^{p}\right\}$, and has the property: for any $x \in A$, $2 x \notin A$. Find the maximum value of $|A|$. (1991 French Mathematical Olympiad)
Analysis and Solution: Divide $X$ into blocks and use induction on $p$.

When $p=1$, $X=\{1,2\}$, take $A=\{1\}$, then $f(1)=1$;

When $p=2$, $X=\{1,2,3,4\}$, divide $X$ into 3 subsets: $\{1,2\}$, $\{3\}$, $\{4\}$. Then $A$ can contain at most one number from each subset, so $|A| \leqslant 3$. Take $A=\{1,3,4\}$, then $f(2)=3$;

When $p=3$, $X=\{1,2, \cdots, 8\}$. Divide $X$ into 5 subsets: $\{1,2\}$, $\{3,6\}$, $\{4,8\}$, $\{5\}$, $\{7\}$. Then $A$ can contain at most one number from each subset, so $|A| \leqslant 5$. Take $A=\{1,5,6,7,8\}$, then $f(3)=5$.

In general, when $X_{p}=\left\{1,2,3, \cdots, 2^{p}\right\}$, we can estimate by dividing into blocks. Notice that $2^{p-1}+1$, $2^{p-1}+2, \cdots, 2^{p}$ can all belong to $A$, so we think of dividing into blocks: $X=\left\{1,2,3, \cdots, 2^{p-1}\right\} \cup\left\{2^{p-1}+\right.$ $\left.1,2^{p-1}+2, \cdots, 2^{\rho}\right\}=X_{p-1} \cup M$, where $X_{p-1}=\left\{1,2,3, \cdots, 2^{p-1}\right\}$, $M=\left\{2^{\rho-1}+\right.$ $\left.1,2^{p-1}+2, \cdots, 2^{p}\right\}$. This way, the problem is how many numbers in $X_{p-1}=\left\{1,2,3, \cdots, 2^{p-1}\right\}$ can belong to $A$, is this the original problem for $p-1$? The problem is not that simple! Consider: when all numbers $2^{p-1}+1,2^{p-1}+2, \cdots, 2^{p}$ in $M$ belong to $A$, many numbers in $X_{p-1}$ cannot belong to $A$, for example: $2^{p-2}+1,2^{p-2}+2, \cdots, 2^{p-1}$ do not belong to $A$; but not necessarily $2^{p-1}+2,2^{p-1}+4, \cdots, 2^{p}$ all belong to $A$. Therefore, we need to make a finer division: some numbers $2^{p-1}+2,2^{p-1}+4, \cdots, 2^{p}$ in $M$ and relevant numbers in $X_{p-1}$ (with a 2-fold relationship) are paired to form sets: $\left\{2^{p-1}+2,2^{p-2}+1\right\}$, $\left\{2^{p-1}+4, 2^{p-2}+2\right\}$, $\cdots$, $\left\{2^{p}, 2^{p-1}\right\}$. This gives a partition of $X_{p}$:
$$\begin{aligned}
X_{p-2} & =\left\{1,2,3, \cdots, 2^{\rho-2}\right\}, M_{t}=\left\{2^{\rho-1}+2 t, 2^{\rho-2}+t\right\}(t=1,2, \cdots, \\
\left.2^{\rho-2}\right), M_{0} & =\left\{2^{\rho-1}+1,2^{\rho-1}+3,2^{p-1}+5, \cdots, 2^{p-1}+2^{\rho-1}-1\right\} .
\end{aligned}$$

Since $A$ can contain at most one element from $M_{t}\left(t=1,2, \cdots, 2^{p-2}\right)$, at most $f(p-2)$ elements from $X_{p-2}$, and at most $2^{p-2}$ elements from $M_{0}$, we have $f(p) \leqslant f(p-2)+2^{p-2}+$ $2^{p-2}=f(p-2)+2^{p-1}$.

Next, consider whether we can construct a set $A$ to prove $f(p) \geqslant f(p-2)+2^{p-1}$.
Let $X=\left\{1,2,3, \cdots, 2^{p-2}\right\}$ have a maximum subset $A_{1}$ that meets the conditions, and let $A_{2}=$ $\left\{2^{p-1}+1,2^{p-1}+2, \cdots, 2^{p}\right\}$. Then for any $x \in A_{1}$, we have $2 x \leqslant 2 \cdot 2^{p-2}=2^{p-1}<$ $2^{p-1}+1 \notin A_{2}$, so $A=A_{1} \cup A_{2}$ is a subset that meets the conditions, hence $f(p) \geqslant|A|=$ $f(p-2)+2^{p-1}$.

In summary, $f(p)=f(p-2)+2^{p-1}$.
We solve this recurrence relation in two ways.
Method 1: Iteration (sum of $p$ equations), we get $f(p-1)+f(p)=f(1)+f(2)+$ $2^{2}+2^{3}+\cdots+2^{p-1}=1+\left(2^{0}+2^{1}\right)+2^{2}+2^{3}+\cdots+2^{p-1}=2^{p}$.

Iterate again (subtract the $(p-1)$-th equation from the $(p-2)$-th equation, add the $(p-3)$-th equation, etc.), we get
$$f(p)+(-1)^{p} f(1)=2^{p}-2^{p-1}+\cdots+(-1)^{p} \cdot 2^{2},$$

so $\quad f(p)=2^{p}-2^{p-1}+\cdots+(-1)^{p} \cdot 2^{2}+(-1)^{p+1}$,
Notice that $(-1)^{p+1} \cdot 2^{1}+(-1)^{p+2} \cdot 2^{0}=(-1)^{p+1}(2-1)=(-1)^{p+1}$,
so $f(p)=2^{p}-2^{p-1}+\cdots+(-1)^{p} \cdot 2^{2}+(-1)^{p+1} \cdot 2^{1}+(-1)^{p+2} \cdot 2^{0}$
$$=\frac{2^{p}\left[1-\left(-\frac{1}{2}\right)^{p+1}\right]}{1+\frac{1}{2}}=\frac{2^{p+1}+(-1)^{p}}{3}$$

Method 2: Categorize and solve.
When $p$ is odd, $f(p)=f(p-2)+2^{p-1}=f(p-4)+2^{p-3}+2^{p-1}=$ $f(1)+2^{2}+2^{4}+\cdots+2^{p-1}=2^{0}+2^{2}+2^{4}+\cdots+2^{p-1}=\frac{2^{p+1}-1}{3}$;

When $p$ is even, $f(p)=f(p-2)+2^{p-1}=f(p-4)+2^{p-3}+2^{p-1}=$ $f(2)+2^{3}+2^{5}+\cdots+2^{p-1}=1+2^{1}+2^{3}+2^{5}+\cdots+2^{p-1}=\frac{2^{p+1}+1}{3}$.