斐波那契数

[（ヅ）]

证明or证伪:

如果a | b，则 Fib(a) | Fib(b)

Fib(a) 为第a个Fibonacci数. Fib(1) = Fib(2) = 1

[Caravel]

a | b是什么操作？

[YWY]

a | b是什么操作？

a | b 就是a整除b的意思。一楼的问题我这就去写证明，我刚想到一个“妙法”。

[tfusion]

书直觉这个就不对。

[YWY]

证明or证伪:

如果a | b，则 Fib(a) | Fib(b)

Fib(a) 为第a个Fibonacci数. Fib(1) = Fib(2) = 1

Let f(n) denote the n-th Fibonacci number. Let a be a natural number. We are going to prove f(a) | f(na) for all non-negative integer n. (In fact, f(a) | f(na) for all integers (positive or negative), with similar proof.)

Proof. Induct on n. When n = 0 or 1, the claim is clear. Assume the claim holds for n = k, i.e., f(a) | f(ka). Next, we consider integers modulo f(a). Thus, f(ka) = 0. Denote f(ka -1) by x. Then (again, modulo f(a)) we have f(ka+1) = f(ka-1)+f(ka) = f(ka-1) + 0 = f(ka-1) = x = f(1)x. Hence, f(ka+2) = f(ka) + f(ka+1) = 0 + f(ka+1) = x = f(2)x. Similarly, mod f(ka), we see f(ka+3) = f(ka+1) + f(ka+2) = x + x = 2x = f(3)x. Now, it is not hard to see that f(ka + i) = f(i)x, mod f(a), for all i. Thus, mod f(a), we see f((k+1)a) = f(ka + a) = f(a)x = 0, which simply says that f(a) divides f((k+1)a). This concludes the induction process. QED.

[nk]

Let f(n) denote the n-th Fibonacci number. Let a be a natural number. We are going to prove f(a) | f(na) for all non-negative integer n. (In fact, f(a) | f(na) for all integers (positive or negative), with similar proof.)

Proof. Induct on n. When n = 0 or 1, the claim is clear. Assume the claim holds for n = k, i.e., f(a) | f(ka). Next, we consider integers modulo f(a). Thus, f(ka) = 0. Denote f(ka -1) by x. Then (again, modulo f(a)) we have f(ka+1) = f(ka-1)+f(ka) = f(ka-1) + 0 = f(ka-1) = x = f(1)x. Hence, f(ka+2) = f(ka) + f(ka+1) = 0 + f(ka+1) = x = f(2)x. Similarly, mod f(ka), we see f(ka+3) = f(ka+1) + f(ka+2) = x + x = 2x = f(3)x. Now, it is not hard to see that f(ka + i) = f(i)x, mod f(a), for all i. Thus, mod f(a), we see f((k+1)a) = f(ka + a) = f(a)x = 0, which simply says that f(a) divides f((k+1)a). This concludes the induction process. QED.

这个做得非常完美。点赞。

[YWY]

这个做得非常完美。点赞。

谢！我估计是我以前某个时候看过这个证明，今天歪打正着，碰巧看到了这个题。。。

[（ヅ）]

Let f(n) denote the n-th Fibonacci number. Let a be a natural number. We are going to prove f(a) | f(na) for all non-negative integer n. (In fact, f(a) | f(na) for all integers (positive or negative), with similar proof.)

Proof. Induct on n. When n = 0 or 1, the claim is clear. Assume the claim holds for n = k, i.e., f(a) | f(ka). Next, we consider integers modulo f(a). Thus, f(ka) = 0. Denote f(ka -1) by x. Then (again, modulo f(a)) we have f(ka+1) = f(ka-1)+f(ka) = f(ka-1) + 0 = f(ka-1) = x = f(1)x. Hence, f(ka+2) = f(ka) + f(ka+1) = 0 + f(ka+1) = x = f(2)x. Similarly, mod f(ka), we see f(ka+3) = f(ka+1) + f(ka+2) = x + x = 2x = f(3)x. Now, it is not hard to see that f(ka + i) = f(i)x, mod f(a), for all i. Thus, mod f(a), we see f((k+1)a) = f(ka + a) = f(a)x = 0, which simply says that f(a) divides f((k+1)a). This concludes the induction process. QED.

赞，这个想法很好

我自己的做法是用通项公式

s = (sqrt(5) + 1) / 2

F(n) = (s^n - (-s)^{-n}) / (2s-1)

如果n = pq,那么F(n) = F(p)*(s^{q-1} + s^{q-2}(-s)^{-1} +... + s(-s)^{-(q-2)} + (-s)^{-(q-2)})

然后利用性质s^i + (-s)^{-i} 为整数

[YWY]

赞，这个想法很好

我自己的做法是用通项公式

s = (sqrt(5) + 1) / 2

F(n) = (s^n - (-s)^{-n}) / (2s-1)

如果n = pq,那么F(n) = F(p)*(s^{q-1} + s^{q-2}(-s)^{-1} +... + s(-s)^{-(q-2)} + (-s)^{-(q-2)})

然后利用性质s^i + (-s)^{-i} 为整数

好！