|
|
抄一下7#$\renewcommand{\mathrm}[1]{#1}$
$$
x_{n+1}=x_{n}^{2}+g_{n}, \quad n \geq 0\tag{13}
$$
with boundary conditions, and are such that
(i)$x_{n}>0$
(ii)$\left|g_{n}\right|<\frac{1}{4} x_{n}$ and $1 \leq x_{n}$ for $n \geq n_{0}$ and
(iii)$g_n$ satisfies condition (16) below
Let
$$
\mathrm{y}_{\mathrm{n}}=\log \mathrm{x}_{\mathrm{n}}, \quad \alpha_{\mathrm{n}}=\log \left(1+\frac{\mathrm{g}_{\mathrm{n}}}{\mathrm{x}_{\mathrm{n}}^{2}}\right)
$$
Then by taking logarithms of (13) we obtain
$$
\mathrm{y}_{\mathrm{n}+1}=2 \mathrm{y}_{\mathrm{n}}+\alpha_{\mathrm{n}}, \quad \mathrm{n} \geq 0 .\tag{14}
$$
For any sequence $\left\{\alpha_{n}\right\}$, the solution of (14) is (see for example [15], p. 26)
\begin{aligned}
\mathrm{y}_{\mathrm{n}}&=2^{\mathrm{n}}\left(\mathrm{y}_{0}+\frac{\alpha_{0}}{2}+\frac{\alpha_{1}}{2^{2}}+\ldots+\frac{\alpha_{\mathrm{n}-1}}{2^{\mathrm{n}}}\right)
\\
&=\mathrm{Y}_{\mathrm{n}}-\mathrm{r}_{\mathrm{n}} \text {, }
\end{aligned}
where
$$\tag{15}\begin{gathered}
Y_{n}=2^{n} y_{0}+\sum_{i=0}^{\infty} 2^{n-1-i} \alpha_{i}
\\
r_{n}=\sum_{i=n}^{\infty} 2^{n-1-i} \alpha_{i}
\end{gathered}$$
Assuming that the $g_{n}$ are such that
$$
\left|\alpha_{n}\right| \geq\left|\alpha_{n+1}\right| \quad \text { for } n \geq n_{0}\tag{16}
$$
it follows from (15) that $\left|r_{n}\right| \leq\left|\alpha_{n}\right|$. Then
$$
x_{n}=e^{y_{n}}=e^{Y_{n}-r_n}=x_{n}e^{-r_{n}}\tag{17}
$$
where
$$\mathrm{X}_{\mathrm{n}}=\mathrm{e}^{\mathrm{Y}_n}=\mathrm{k}^{2^{\mathrm{n}}} \tag{18}$$
$$\mathrm{k}=\mathrm{x}_{0} \exp \left(\sum_{\mathrm{i}=0}^{\infty} 2^{-\mathrm{i}-1} \alpha_{i}\right)\tag{19}$$
Also
\begin{aligned}
x_{n} &=x_{n} e^{r_{n}} \leq x_{n} e^{\left|\alpha_{n}\right|} \\
& \leq x_{n}\left(1+\frac{2\left|g_{n}\right|}{x_{n}^{2}}\right) \text { for } n \geq n_{0}
\end{aligned}
using (ii), and the fact that $(1-\mathrm{u})^{-1} \leq 1+2 \mathrm{u}$ for $0 \leq \mathrm{u} \leq \frac{1}{2}$,
$$
=x_{n}+\frac{2\left|g_{n}\right|}{x_{n}}
$$
and
$$
x_{n} \geq x_{n} e^{-\left|\alpha_{n}\right|} \geq x_{n}\left(1-\frac{\left|g_{n}\right|}{x^{2}}\right)=x_{n}-\frac{\left|g_{n}\right|}{x_{n}}\text{ .}
$$
From assumption (ii), this means that
$$
\left|x_{n}-X_{n}\right|<\frac{1}{2} \text { for } n \geq n_{0}
$$
If $\mathrm{x}_{\mathrm{n}}$ is an integer, as in recurrences (1)-(3), (8) for $\mathrm{r}$ even, and (10), then the solution to the recurrence (13) is
$$
x_{n}=\text { nearest integer to } k^{2}, \text { for } n \geq n_{0}\tag{20}
$$
while if $x_{n}$ is half an odd integer, as in (8) for $r$ odd and (12), the solution is
$$
x_{n}=\left(\text { nearest integer to } \mathrm{k}^{2}+\frac{1}{2}\right)-\frac{1}{2}, \quad \text { for } n \geq n_{0}\tag{21}
$$
where $\mathrm{k}$ is given by (19).
Note that if $\mathrm{g}_{\mathrm{n}}$ is always positive, then $\alpha_{\mathrm{n}}>0, \mathrm{r}_{\mathrm{n}}>0, \mathrm{X}_{\mathrm{n}}>\mathrm{x}_{\mathrm{n}}$, and (20) may be replaced by
$$
\mathrm{x}_{\mathrm{n}}=\left[\mathrm{k}^{2^n}\right] \quad \text { for } \mathrm{n} \geq \mathrm{n}_{0}\tag{22}
$$
where $[\mathrm{a}]$ denotes the integer part of $a$. Similarly if $\mathrm{g}_{\mathrm{n}}$ is always negative then $X_{n}<x_{n}$ and
$$
x_{n}=\left[k^{2^n}\right] \quad \text { for } n \geq n_{0}\tag{23}
$$
where $[a]$ denotes the smallest integer $\geq a$.
In some cases (see below) $\mathrm{k}$ turns out to be a "known" constant (such as $\frac{1}{2}(1+\sqrt{5})$ ). But in general Eqs. (20)-(23) are not legitimate solutions to the recurrence (13), since the only way we have to calculate $\mathrm{k}$ involves knowing the terms of the sequence. Nevertheless, they accurately describe the asymptotic behavior of the sequence.
We now apply this result to the preceding examples. For all except 2.7 the proofs of properties (ii) and (iii) are by an easy induction, and are omitted.
Example 2.1.
Here $g_{n}=0, k=2$ and (20) correctly gives the solution $x_{n}=2^{2^{n}}$.
Example 2.2.
Condition (ii) holds for $\mathrm{n}_{0}=2$, and (iii) requires $\mathrm{x}_{\mathrm{n}} \leq \mathrm{x}_{\mathrm{n}+1}$, which is immediate.
From (20) $\mathrm{x}_{\mathrm{n}}=\left[\mathrm{k}^{2^n}\right]$ for $\mathrm{n} \geq 1$, where
$$
\begin{aligned}
\mathrm{k} &=\exp \left(\frac{1}{2} \log 2+\frac{1}{4} \log \frac{5}{4}+\frac{1}{8} \log \frac{26}{25}+\frac{1}{16} \log \frac{677}{676}+\cdots\right) \\
&=1.502837 \cdots
\end{aligned}
$$
The comparison of $k^{2^{n}}$ with $x_{n}$ is as follows:
$$\begin{array}{ccccccc}\mathrm{n} & 0 & 1 & 2 & 3 & 4 & 5 \\ \mathrm{x}_{\mathrm{n}} & 1 & 2 & 5 & 26 & 677 & 458330 \\ \mathrm{k}^{2^\mathrm{n}} & 1.50284 & 2.25852 & 5.10091 & 26.01924 & 677.00074 & 458330.00000\end{array}$$
Example 2.3 is similar, and $\mathrm{x}_{\mathrm{n}}=\left[\mathrm{k}^{2^{\mathrm{n}}}\right]$ where $\mathrm{k}=1.678459 \cdots$
Example 2.5.
It is found that (ii) is valid for $\mathrm{n}_{0}=1$ if $\mathrm{r}=1$ and for $\mathrm{n}_{0}=3$ if $r>3$. The solution of (5) for $r=1$ (and of example 2.4) is
$$
\mathrm{y}_{\mathrm{n}}^{(1)}=\left[\mathrm{k}^{2} \mathrm{n}+\frac{1}{2}\right], \quad \mathrm{n} \geq 0
$$
and for $r \geq 3$ is
$$
\mathrm{y}_{\mathrm{n}}^{(\mathrm{r})}=\left[\mathrm{k}^{2} \mathrm{n}+\frac{\mathrm{r}}{2}\right], \quad \mathrm{n} \geq 3
$$
where $\mathrm{k}$ is given by (19). The first few values of $\mathrm{k}$ are as follows.
$$\begin{array}{ccccc}\mathrm{r} & 1 & 3 & 4 & 5 \\ \mathrm{k} & 1.264085 & 1.526526 & 1.618034 & 1.696094\end{array}$$
For $r=4$, the value of $k$ is seen to be very close to the "golden ratio"
$$
\varphi=\frac{1}{2}(1+\sqrt{5})=1.6180339887 \cdots
$$
In fact we may take $k=\varphi$, for
$$
\begin{aligned}
&\mathrm{y}_{1}^{(4)}=5 \\
&\mathrm{y}_{\mathrm{n}+1}^{(4)}=\left(\mathrm{y}_{\mathrm{n}}^{(4)}-2\right)^{2}, \quad \mathrm{n} \geq 1
\end{aligned}
$$
is solved exactly by
$$
\mathrm{y}_{\mathrm{n}}^{(4)}=\varphi^{2^{\mathrm{n}}}+\varphi^{-2} \mathrm{n}+2, \quad \mathrm{n} \geq 1
$$
and so
$$
\mathrm{y}_{\mathrm{n}}^{(4)}=\left[\varphi^{2^{\mathrm{n}}}+2\right], \quad \mathrm{n} \geq 1
$$
(This was pointed out to us by D. E. Knuth.) So far, none of the other values of $k$ have been identified. Golomb [9] has studied the solution of (5) by a different method.
Example 2.6.
The solution to (9) is
$$
\mathrm{y}_{\mathrm{n}}=\left[\frac{1}{2}\left(1+\mathrm{k}^{2^n}\right)\right] \quad \text { for } \mathrm{n} \geq 1
$$
where $\mathrm{k}=1.618034 \cdots$, and again, as pointed out by D. E. Knuth, we may take
$$
\mathrm{k}=\varphi=\frac{1}{2}(1+\sqrt{5})
$$
since
$$
\mathrm{x}_{\mathrm{n}}=\varphi^{2^{\mathrm{n}}}+\varphi^{-2^n}, \quad \mathrm{n} \geq 0
$$
solves (10) exactly. A similar exact solution can be given for (10) for any initial value $\mathrm{x}_{0}$.
Example 2.7.
This is the only example for which (ii) and (iii) are not immediate. Bounds on $x_{n}$ and $\mathrm{y}_{\mathrm{n}}$ are first established by induction:
$$
2^{2^{n-2.1}} \leq x_{n} \leq y_{n} \leq 2^{2^{n-2}} \quad \text { for } n \geq 4
$$
then
$$
\mathrm{g}_{\mathrm{n}}=-\left(\mathrm{x}_{\mathrm{n}-2}+\frac{1}{2}\right)^{2}-\frac{3}{4}=-\mathrm{y}_{\mathrm{n}-2}^{2}-\frac{3}{4}
$$
and
$$
2^{2^{n-3.1}} \leq \mathrm{g}_{\mathrm{n}} \leq 2^{2^{\mathrm{n}-3}} \text { for } \mathrm{n} \geq 7
$$
It is now easy to show that (ii) and (iii) hold for $n \geq n_{0}=5$. The solution is
$$
\mathrm{y}_{\mathrm{n}}=\left[\mathrm{k}^{2}+\frac{1}{2}\right], \quad \mathrm{n} \geq 1
$$ |
|
敬畏数学
posted 2018-3-16 10:12
hbghlyj
posted 2022-4-15 22:59
这是怎么求出来嘀
