高中奥数 2022-02-09

作者: 不为竞赛学奥数 | 来源:发表于2022-02-09 08:09 被阅读0次

高中奥数 2022-02-09
奥数！奥数！
高中奥数 2022-03-16
高中奥数 2022-03-14
高中奥数 2022-02-17
高中奥数 2022-02-24
高中奥数 2022-02-25
高中奥数 2022-03-11
高中奥数 2022-03-10
高中奥数 2022-03-13

2022-02-09-01

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚先猜后证 P085 例03）

整数数列 $\left\{a_{n}\right\}$ 定义如下 $a_{1}=2$ , $a_{2}=7$ ,
$-\dfrac{1}{2}<a_{n+1}-\dfrac{a_{n}^{2}}{a_{n-1}}\leqslant \dfrac{1}{2}n=2,3\cdots.$
求数列 $\left\{a_{n}\right\}$ 的通项公式.

解

题设所给的递推式难以确定 $a_{n}$ 能否由条件得出我们熟悉的常系数线性递推式呢?大胆猜测 $a_{n+1}=pa_{n}+q_{n-1}$ , $p$ 、 $q$ 为待定的常数.

试算该数列的前面几项,可知 $a_{1}=2$ , $a_{2}=7$ , $a_{3}=25$ , $a_{4}=89$ , $\cdots$ .确定猜测中的 $p$ 、 $q$ 的值,猜想 $a_{n+1}=3a_{n}+2a_{n-1}$ , $n\geqslant 2$ .

下面用数学归纳法证明上述猜想.

当 $n=2$ 、 $3$ 时,上述猜想成立.

设对 $k\leqslant n$ 时,都有 $a_{k+1}=3a_{k}+2a_{k-1}$ ;立.则对 $k=n+1$ 的情形,我们有
$\dfrac{a_{n+1}^{2}}{a_{n}}=\dfrac{a_{n+1}\left(3a_{n}+2a_{n-1}\right)}{a_{n}}=3a_{n+1}+2a_{n}+2\left(\dfrac{a_{n+1}a_{n-1}-a_{n}^{2}}{a_{n}}\right).$
注意到
$\begin{aligned} \left|2\left(\dfrac{a_{n+1}a_{n-1}-a_{n}^{2}}{a_{n}}\right)\right|&=\left|\dfrac{2a_{n-1}}{a_{n}}\right|\left|a_{n+1}-\dfrac{a_{n}^{2}}{a_{n-1}}\right|\\ &\leqslant \dfrac{1}{2}\left|\dfrac{2a_{n-1}}{a_{n}}\right|. \end{aligned}$
由归纳假设,可知 $a_{n}>2a_{n-1}$ .所以
$\left|3a_{n+1}+2a_{n}-\dfrac{a_{n+1}^{2}}{a_{n}}\right|<\dfrac{1}{2}.$
利用 $a_{n+2}$ 为整数,且 $\left|a_{n+2}-\dfrac{a_{n+1}^{2}}{a_{n}}\right|\leqslant \dfrac{1}{2}$ ,得
$\begin{aligned} &\left|a_{n+2}-\left(3a_{n+1}+2a_{n}\right)\right|\\ =&\left|a_{n+2}-\dfrac{a_{n+1}^{2}}{a_{n}}\right|+\left|\dfrac{a_{n+1}^{2}}{a_{n}}-\left(3a_{n+1}+2a_{n}\right)\right|\\ <&\dfrac{1}{2}+\dfrac{1}{2}\\ =&1. \end{aligned}$
所以 $a_{n+2}=3a_{n+1}+2a_{n}$ .于是猜想对 $k=n+1$ 的情形成立.

综上可知,数列 $\left\{a_{n}\right\}$ 满足 $a_{1}=2$ , $a_{2}=7$ , $a_{n}=3a_{n-1}+2a_{n-2},n=3,4,\cdots$ .利用特征方程求解这个常系数齐次线性递推式,可得
$a_{n}=\dfrac{17+5\sqrt{17}}{68}\left(\dfrac{3+\sqrt{17}}{2}\right)^{n}+\dfrac{17-5\sqrt{17}}{68}\left(\dfrac{3-\sqrt{17}}{2}\right)^{n}.$

2022-02-09-02

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚先猜后证 P086 例04）

函数 $f:\mathbb{N}^{*}\rightarrow \mathbb{N}^{*}$ 定义如下 $f\left(1\right)=1$ ,对 $n\in \mathbb{N}^{*}$ ,数 $f\left(n+1\right)$ 是满足下述条件的最大正整数 $m$ :存在一个由正整数组成的等差数列 $a_{1},a_{2},\cdots ,a_{m}$ (这里项数小于3的数列也认为是等差数列),使得 $a_{1}<a_{2}<\cdots <a_{m}=n$ ,并且 $f\left(a_{1}\right)=f\left(a_{2}\right)=\cdots=f\left(a_{m}\right)$ .证明:对任意正整数 $n$ ,都有 $f\left(4n+8\right)=n+2$ .

证明

题目并不要求确定每一个n的函数值,但从f的定义来看,只有每个 $f\left(n\right)$ 的值都确定后才能方便地求出下一个值.

利用 $f$ 的定义作初始值的计算,可知
$\begin{aligned} &f(1)=1, f(2)=1, f(3)=2, f(4)=1, f(5)=2, f(6)=2, \\ &f(7)=2, f(8)=3, f(9)=1, f(10)=2, f(11)=2, f(12)=3, \\ &f(13)=2, f(14)=3, f(15)=2, f(16)=4, f(17)=1, f(18)=3, \\ &f(19)=2, f(20)=5, f(21)=1, f(22)=2, f(23)=2, f(24)=6, \\ &f(25)=1, f(26)=4, f(27)=2, f(28)=7, f(29)=1, f(30)=4, \\ &f(31)=2, f(32)=8, f(33)=1, f(34)=5, f(35)=2, f(36)=9, \\ &\ldots \ldots . \end{aligned}$
这些数据的列出不仅说明了当 $1\leqslant n\leqslant 7$ 时,有 $f\left(4n+8\right)=n+2$ ,进一步,还促使我们猜测当 $n\geqslant 8$ 时,有
$\left(4n+1\right)=1;f\left(4n+2\right)=n-3;f\left(4n+3\right)=2;f\left(4n+4\right)=n+1.\qquad(*)$
下面对 $n$ 归纳来证: $n\geqslant 8$ 时, $(*)$ 都成立.

当 $n=8$ 时,利用所列出的数据可知 $(*)$ 成立.

现设 $(*)$ 对 $8,9,\cdots ,n-1$ 都成立,考察 $n\left(\geqslant 9\right)$ 的情形.

利用所算得的 $f\left(1\right)$ 至 $f\left(36\right)$ 值结合归纳假设可知 $f\left(4n\right)=n$ 是 $f\left(1\right),f\left(2\right),\cdots ,f\left(4n\right)$ 中最大的数,所以 $f\left(4n+1\right)=1$ .

现在考察 $f\left(1\right)$ 至 $f\left(4n+1\right)$ 中等于1的项,可知 $f\left(17\right)=f\left(21\right)=\cdots=f\left(4n+1\right)=1$ ,结合 $f$ 的定义得 $f\left(4n+2\right)\geqslant n-3$ .另一方面,对于以 $4n+1$ 为末项的等差数列 $a_{1}<a_{2}<\cdots <a_{m}\left(=4n+1\right)$ ,若 $f\left(a_{1}\right)=\cdots=f\left(a_{m}\right)=1$ ,则该数列的公差 $d\geqslant 4$ (因为若 $d\leqslant 3$ ,则 $f\left(4n-2\right)$ , $f\left(4n-1\right)$ , $f\left(4n\right)$ , $f\left(4n+1\right)$ 中应有至少两个等于1,但由归纳假设,这4个数中只有 $f\left(4n+1\right)=1$ ),如果 $d>4$ ,那么由归纳假设及所列 $f\left(1\right)$ 至 $f\left(36\right)$ 的值可知 $d\geqslant 8$ ,此时 $m\leqslant 1+\dfrac{\left(4n+1\right)-1}{8}<n-3$ .因此 $f\left(4n+2\right)=n-3$ .

再考察 $f\left(1\right)$ 到 $f\left(4n+2\right)$ 的值,仅有 $f\left(4n-12\right)=f\left(4n+2\right)=n-3$ (这里用到 $n\geqslant 9$ ),从而 $f\left(4n+3\right)=2$ .

最后,与讨论 $f\left(4n+2\right)$ 的值类似,可知 $f\left(4n+4\right)=n+1$ .

所以,对任意 $n\in \mathbb{N}^{*}\left(n\geqslant 8\right)$ , $(*)$ 都成立.进而,对任意 $n\in \mathbb{N}^{*}$ ,都有 $f\left(4n+8\right)=n+2$ .

说明
要猜出规律性的结果,每个问题需要试算的初始值个数不尽相同,仔细与信心都很重要.

2022-02-09-03

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚先猜后证 P087 例05）

对任意 $n\in \mathbb{N}^{*}$ ,记 $\rho\left(n\right)$ 为满足 $2^{k}\mid n$ 且 $2^{k+1}\nmid n$ 的非负整数 $k$ .

数列 $\left\{x_{n}\right\}$ 定义如下
$x_{0}=0,\dfrac{1}{x_{n}}=1+2 \rho\left(n\right)-x_{n-1}x_{0}=0,n=1,2,\cdots$
证明:每一个非负有理数恰好在数列 $x_{0},x_{1},\cdots$ 中出现一次.

证明

如果写 $x_{n}=\dfrac{p_{n}}{q_{n}}\left(p_{n},q_{n}\in \mathbb{N}^{*},\left(p_{n},q_{n}\right)=1\right)$ ,那么条件式为
$\dfrac{q_{n}}{p_{n}}=\left(1+2\rho\left(n\right)\right)-\dfrac{p_{n-1}}{q_{n-1}}.$
去分母在 $p_{n}=q_{n-1}$ 时是最方便的.这个猜测引出了下面的证明.

定义数列 $\left\{y_{n}\right\}$ 如下 $y_{1}=y_{2}=1$ ,
$y_{r+2}=\left(1+2\rho\left(n\right)\right)y_{n+1}-y_{n},n=1,2,\cdots.$
我们依次建立下述结论.

结论1对任意 $n\in \mathbb{N}^{*}$ ,都有 $x_{n}=\dfrac{y_{n}}{y_{n+1}}$ .

对 $n$ 归纳予以证明.归纳过渡可依如下方式进行
$\begin{aligned} \dfrac{1}{x_{n+1}}&=1+2\rho\left(n+1\right)-x_{n}\\ &=1+2\rho\left(n+1\right)-\dfrac{y_{n}}{y_{n+1}}\\ &=\dfrac{1}{y_{n+1}}\left(\left(1+2\rho\left(n+1\right)\right)y_{n+1}-y_{n}\right)\\ &=\dfrac{y_{n+2}}{y_{n+1}}, \end{aligned}$
故 $x_{n+1}=\dfrac{y_{n+1}}{y_{n+2}}$ .

结论2

对任意 $n\in \mathbb{N}^{*}$ ,都有
$y_{2n+1}=y_{n+1}+y_{n},y_{2n}=y_{n}.$
对 $n$ 归纳予以证明.事实上,若结论2对 $n$ 成立,那么
$y_{2n+2}=\left(1+2\rho\left(2n+1\right)\right)y_{2n+1}-y_{2n}=y_{2n+1}-y_{n}=y_{n+1};$
$\begin{aligned} y_{2n+3}&=\left(1+2\rho\left(2n+2\right)\right)y_{2n+2}-y_{2n+1}\\ &=\left(1+2\left(1+\rho\left(n+1\right)\right)\right)y_{2n+2}-y_{2n+1}\\ &=2y_{n+1}+\left(1+\rho\left(n+1\right)\right)y_{n+1}-\left(y_{n+1}+y_{n}\right)\\ &=y_{n+1}+\left(1+\rho\left(n+1\right)\right)y_{n+1}-y_{n}\\ &=y_{n+1}+y_{n+2}. \end{aligned}$
依此结合初始情况成立就可知结论2正确.

由结论2结合数学归纳法易证:对任意 $n\in \mathbb{N}^{*}$ ,都有 $\left(y_{n},y_{m+1}\right)=$ 1.

结论3对任意 $p$ 、 $q\in \mathbb{N}^{*}$ , $\left(p,q\right)=1$ .,存在唯一的 $n\in \mathbb{N}^{*}$ ,使得 $\left(p,q\right)=\left(y_{n},y_{n+1}\right)$ .

对 $p+q$ 归纳予以证明.当 $p+q=2$ 时, $p=q=1$ ,此时 $\left(p,q\right)=\left(y_{1},y_{2}\right)$ ,而由结论2知,当 $n\geqslant 2$ 时, $y_{n}$ 与 $y_{n+1}$ 中至少有一个大于1,所以 $\left(y_{n},y_{n+1}\right)\ne \left(y_{1},y_{2}\right)$ ,故结论3对 $p+q=2$ 成立.

现设结论3对所有满足 $p+q<m\left(m\geqslant 3,m\in \mathbb{N}^{*}\right)$ 且 $\left(p,q\right)=1$ 的正整数对 $\left(p,q\right)$ 成立.考虑 $p+q=m$ 的情形,此时 $p\ne q$ ,分 $p<q$ 和 $p>q$ 两种情形讨论.

情形一 $p<q$ ,由 $\left(p,q\right)=1$ ,知 $\left(p,q-p\right)=1$ ,而 $\left(q-p\right)+p=q<m$ ,由归纳假设知,存在唯一的 $n\in \mathbb{N}^{*}$ ,使得 $\left(p,q-p\right)=\left(y_{n},y_{n+1}\right)$ ,这时 $\left(p,q\right)=\left(y_{n},y_{n}+y_{n+1}\right)=\left(y_{2n},y_{2n+1}\right)$ (这里用到结论2).

另一方面,若存在 $k<l$ , $k$ 、 $l\in \mathbb{N}^{*}$ ,使得 $\left(p,q\right)=\left(y_{k},y_{k+1}\right)=\left(y_{l},y_{l+1}\right)$ ,则 $y_{k}=y_{l}$ , $y_{k+1}=y_{l+1}$ .这时如果 $k$ 与 $l$ 都为偶数,那么由结论2可知 $\left(p,q-p\right)$ 有两种不同的表示,与归纳假设矛盾.但是 $k$ 为奇数时, $y_{k}>y_{k+1}$ ,与 $p\neg q$ 矛盾,故 $k$ 只是偶数,同理 $l$ 为偶数.从而,只有一个 $n\in \mathbb{N}^{*}$ ,使得 $\left(p,q\right)=\left(y_{n},y_{r+1}\right)$ .