34408 幾道美國大學生數學競賽題的一般形式
幾道美國大學生數學競賽題的一般形式

摘要: 給出幾道美國大學生數學競賽題的一般性結論並說明其應用。

關鍵詞: Putnam 數學競賽, 數列極限, Stolz 定理, 收斂速度。

歷屆美國大學生數學競賽 (The William Lowell Putnam Mathematical Competition) 有這樣幾道試題:

一、第 7 屆 (1947 年) A$-$1 題

設數列 $\{a_n\}$ 滿足條件 $$ (2-a_n) a_{n+1} = 1, \quad n \ge 1, $$ 試證: 當 $n\to\infty$ 時, $\lim\limits_{n\to\infty} a_n$ 存在且等於 1。

二、第 27 屆 (1966 年) A$-$3 題

設 $0\lt x_1\lt 1$ 而 $x_{n+1}=x_n(1-x_n)$, $n=1, 2, \ldots$, 求證: $\lim\limits_{n\to\infty} nx_n=1$。

三、第 67 屆 (2006 年) B$-$6 題

設 $k$ 為大於 1 的整數, 若 $a_0\gt 0$ 且定義: $$ a_{n+1} = a_n + \frac{1}{\root k\of a_n}, n = 0, 1, 2, \ldots, \quad \hbox{求 }~ \lim_{n\to\infty} \frac{a_n^{k+1}}{n^k} \hbox{。} $$

本文得到了一個一般性命題, 由此命題可給出這幾道試題的統一解答, 然後通過其他實例再進一步說明此命題的應用。

命題: 設函數 $f(x)$ 在 $[0, +\infty)$ 上連續, 且 $0\le f(x)\lt x$, $x\in(0, +\infty)$。 對任意的 $a_1\ge 0$, 定義數列: $a_{n+1}=f(a_n)$, $n=1, 2, \ldots$。 若存在正數 $m\gt 0$, 使 $$ \lim_{x\to 0^+} \frac{[xf(x)]^m}{x^m-[f(x)]^m} = l \quad \hbox{($l$ 為常數)} $$ 成立, 則 $\lim\limits_{n\to\infty} na_n^m=l$。

證: 因 $0\le f(x)\lt x$, 所以 $0\le a_{n+1}\lt a_n$, 故數列 $\{a_n\}$ 單調遞減且有下界, 從而數列 $\{a_n\}$收斂。 令 $\lim\limits_{n\to\infty} a_n=\lambda$, 則 $\lambda\ge 0$。 由函數 $f(x)$ 連續性知 $\lim\limits_{n\to\infty} a_{n+1}=\lim\limits_{n\to\infty} f(a_n)=f(\lim\limits_{n\to\infty} a_n)$, 即 $\lambda=f(\lambda)$。

又因為 $f(\lambda)\lt \lambda$, 所以 $\lambda=0$, 從而數列單調遞減趨於零。

利用數學分析中著名的施篤茨 (Stolz) 定理, 有 $$ \lim_{n\to\infty} na_n^m = \lim_{n\to\infty} \frac{n}{\displaystyle\frac{1}{a_n^m}} = \lim_{n\to\infty} \frac{n+1-n}{\displaystyle\frac{1}{a_{n+1}^m}-\displaystyle\frac{1}{a_n^m}} = \lim_{n\to\infty} \frac{a_n^m\cdot a_{n+1}^m}{a_n^m-a_{n+1}^m}, $$ 由於 $\lim\limits_{n\to\infty} a_n=0$, $\lim\limits_{n\to\infty} a_{n+1}^m=\lim\limits_{n\to\infty} [f(a_n)]^m$, 故 $$ \lim_{n\to\infty} na_n^m = \lim_{n\to\infty} \frac{a_n^m\cdot a_{n+1}^m}{a_n^m-a_{n+1}^m} = \lim_{x\to 0^+} \frac{[xf(x)]^m}{x^m-[f(x)]^m} = l \hbox{ 。} $$

注: 本命題與文 結論類似, 但這裏所需條件較弱, 證明方法與 也不同。

試題一的解答

由題設知 $a_n\not=0, 2$, $n=2, 3, \ldots$, 所以不妨設 $a_n\not=0, 2$, $n=1, 2, 3, \ldots$ 。

令 $b_n=1-a_n$, $n=1, 2, \ldots$, 則 $b_n\not=\pm 1$, 且由已知關係, 有 $(1+b_n)(1+b_{n+1})=1$, 或 $b_{n+1}=\displaystyle\frac{b_n}{1+b_n}$。

若有某個 $b_k=0$, 則 $b_{k+1}=0$, 由此知當 $n\ge k$ 時, $b_n=0$, 從而 $\lim\limits_{n\to\infty} b_n=0$, $\lim\limits_{n\to\infty} a_n=1$, 結論成立。

以下設 $b_n\not=0$, $n=1, 2, \ldots$ 。

若對一切自然數 $n$ 有 $-1\lt b_n\lt 0$, 則由 $b_{n+1}-b_n=\displaystyle\frac{b_n}{1+b_n}-b_n=-\frac{b_n^2}{1+b_n}$ 及 $1+b_n\gt 0$, $-b_n^2\lt 0$ 知 $b_{n+1}-b_n\lt 0$, 從而數列 $\{b_n\}$ 單調遞減且有下界 $-1$, 從而 $\lim\limits_{n\to\infty} b_n$ 存在。 設 $\lim\limits_{n\to\infty} b_n=b$, 則由 $b_{n+1}=\displaystyle\frac{b_n}{1+b_n}$ 知 $b=0$, 而 $b\le\cdots\le b_{n+1}\lt b_n\lt \cdots\lt b_2\lt b_1$

$\lt 0$, 由此得出矛盾。 因此存在自然數 $k$, 使得 $b_k\gt 0$ 或 $b_k\lt -1$。

若 $b_k\lt -1$, 則由 $b_k+1\lt 0$ 知 $b_{k+1}=\displaystyle\frac{b_k}{1+b_k}\gt 0$, 故對於數列 $\{b_n\}$, 必有自然數 $k$, 使 $b_k\gt 0$, 再由 $b_{k+1}=\displaystyle\frac{b_k}{1+b_k}\gt 0$, 故當 $n\ge k$ 時, $b_n\gt 0$。

由以上分析, 不妨可設 $b_n\gt 0$, $n=1, 2, \ldots$。

在已證命題中取 $m=1$, $f(x)=\displaystyle\frac{x}{1+x}=x(1+x)^{-1}$, 因為 $$ \lim_{x\to 0^+} \frac{xf(x)}{x-f(x)} = \lim_{x\to 0^+} \frac{x^2(1+x)^{-1}}{x-x(1+x)^{-1}} = \lim_{x\to 0^+} \frac{x(1-x+o(x))}{1-(1-x+o(x))} = 1, $$ 所以 $\lim\limits_{n\to\infty} nb_n=1$, 從而 $\lim\limits_{n\to\infty} b_n=\lim\limits_{n\to\infty} \displaystyle\frac{1}{n}=0$, 由此知 $\lim\limits_{n\to\infty} a_n=1$。

注: 我們不僅證明了 $\lim\limits_{n\to\infty} a_n=1$, 而且證明了, 當 $a_n\not=1$ 時, $1-a_n\sim\displaystyle\frac{1}{n}$ $(n\to\infty)$, 即數列 $\{a_n\}$ 收斂於 1 的速度與數列 $\displaystyle\Big\{\frac{1}{n}\Big\}$ 收斂於零的速度相同。

試題二的解答

事實上我們可考慮更一般的結果

設 $0\lt x_1\lt \displaystyle\frac{1}{q}$, 其中 $0\lt q \le 1$, 並且 $x_{n+1}=x_n(1-qx_n)$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} nx_n=\displaystyle\frac{1}{q}$。

在已證命題中取 $m=1$, $f(x)=x-qx^2$, 因為 $$ \lim_{x\to 0^+} \frac{xf(x)}{x-f(x)} = \lim_{x\to 0^+} \frac{x^2-qx^3}{qx^2} = \frac{1}{q}, $$ 所以 $\lim\limits_{n\to\infty} nx_n=\displaystyle\frac{1}{q}$。

特別取 $q=1$, 則有 $\lim\limits_{n\to\infty} nx_n=1$, 此即試題二的答案。

試題三的解答

令 $x_n=\displaystyle\frac{1}{\root k\of a_n}$, 則 $x_n^k=\displaystyle\frac{1}{a_n}$, $a_n=\displaystyle\frac{1}{x_n^k}$, $a_{n+1}=\displaystyle\frac{1}{x_{n+1}^k}$, $n=0, 1, 2, \ldots$ 故由題設

$a_{n+1}=a_n+\displaystyle\frac{1}{\root k\of a_n}$ 知 $$ x_{n+1} = \frac{x_n}{(1+x_n^{k+1})^{\frac{1}{k}}}, \quad n = 0, 1, 2, \ldots \hbox{ 。} $$

在已證的命題中取 $m=k+1$, $f(x)=x(1+x^{k+1})^{-\frac{1}{k}}$, 因為 $$ \lim_{x\to 0^+} \frac{[xf(x)]^{k+1}}{x^{k+1}-[f(x)]^{k+1}}= \lim_{x\to 0^+} \frac{x^{k+1}\Big (x-\displaystyle\frac{1}{k}x^{k+2}+o(x^{k+2})\Big )^{k+1}} {x^{k+1}-\Big (x-\displaystyle\frac{1}{k}x^{k+2}+o(x^{k+2})\Big )^{k+1}} = \frac{k}{k+1}, $$ 所以 $\lim\limits_{n\to\infty} nx_n^{k+1}=\displaystyle\frac{k}{k+1}$,

於是 $\lim\limits_{n\to\infty} n^{-k} x_n^{-k(k+1)}=\displaystyle\Big (1+\frac{1}{k}\Big )^k$,

從而 $\lim\limits_{n\to\infty} \displaystyle\frac{a_n^{k+1}}{n^k}=\displaystyle\Big (1+\frac{1}{k}\Big )^k$。

注: (i) 從解題過程可知, 試題中 $k$ 為大於 1 的整數這一條件可減弱為 $k\gt 0$。

(ii) 特別在 (1) 中取 $k=1$, 可得:

設 $a_1\gt 0$, $a_{n+1}=a_n+\displaystyle\frac{1}{a_n}$, $n=1, 2, \ldots$, 則有 $\lim\limits_{n\to\infty} \displaystyle\frac{a}{\sqrt{2n}}=1$。

本文命題應用舉例

例 1: 設 $x_1\gt 0$, $x_{n+1}=\ln(1+x_n)$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} nx_n=2$。

證: 在已證命題中取 $m=1$, $f(x)=\ln(1+x)$, 因為 $$ \lim_{x\to 0^+} = \frac{xf(x)}{x-f(x)} = \lim_{n\to 0^+} \frac{x \Big (x-\displaystyle\frac{~x^2}{2}+o(x^2)\Big )}{x-\Big (x-\displaystyle\frac{~x^2}{2}+o(x^2)\Big )} = 2, $$ 所以 $\lim\limits_{n\to\infty} nx_n=2$, 從而 $x_n\sim\displaystyle\frac{2}{n}$ $(n\to\infty)$。

例 2: 設 $x_1\gt 0$, $x_{n+1}=\arctan x_n$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} \sqrt{\displaystyle\frac{2n}{3}} x_n=1$。

證: 在已證命題中取 $m=2$, $f(x)=\arctan x$, 因為 $$ \lim_{x\to 0^+} \frac{[xf(x)]^2}{x^2-[f(x)]^2} = \lim_{n\to 0^+} \frac{x^2 \Big (x-\displaystyle\frac{~x^3}{3}+o(x^3)\Big )^2}{x^2-\Big (x-\displaystyle\frac{~x^3}{3}+o(x^3)\Big )^2} = \frac{3}{2}, $$ 所以 $\lim\limits_{n\to\infty} nx_n^2=\displaystyle\frac{3}{2}$, 從而 $\lim\limits_{n\to\infty} \sqrt{\displaystyle\frac{2n}{3}}x_n=1$, 亦即 $x_n\sim\sqrt{\displaystyle\frac{3}{2n}}$ $(n\to\infty)$。

例 3: 設 $x_1\gt 0$, $x_{n+1}=x_n+\sqrt{x_n}$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} \displaystyle\frac{\sqrt{x_n}}{n}=\frac{1}{2}$。

證: 令 $\sqrt{x_n}=\displaystyle\frac{1}{y_n}$, 則由題設 $x_{n+1}=x_n+\sqrt{x_n}$ 知 $y_{n+1}^2=\displaystyle\frac{y_n^2}{1+y_n}$。 由於 $y_n\gt 0$, 故 $y_{n+1}=\displaystyle\frac{y_n}{\sqrt{1+y_n}}$, $n=1, 2, \ldots$ 。

在已證的命題中取 $m=1$, $f(x)=\displaystyle\frac{x}{\sqrt{1+x}}=x(1+x)^{-\frac{1}{2}}$, 因為 $$ \lim_{x\to 0^+} \frac{xf(x)}{x-f(x)} = \lim_{x\to 0^+} \frac{x^2\Big (1-\displaystyle\frac{1}{2}x+o(x)\Big )} {x-x\Big (1-\displaystyle\frac{1}{2}x+o(x)\Big )}=2, $$ 所以 $\lim\limits_{n\to\infty} ny_n=2$, 此即 $\lim\limits_{n\to\infty} \displaystyle\frac{n}{\sqrt{x_n}}=2$, 從而 $\lim\limits_{n\to\infty} \displaystyle\frac{\sqrt{x_n}}{n}=\frac{1}{2}$。

注: (i) 所證極限說明了數列 $\{x_n\}$ 發散到 $+\infty$ 的速度與數列 $\displaystyle\Big\{\frac{n^2}{4}\Big\}$ 發散到 $+\infty$ $(n\to\infty$ 時) 的速度是相同的。

(ii) 本例更一般的情形: 設 $k\gt 1$, 若 $x_1\gt 0$, $x_{n+1}=x_n+x_n^{\frac{1}{k}}$, $n=1, 2, \ldots$, 則有

$\lim\limits_{n\to\infty} \displaystyle\frac{x_n^{k-1}}{n^k}=\Big (1-\frac{1}{k}\Big )^k$。

例 4: 設正數列 $\{a_n\}$ 滿足: $a_{n+1} \sum\limits_{i=1}^n a_i^2=1$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} {\root 3\of {3n}} a_n=1$。

證: 設 $x_n=\sum\limits_{i=1}^n a_i^2$, $n= 1, 2, \ldots$, 由題設知 $a_{n+1}^2 \Big (\sum\limits_{i=1}^n a_i^2\Big )^2=1$, 故有 $(x_{n+1}-x_n)x_n^2=1$, 由此得 $x_{n+1}=x_n+\displaystyle\frac{1}{x_n^2}$, $n=1, 2, \ldots$ 。

再令 $y_n=\displaystyle\frac{1}{x_n}$, 則由 $a_{n+1} \sum\limits_{i=1}^n a_i^2=1$ 及 $x_n=\sum\limits_{i=1}^n a_i^2$ 知 $x_n=\displaystyle\frac{1}{a_{n+1}}$, 從而 $y_n=a_{n+1}$, $n=1, 2, \ldots$, 且有 $$ \frac{1}{y_{n+1}} = \frac{1}{y_n} + y_n^2 = \frac{1+y_n^3}{y_n}, $$ 從而 $y_{n+1}=\displaystyle\frac{y_n}{1+y_n^3}$, $n=1, 2, \ldots$ 。

在已證命題中取 $m=3$, $f(x)=\displaystyle\frac{x}{1+x^3}=x(1+x^3)^{-1}$, 因為 $$ \lim_{x\to 0^+} \frac{[xf(x)]^3}{x^3\!-[f(x)]^3} = \lim_{x\to 0^+} \frac{x^6(1-x^3+o(x^3))^3}{x^3-x^3(1-x^3+o(x^3))^3} = \lim_{x\to 0^+} \frac{x^3(1\!-x^3\!+o(x^3))^3}{1\!-(1\!-x^3\!+o(x^3))^3} = \frac{1}{3}, $$ 所以 $\lim\limits_{n\to\infty} ny_n^3=\displaystyle\frac{1}{3}$, 即有 $\lim\limits_{n\to\infty} (3na_{n+1}^3)=1$, 由此可得 $\lim\limits_{n\to\infty} {\root 3\of {3n}}a_n=1$。

以下問題均可利用本文命題去解, 解題過程留給有興趣的讀者去完成。

問題 1: 設 $0\lt x_1\lt \displaystyle\frac{\pi}{2}$, $x_{n+1}=\sin x_n$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} \sqrt{\displaystyle\frac{n}{3}} x_n=1$。

問題 2: 設 $0\lt x_1\lt 1$, $x_{n+1}=1-e^{-x_n}$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} nx_n=2$。

問題 3: 設 $a_1\gt 0$, $m\gt 1$ 為正整數, $a_{n+1}=\displaystyle\frac{a_n}{\root m\of {1+a_n^m}}$, $n= 1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} \root m\of n a_n=1$。

問題 4: 設 $0\lt x_1\lt \displaystyle\frac{\pi}{2}$, $x_{n+1}=\displaystyle\frac{2(1-\cos x_n)}{x_n}$, $n=1, 2, \ldots$, 證明: $\lim\limits_{n\to\infty} nx_n^2=6$。

參考文獻

劉裔宏, 許康, 吳茂貴, 魏力仁譯, 普特南數學競賽, 長沙: 湖南科學技術出版社, 1983。 The Sixty-seventh William Lowell Putnam Mathematical Competition, The Amer. Math. Monthly 114, No.8, p.716-724, 2007. Jolene Harris and Bogdam Suceavă, Iterational rate of convergence, The Amer. Math. Monthly 115, No.2, 173, 2008. 常庚哲, 史濟懷, 數學分析教程 (第一冊), 南京: 江蘇教育出版社, 1998。

---本文作者任教安徽省合肥工業大學數學系---