高中奥数 2022-01-27

作者: 天目春辉 | 来源:发表于2022-01-27 12:18 被阅读0次

斐波那契(Fibonaccia)数列 $\left\{F_{n}\right\}$ 定义如下

$F_{1}=F_{2}=1,F_{n+2}=F_{n+1}+F_{n},n=1,2,\cdots.$

它是一个非常著名的数列,围绕它展开的讨论层出不穷,有许多有趣而又深刻的结论.

2022-01-27-01

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚斐波那契(Fibonaccia)数列 P057 例01）

证明:对任意 $m,n\in \mathbb{N}^{*}$ ,都有 $\left(F_{m},F_{n}\right)=F_{\left(m,n\right)}$ .即针对Fibonaccia数列的项求最大公因数可以转化到下标上去.

证明

当 $m=n$ 时显然成立.考虑 $m\neq n$ 的情形,不妨设 $m>n$ .

利用Fibonaccia数列的递推式,可知

$\begin{aligned} F_{m}=& F_{m-1}+F_{m-2}=F_{2} F_{m-1}+F_{1} F_{m-2} \\ =& F_{2}\left(F_{m-2}+F_{m-3}\right)+F_{1} F_{m-2} \\ =&\left(F_{2}+F_{1}\right) F_{m-2}+F_{2} F_{m-3} \\ =& F_{3} F_{m-2}+F_{2} F_{m-3} \\ & \cdots \\ =& F_{n} F_{m \backsim+1}+F_{n-1} F_{m-n} . \end{aligned}$

于是 $\left(F_{m},F_{n}\right)=\left(F_{n-1}F_{m-n},F_{n}\right)=\left(F_{m-n},F_{n}\right)$ (这里用到 $\left(Fn-1,F_{n}\right)=1$ ,它可以通过对 $n$ 用数学归纳法证得).

在上面的结论中,用 $\left(m-n,n\right)$ 代替 $\left(m,n\right)$ 继续讨论,表明求 $F_{m}$ 与 $F_{n}$ 的最大公因数的过程实质上是对下标 $m$ 、 $n$ 作辗转相除.所以 $\left(F_{m},F_{n}\right)=F_{\left(m,n\right)}$ .

说明利用本题的结论可证出下述命题:如果 $F_{n}$ 为素数,那么 $n=4$ 或者 $n$ 为素数.

事实上,如果 $n\ne 4$ 且 $n$ 不是素数,那么可写 $n=pq$ , $2\leqslant p\leqslant q$ ,并且 $q\geqslant 3$ .此时 $\left(F_{n},F_{q}\right)=F_{\left(n,q\right)}=F_{q}$ ,而 $F_{q}\geqslant 2$ , $F_{n}>P_{q}$ ,由此导出 $F_{n}$ 为合数.

2022-01-27-02

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚斐波那契(Fibonaccia)数列 P058 例02）

证明:每一个正整数 $m$ ,都可以唯一地表示为如下形式

$\begin{aligned} m&=\left(a_{n}a_{n-1}\cdots a_{2}\right)_{F}\\ &=a_{n}F_{n}+a_{n-1}F_{n-1}+\cdots+a_{2}F_{2}. \end{aligned}\qquad(1)$

这里 $a_{i}=0$ 或 $1$ , $a_{n}=1$ ,并且不存在下标 $2\leqslant i\leqslant n-1$ ,使得 $a_{i}=a_{i-+1}=1$ ,其中 $F_{i}$ 为Fibonaccia数列中的第 $i$ 项.

证明

形如(1)的正整数表示可称为 $m$ 的 $F-$ 表示,它类似于二进制,此结论是著名的Zerkendorf定理.

对 $m$ 归纳来予以证明.

当 $m=1$ 时, $m=F_{2}$ ,命题成立.现设对所有小于 $m$ 的正整数 $k$ 命题都成立.

由于存在唯一的 $n\in \mathbb{N}^{*}$ ,使得 $F_{n}\leqslant m< F_{n+1}$ ,如果 $m-F_{n}=0$ ,那么 $m$ 已表为(1)的形式,如果 $m-F_{n}>0$ ,那么由归纳假设 $m-F_{n}$ 有形如(1)的表示,设

$m-F_{n}=\left(a_{l}a_{l-1}\cdots a_{2}\right)_{F}=a_{l}F_{l}+\cdots+a_{2}F_{2},$

其中 $a_{l}=1$ ,则 $m=F_{n}+a_{l}F_{l}+\cdots+a_{2}F_{2}$ .现在 $l\geqslant n-1$ ,则 $m\geqslant F_{n}+F_{n-1}=F_{n+1}$ ,矛盾,所以 $l\leqslant n-2$ ,从而 $m$ 有满足(1)的表示.

下证 $m$ 的形如(1)的表示是唯一的.

事实上,若

$m=\left(a_{n}\cdots a_{2}\right)_{F}=\left(b_{l}\cdots b_{2}\right)_{F},\qquad(2)$

这里 $a_{n}=b_{l}=1$ ,且 $n\geqslant l$ .

若 $n>l$ ,则由于不存在下标 $1\leqslant i\leqslant l-1$ ,使得 $b_{i}=b_{i+1}=1$ ,结合 $\left\{F_{n}\right\}$ 的定义,可知

$\begin{aligned} \left(b_{l} \cdots b_{2}\right)_{F} & \leqslant\left\{\begin{array}{l} F_{l}+F_{l-2}+\cdots+F_{3}, m \text { 为偶数, } \\ F_{l}+F_{l-2}+\cdots+F_{4}+F_{2}, m \text { 为奇数, } \end{array}\right.\\ &<\left\{\begin{array}{l} F_{l}+F_{l-2}+\cdots+F_{3}+F_{2}=F_{l+1}, m \text { 为偶数, } \\ F_{l}+F_{l-2}+\cdots+F_{4}+F_{2}+F_{1}=F_{l+1}, m \text { 为奇数. } \end{array}\right. \end{aligned}$

因此 $(\left(b_{l}\cdots b_{2}\right)_{F}<F_{l+1}\leqslant F_{n}$ ,故(2)不能都取等式.

所以 $n=l$ ,进而 $m-F_{n}$ 有两种表示,这与归纳假设不符.所以, $m$ 的表示唯一.

综上所述,由第二数学归纳法知,命题成立.

2022-01-27-03

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚斐波那契(Fibonaccia)数列 P058 例03）

熟知任意连续 $n$ 个整数之积是前 $n$ 个正整数之积(即 $n!$ )的倍数.Fibonaccia数列也具有类似的性质.请证明:对任意 $k\in \mathbb{N}^{*}$ ,数列 $\left\{F_{n}\right\}$ 中任意连续 $k$ 项之积都是前 $k$ 项之积的倍数.

证明

引入记号 $\left[n\right]!=F_{1}F_{2}\cdots F_{n}$ , $n=1,2,\cdots$ ,并规定 $f\left[0\right]!=1$ .并写

$R\left(m,n\right)=\dfrac{\left[m+n\right]!}{\left[m\right]!\left[n\right]!},m,n\in \mathbb{N}.$

为证命题成立,只需证明:对任意 $m$ 、 $n\in \mathbb{N}$ ,都有 $R\left(m,n\right)\in \mathbb{N}^{*}$ .

利用例1中类似的推导过程,知

$F_{m+n}=F_{2}F_{m+n-1}+F_{1}F_{m+n-2}=\cdots=F_{m}F_{n+1}+F_{m-1}F_{n},$

所以,我们有

$\begin{aligned} R(m, n) &=\frac{F_{m+n} \cdot[m+n-1] !}{[m] ! \cdot[n] !}\\ &=\frac{F_{m+n} \cdot[m+n-1] !}{F_{m} \cdot F_{n} \cdot[m-1] ! \cdot[n-1] !} \\ &=F_{n+1} \cdot \frac{[m+n-1] !}{[m-1] ! \cdot[n] !}+F_{m-1} \cdot \frac{[m+n-1] !}{[m] ! \cdot[n-1] !} \\ &=F_{n+1} \cdot R(m-1, n)+F_{m-1} \cdot R(m, n-1) . \end{aligned}$

上式对 $m$ 、 $n\in \mathbb{N}^{*}$ 都成立,结合初始情形 $R\left(0,n\right)=R\left(m,0\right)=1$ (对 $m$ 、 $n\in \mathbb{N}$ 都成立)及数学归纳法,即可证明 $R\left(m,n\right)$ 都是正整数.

所以,命题成立.

高中奥数 2022-01-27

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

奥数自学研究