1.13

设 $f:\mathbb{N} \rightarrow \mathbb{N}$ 满足 $f(0) = 1$

$f(1) = 1$

$f(x+2) =f(x)+f(x+1)$

证明：

(1) $f \in \mathcal{PRF}$；

(2) $f \in \mathcal{EF}$。

证明

(1) 令 $[a_0, a_1, \cdots, a_n] \prod\limits_{i=0}^{n} p_i^{a_i}$ 这里 $p_i$ 为第 $i$ 个素数，比如$p_0=2$，$p_1=3$，$p_2=5$，那么 $[a_0, a_1, a_2] = 2^{a_0} \cdot 3^{a_1} \cdot 5^{a_2}$，为 Gödel 编码形式

$ep_i(a) = a$ 的素因子分解式中第 $i$ 个素数的指数。易见 $ep_i[a_0, a_1, \cdots, a_n] = \left\{\begin{array}{ll} a_i, & i\leq n \\ 0, & i>n\end{array}\right.$ 从而令 $F(n) = [f(n), f(n+1)]$，$F(0) = [f(0), f(1)] = 2^1 \cdot 3^1 = 6$ $\begin{array}{rl} F(n+1) & = [f(n+1), f(n+2)]\\ & = [f(n+1), f(n+1)+f(n)] \\ & = [ep_1F(n), ep_1F(n)+ep_0F(n)] \\ & = H(F(n))\end{array}$ 这里，$H(x) = [ep_1x, ep_1x+ep_0x] = 2^{ep_1x} \cdot 3^{ep_1x} \cdot 3^{ep_0x}$

$\therefore H(x)$ 是初等的。

又 $\because F(0)=6, F(n+1) = H(F(n))$ ，以及 $H$ 为原始递归函数

$\therefore F(n)$ 为原始递归函数

又 $\because f(n)=ep_0F(x)$

$\therefore f(n)$ 为原始递归函数。

(2) 现在证明 $f(n)$ 是初等的。

证法一：

首先有 $f(n) \leq 2^n$ ，归纳证明如下：

当 $n=0,1$ 时，$f(0)=1 \leq 2^0$ ，$f(1) = 1 \leq 2^1$

归纳假设：$\forall k \leq n, f(k) \leq 2^k$

归纳步骤：当 $n<2$ 时，$f(n) \leq 2^n$ 为真，当 $n \geq 2$ 时，

$f(n) = f(n-1)+f(n-2) \leq 2^{n-1} +2^{n-2} \leq 2^{n-2} \cdot 3 \leq 2^{n-2} \cdot 4 \leq 2^n$

其次，还有 $F(n) \leq G(n)$ ，这里 $G(n) = 2^{2^n}\cdot 3^{2^{n+1}}$，且 $G(n)$ 是初等的。

$F(n) = [f(n), f(n+1)] = 2^{f(n)} \cdot 3^{f(n+1)} \leq 2^{2^n}\cdot 3^{2^{n+1}} = G(n)$，易见 $G(n)$ 的初等性。

令$\alpha(n) = [F(0), \cdots, F(n)] \leq [G(0), \cdots, G(n)]$，有 $\alpha(n) \leq \prod\limits_{i=0}^np_i^{G(i)} \leq \prod\limits_{i=0}^np_n^{(2^{2^n}\cdot 3^{2^{n+1}} \cdot (n+1))} = \beta(n)$ 易见，$\beta(n)$ 为初等函数。

因为 $\begin{array}{rl}\alpha(n) & = \mu x \leq \beta(n) \cdot (ep0x = F(0)) \wedge \forall i<n, ep{i+1}x = H(ep_ix) \\ & = \mu x \leq \beta(n) \cdot[ep_0x=6 \wedge \forall i <n , (ep_{i+1}x \ddot{-}H(ep_ix)=0)] \\ &= \mu x \leq \beta(n) \cdot\left[ep_0x=6 + \sum_{i \rightarrow n \ddot{-}1}(ep_{i+1}x\ddot{-}H(ep_ix))N^2n\right] \\ & = \mu x \leq \beta(n) \cdot \gamma(n) \end{array}$ 易见，$\gamma(n)$ 是初等的，所以 $\alpha(n)$ 是初等的。

因为 $f(n) = ep_0(F(n)) = ep_0(ep_n(\alpha(n)))$，所以 $f(n)$ 是初等的。

证法二： $f(n) = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}$ （该公式的证明参见 Kolman B, Busby R C. Ross S. Discrete mathematical structures. Prentice-Hall, Inc. 1996 (3rd) ）

从而 $\begin{array}{rl}f(n) & = \frac{1}{2^{n+1}\sqrt5}\left[(1+\sqrt 5)^{n+1} - (1-\sqrt 5)^{n+1}\right] \\ & = \frac{1}{2^{n+1}\sqrt5}\left[\sum_{i=0}^{n+1}C_{n+1}^i (\sqrt 5)^i - \sum_{i=0}^{n+1}C_{n+1}^i (-\sqrt 5)^i \right] \\ & = \frac{1}{2^{n+1}\sqrt5}\left[\sum_{i=0}^{n+1}C_{n+1}^i 2(\sqrt 5)^i N^2rs(i,2) \right] \\ & = \frac{1}{2^{n}}\left[\sum_{i=0}^{n+1}C_{n+1}^i 5^{\lfloor\frac{i}{2}\rfloor} N^2rs(i,2) \right] \\ \end{array}$