习题-归纳定义原理

习题

 1. 设\((b_1,b_2,\cdots)\)是实数的一个无穷序列。用归纳法定义它的和\(\sum_{k=1}^n b_k\)如下：

\[\begin{align*}&\sum_{k=1}^n b_k = b_1\qquad\qquad\text{当}n=1,\\&\sum_{k=1}^n=(\sum_{k=1}^{n-1} b_k)+b_n\ \ \text{当}n>1. \end{align*} \]

 设\(A\)为实数集，选取\(\rho\)，使得可以用定理 8.4来严格定义这个和。

 我们有时用符号\(b_1+b_2+\cdots+b_n\)表示和\(\sum_{k=1}^n b_k\)。

 2. 设\((b_1,b_2,\cdots)\)为实数的一个无穷序列。\(\prod_{k=1}^nb_k\)的定义为

\[\begin{align*}&\prod_{k=1}^1b_k = b_1,\\&\prod_{k=1}^nb_k = (\prod_{k=1}^{n-1}b_k)\cdot b_n,\quad \text{当}n>1. \end{align*} \]

 试应用定理 8.4来严格定义这个积。我们有时用符号\(b_1b_2\cdots b_n\)来表示积\(\prod_{k=1}^n b_k\)。

 3. 作为习题 2的特例，对于\(n\in\mathbb{Z}_+\)，给出\(a^n\)与\(n!\)的定义。

 4. 数论中的Fibonacci数是用下式归纳定义的：

\[\begin{align*}&\lambda_1=\lambda_2=1,\\&\lambda_n=\lambda_{n-1}+\lambda_{n-2},\quad\text{对于}n>2. \end{align*} \]

 试用定理 8.4给出它的严格定义。

 5. 证明存在唯一的一个函数\(h:\mathbb{Z}_+\rightarrow\mathbb{R}_+\)，满足公式

\[\begin{align*}&h(1)=3,\\&h(i)=[h(i-1)+1]^{1/2},\quad\text{对于}i>1. \end{align*} \]

 6. (a)证明不存在函数\(h:\mathbb{Z}_+\rightarrow \mathbb{R}_+\)满足公式

\[\begin{align*}&h(1)=3,\\&h(i)=[h(i-1)-1]^{1/2},\quad\text{对于}i>1. \end{align*} \]

 试说明为什么这个例子不违背归纳定义原理。

 (b) 考虑归纳公式

\[\begin{align*}&h(1)=3,\\&h(i)=\left\{\begin{array}{ll}[h(i-1)-1]^{1/2},&\text{如果}h(i-1)>1\\5,&\text{如果}h(i-1)\leqslant 1\end{array}\right \}\quad\text{对于}i>1. \end{align*} \]

 证明存在唯一的函数\(h:\mathbb{Z}_+\rightarrow\mathbb{R}_+\)满足这个公式。

 7. 证明定理 8.4。

 8. 证明归纳定义原理的以下形式：设\(A\)是一个集合，\(\rho\)是一个函数，使得每一个从正整数\(\mathbb{Z}_+\)的一个截\(S_n\)映到\(A\)中的函数\(f\)对应着\(A\)中的一个元素\(\rho(f)\)。则存在唯一的一个函数\(h:\mathbb{Z}_+\rightarrow A\)，使得对于每一个\(n\in\mathbb{Z}_+\)，\(h(n)=\rho(h|S_n)\)。

解答

 1. 解 设\(h(n)=\sum_{k=1}^n b_k\)，则定义\(\rho(h|\{1,\cdots,i-1\})=h(i-1) + b_i\)，容易验证由\(\rho\)定义的和\(h(n)=\sum_{k=1}^nb_k\)符合题意。

 2. 解 设\(h(n)=\prod_{k=1}^n b_k\)，有归纳定义：

\[\begin{align*}&h(1) = b_1,\\&h(i) = h(i-1)\cdot b_i,\quad\text{对于}i>1. \end{align*} \]

 容易验证其符合题意。

 3. 解 有\(a^n=\prod_{k=1}^n a,n!=\prod_{k=1}^n k\)。

 4. 解 归纳定义如下：

\[\begin{align*}&\lambda_1 = 1,\\&\lambda_i = \left\{\begin{array}{ll}\lambda_{i-1}+\lambda_{i-2},&\text{如果}i>2\\1,&\text{如果}i=2\end{array}\right\}\quad\text{对于}i>1. \end{align*} \]

 5. 证明 只需注意到对于任意\(n\in\mathbb{Z}_+,h(n)>0\)，\(h\)是良定义的，结合定理 8.4即可证明。

$\square$

 6. 证明 (a) 按归纳定义公式有\(h(2)=\sqrt{2},h(3)=\sqrt{\sqrt{2}-1},h(4)=\sqrt{\sqrt{\sqrt{2}-1} - 1},\sqrt{\sqrt{2}-1}-1<0\)，矛盾，故不存在\(h\)满足公式。这并不违背定理 8.4，因为定理 8.4要求\(\rho\)是良定义的，而此处不是。

 (b) 容易验证\(\rho\)是良定义的，结合定理 8.4即可证明存在唯一的函数\(h\)符合公式。

$\square$

 7. 证明 考虑以下归纳公式

\[\begin{aligned}&h(1) = a_0,\\&h(i) = \rho(h|\{1,\cdots,n-1\}),\quad\text{对于}i>1. \end{aligned}\tag{$*$}\label{*} \]

 先证明以下引理：

 引理 1 给定\(n\in\mathbb{Z}_+\)，存在一个函数

\[f:\{1,\cdots,n\}\rightarrow C, \]

对于定义域中的所有\(i\)满足\(\eqref{*}\)。

 证 用归纳法加以证明。当\(n=1\)时引理成立，因为由

\[f(1) = a_0 \]

定义的函数\(f:\{1\}\rightarrow C\)满足\(\eqref{*}\)。

 假定引理对于\(n-1\)成立，以下证明引理对于\(n\)成立。根据归纳假定，存在函数\(f':\{1,\cdots, n-1\}\rightarrow C\)，对于定义域\(\{1,\cdots,n-1\}\)中所有\(i\)满足\(\eqref{*}\)。用

\[\begin{align*}&f(i) = f'(i),\quad\text{对于}i\in\{1,\cdots,n-1\},\\&f(n) = \rho(f'|\{1,\cdots, n-1\}) \end{align*} \]

定义一个函数\(f:\{1,\cdots,n\}\rightarrow C\)。容易验证，\(f\)对于定义域中的所有\(i\)满足\(\eqref{*}\)。因为当\(i\leqslant n-1\)时，\(f\)等于\(f'\)，所以函数\(f\)满足\(\eqref{*}\)。当\(i=n\)时，\(f\)定义为

\[f(n) = \rho(f'|\{1,\cdots, n-1\}) \]

而\(f(i) = f'(i),i=1,\cdots n-1\)，所以\(f\)也满足\(\eqref{*}\)。

$\square$

 引理 2 设\(f:\{1,\cdots, n\}\rightarrow C\)与\(g:\{1,\cdots, m\}\rightarrow C\)对于它们各自定义域中的所有\(i\)都满足\(\eqref{*}\)，则对于两个定义域中所有公共的\(i\)，\(f(i)=g(i)\)。

 证 设结论不真。令\(i\)为使得\(f(i)\ne g(i)\)的最小整数，根据\(\eqref{*}\)

\[f(1) = a_0 = g(1) \]

所以整数\(i\)不是1。对于所有\(j<i\)，我们有\(f(j)=g(j)\)。由于\(f\)和\(g\)满足\(\eqref{*}\)，所以

\[\begin{align*}&f(i) = \rho(f|\{1,\cdots,i-1\})\\&g(i) = \rho(g|\{1,\cdots,i-1\}) \end{align*} \]

由于\(f(j) = g(j),i=1,\cdots i-1\)，所以\(f(i)=g(i)\)，这与\(i\)的选取矛盾。

$\square$

 现证明定理 8.4。根据引理 1，对于每一个\(n\)，存在一个将\(\{1,\cdots,n\}\)映到\(C\)中的函数，并且对其定义域中所有\(i\)满足\(\eqref{*}\)。给定\(n\)，引理 2证明了这样的函数是唯一的，定义域相同的两个这样的函数必定相等。设\(f_n:\{1,\cdots,n\}\rightarrow C\)表示这个唯一的函数。

 现在进行关键的一步。定义一个函数\(h:\mathbb{Z}_+\rightarrow C\)，其指派法则是所有\(f_n\)的指派法则的并\(U\)。由于\(f_n\)的指派法则是\(\{1,\cdots,n\}\times C\)的一个子集，因此\(U\)是\(\mathbb{Z}_+\times C\)的一个子集。我们要证明\(U\)是函数\(h:\mathbb{Z}\rightarrow C\)的指派法则。

 就是说我们要证明\(\mathbb{Z}_+\)的每一个元素\(i\)恰好是\(U\)中一个元素的第一个坐标，这是容易的。整数\(i\)在\(f_n\)定义域中的充分必要条件是\(n\geqslant i\)，所以\(U\)中所有使\(i\)为其第一个坐标的元素的集合，正好是形如\((i,f_n(i))\)的所有偶对的集合，其中\(n\geqslant i\)。引理 2表明，当\(n,m\geqslant i\)时\(f_n(i)=f_m(i)\)。因此，\(U\)中所有这些元素都相等，亦即\(U\)中只有一个元素以\(i\)为它的第一个坐标。

 证明\(h\)满足条件\(\eqref{*}\)也是容易的，它是以下事实的推论：

\[\begin{align*}&\text{如果}i\leqslant n,\text{则}h(i)=f_n(i),\\&f_n\text{对于定义域中所有}i\text{满足}\eqref{*}. \end{align*} \]

唯一性证明是引理 2的证明的翻版。

$\square$

 8. 证明 结合\(\eqref{*}\)，只需注意到以下对应关系：

\[\rho(f|S_1=\varnothing) = a_0 \]

由定理 8.4即可证明。

$\square$