数学-齐肯多夫定理

发表于 2020-12-01 更新于 2020-12-02 分类于学习

本文字数： 589 阅读时长 ≈ 1 分钟

任何正整数都可以表示为若干个不连续的斐波那契数（不包括第一个斐波那契数）之和，这种和式称为齐肯多夫表述法

以 $F (n)$ 来表示第 $n$ 个斐波那契数， $m$ 为任意正整数

当 $m = 1, 2, 3$ 时，由 $F (2) = 1, F (3) = 2, F (4) = 3$ ，则命题成立，下面采用数学归纳法证明定理对任何 $m$ 均成立

1.若 $m$ 是斐波那契数，则 $m$ 命题对成立

2.若 $m$ 不是斐波那契数，设 $n_{1}$ 是满足 $F (n_{1}) < m < F (n_{1} + 1)$ 的最大正整数

设 $m_{c} = m - F (n_{1})$ ，则 $m_{c} = m - F (n_{1}) < F (n_{1} + 1) - F (n_{1}) = F (n_{1} - 1)$ ，即 $m_{c} < F (n_{1} - 1)$

由归纳假设， $m_{c}$ 可以表示为不连续的斐波那契数之和，即 $m_{c} = F (n_{2}) + F (n_{3}) + \dots + F (n_{t})$

其中 $n_{2} > n_{3} > \dots > n_{t}$ 且是不连续整数

又 $m_{c} < F (n_{1} - 1)$ ，所以 $n_{2} < n_{1} - 1$ ，即 $n_{2}$ 与 $n_{1}$ 也是不连续的整数

故 $m = F (n_{1}) + m_{c} = F (n_{1}) + F (n_{2}) + F (n_{3}) + \dots + F (n_{t})$ 且 $n_{1} > n_{2} > n_{3} > \dots > n_{t}$ 是不连续的整数

因此命题对 $m$ 也成立

综上，由数学归纳法，齐肯多夫定理对任何正整数 $m$ 都成立