0
0

寻找相邻两项之比不趋于 1.618 的广义 Fibonacci 数列

admin 发表于 2014年08月14日 20:18 | Hits: 1632
Tag: 数列 | 抽象代数 | 线性代数 | Uncategorized | 趣题 | 证明

大家或许知道 Fibonacci 数列 1, 1, 2, 3, 5, 8, … 有一个非常漂亮的性质:数列中的相邻两项之比将会越来越接近黄金比例 (1 + √5) / 2 ≈ 1.618 。事实上,如果我们用 F(n) 来表示第 n 个 Fibonacci 数的话,那么当 n → ∞ 时,我们有 F(n + 1) / F(n) → (1 + √5) / 2 。

不过,可能有人并不知道,如果把 Fibonacci 数列的前两项换成两个其他的正整数(但保持 Fibonacci 数列的递推关系不变),由此所得的广义 Fibonacci 数列当中,相邻两项之比仍然会趋近于 (1 + √5) / 2 。比方说,如果数列的前两项为 7, 2 ,那么整个数列的前 15 项以及相邻两项之比的情况如下:

7, 2, 9, 11, 20, 31, 51, 82, 133, 215, 348, 563, 911, 1474, 2385, …
 
2 / 7 = 0.28571429…
9 / 2 = 4.5
11 / 9 = 1.2222222…
20 / 11 = 1.8181818…
31 / 20 = 1.55
51 / 31 = 1.6451613…
82 / 51 = 1.6078431…
133 / 82 = 1.6219512…
215 / 133 = 1.6165414…
348 / 215 = 1.6186047…
563 / 348 = 1.6178161…
911 / 563 = 1.6181172…
1474 / 911 = 1.6180022…
2385 / 1474 = 1.6180461…

更神奇的是,即使最前面这两个数当中有一个负数或者都是负数,相邻两项之比的趋势依旧不变!举个例子,若数列的开头两项是 20 和 -13 ,则有:

20, -13, 7, -6, 1, -5, -4, -9, -13, -22, -35, -57, -92, -149, -241, …
 
(-13) / 20 = -0.65
7 / (-13) = -0.53846154
(-6) / 7 = -0.85714286
1 / (-6) = -0.16666667
(-5) / 1 = -5
(-4) / (-5) = 0.8
(-9) / (-4) = 2.25
(-13) / (-9) = 1.4444444
(-22) / (-13) = 1.6923077
(-35) / (-22) = 1.5909091
(-57) / (-35) = 1.6285714
(-92) / (-57) = 1.6140351
(-149) / (-92) = 1.6195652
(-241) / (-149) = 1.6174497

事实上,不管数列的开头两项是多么奇怪的两个实数(比如 -7/2, √2, … 或者 π/10, -√e, … 等等),按照 Fibonacci 式的递推关系算出后面各项,相邻两项之比几乎总会趋于 (1 + √5) / 2 !注意,刚才我们使用了“几乎”一词,因为这个结论其实并不总是成立。今天的题目就是:请你找出至少一个反例。也就是说,你需要找出至少一个由递推关系 a(i) = a(i – 1) + a(i – 2) 生成的数列,使得当 n 趋于无穷大时 a(n + 1) / a(n) 并不趋于 (1 + √5) / 2 。

对了, 0, 0, 0, 0, 0, … 这种情况自然不算。

 

为了方便起见,接下来我们把 (1 + √5) / 2 记作 φ ,它约等于 1.618 ;再把 (1 – √5) / 2 记作 φ’ ,它约等于 -0.618 。容易看出, φ 和 φ’ 是方程 1 + x = x2的两根。如果数列的开头两项是 1 和 φ’ 的话,这个数列会是什么样呢?由于 1 + φ’ = φ’2,因此数列的下一项是 φ’2;由于 φ’ + φ’2= φ’ · (1 + φ’) = φ’ · φ’2= φ’3,因此数列的下一项是 φ’3;由于 φ’2+ φ’3= φ’2· (1 + φ’) = φ’2· φ’2= φ’4,因此数列的下一项是 φ’4……不断这样推下去,大家很快便会发现,整个数列其实就是这样:

1, φ’, φ’2, φ’3, φ’4, φ’5, φ’6, …

毫无疑问,这个数列的相邻两项之比永远是 φ’ = (1 – √5) / 2 ,并不会慢慢趋近于 φ = (1 + √5) / 2 。这就是一个满足要求的反例。万事开头难,有了第一个反例,再找更多的反例就不是难事了。比方说,所有以 c, c · φ’, … 开头的数列全都一并成为了反例,其中 c 可以是任意一个非 0 实数。

有趣的是,除此之外,再也没有其他的反例了。换句话说,如果你把相差一个系数的广义 Fibonacci 数列看作本质上相同的数列,那么刚才我们给出的反例是唯一的。下面我们就来证明这一点。

 

首先注意到,让广义 Fibonacci 数列里的每一项都乘上非 0 实数 c ,得到的仍然是一个广义 Fibonacci 数列。也就是说,如果数列

a(1), a(2), a(3), a(4), a(5), …

是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列,那么

c · a(1), c · a(2), c · a(3), c · a(4), c · a(5), …

就是一个由 c · a(1) 和 c · a(2) 生成的广义 Fibonacci 数列。

另外,两个广义 Fibonacci 数列之和必然也是一个广义 Fibonacci 数列。也就是说,如果数列

a(1), a(2), a(3), a(4), a(5), …

是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列,并且数列

b(1), b(2), b(3), b(4), b(5), …

是一个由 b(1) 和 b(2) 生成的广义 Fibonacci 数列,那么数列

a(1) + b(1), a(2) + b(2), a(3) + b(3), a(4) + b(4), a(5) + b(5), …

就是一个由 a(1) + b(1) 和 a(2) + b(2) 生成的广义 Fibonacci 数列。

最后别忘了,刚才我们说过, φ 和 φ’ 是方程 1 + x = x2的两根,因而数列

1, φ, φ2, φ3, φ4, φ5, φ6, …

1, φ’, φ’2, φ’3, φ’4, φ’5, φ’6, …

就成了两个非常特别的广义 Fibonacci 数列。

 

把上面三点结合起来,我们将会得出结论:一切广义 Fibonacci 数列都可以表示成

k + l, k · φ + l · φ’, k · φ2+ l · φ’2, k · φ3+ l · φ’3, k · φ4+ l · φ’4, k · φ5+ l · φ’5, …

的形式,其中 k 和 l 是两个适当的常数。例如,为了把经典的 Fibonacci 数列

1, 1, 2, 3, 5, 8, …

表示成刚才那种形式,我们只需要找出合适的 k 和 l ,使得它们同时满足

k + l = 1, k · φ + l · φ’ = 1

这两个方程。解得 k = φ / √5, l = – φ’ / √5,因而 Fibonacci 数列实际上就是

(φ / √5) – (φ’ / √5), (φ / √5) · φ – (φ’ / √5) · φ’, (φ / √5) · φ2– (φ’ / √5) · φ’2, (φ / √5) · φ3– (φ’ / √5) · φ’3, …

或者干脆写作

(φ – φ’) / √5, (φ2– φ’2) / √5, (φ3– φ’3) / √5, (φ4– φ’4) / √5, …

这正是 Fibonacci 数列的通项公式。类似地,为了求出广义 Fibonacci 数列

20, -13, 7, -6, 1, -5, -4, -9, -13, -22, …

的通项公式,我们只需要求解关于 k 和 l 的二元一次方程组

k + l = 20, k · φ + l · φ’ = -13

解得 k = 10 – 23 / √5, l = 10 + 23 / √5,因而该数列其实就是

(10 – 23 / √5) + (10 + 23 / √5), (10 – 23 / √5) · φ + (10 + 23 / √5) · φ’, (10 – 23 / √5) · φ2+ (10 + 23 / √5) · φ’2, (10 – 23 / √5) · φ3+ (10 + 23 / √5) · φ’3, …

 

注意, φ 是一个绝对值大于 1 的数, φ’ 是一个绝对值小于 1 的数,因而随着 n 的增加, φn很快便会变得非常非常大,同时 φ’n也会很快变得非常非常接近于 0 。因此,就算 k 的绝对值再小,就算 l 的绝对值再大, k · φn+ l · φ’n的值也会很快变得和 k · φn几乎相同,相邻两项之比基本上就相当于是 k · φn+1和 k · φn之比,自然也就等于 φ 了。除非……除非 k 等于 0 !因此,广义 Fibonacci 数列的相邻两项之比不趋于 φ 的情况仅此一种,此时整个数列实际上为:

l, l · φ’, l · φ’2, l · φ’3, l · φ’4, l · φ’5, …

 

最近在 reddit 上看到了这个帖子,网友 Gro-Tsen 的回复让人有醍醐灌顶之感,故写此文记之。

原文链接: http://www.matrix67.com/blog/archives/6063

0     0

评价列表(0)