Fibonacci数列中的偶数除以2

hbghlyj

$a(n)$ 是 Fibonacci数列中的偶数除以2

1. Select[Fibonacci/@Range[30]/2, IntegerQ]

Copy the Code

$a(n)$ 是 $\sqrt5$ 的$n$阶渐近分数的分母。
$a(n)$ 属于 divisibility sequence, 即$n|m⇒a(n)|a(m)$, $\gcd(a(n),a(n+k)) = a(\gcd(n, k))$.
$$a(n)={(2 + \sqrt5)^n - (2 - \sqrt5)^n\over2\sqrt5}$$
oeis.org/A001076

hbghlyj

projecteuler.net/overview=0002
现在让我们看看是否可以摆脱对偶数的测试。
容易证明每第三个斐波那契数都是偶数。
稍微改变一下程序：

1. limit=4000000
2. a=1
3. b=1
4. c=a+b
5. while c<limit:
6.     print(c)
7.     a=b+c
8.     b=c+a
9.     c=a+b

Copy the Code

2
8
34
144
610
2584
10946
46368
196418
832040
3524578
它们遵循以下递归关系：$$E(n)=4E(n-1)+E(n-2).$$
如果我们能证明对于斐波那契数列，公式 $F(n)=4F(n-3)+F(n-6)$ 成立，我们就证明了这个递归。
F(n) = F(n-1) + F(n-2)
= F(n-2)+F(n-3)+F(n-2)=2 F(n-2) + F(n-3)
= 2(F(n-3)+F(n-4))+F(n-3))=3 F(n-3) + 2 F(n-4)
= 3 F(n-3) + F(n-4) + F(n-5) + F(n-6)
= 4 F(n-3) + F(n-6)