新未名空间

证明or证伪:

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

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

a | b是什么操作？

Caravel 写了： 2023年 5月 15日 18:55 a | b是什么操作？

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

书直觉这个就不对。

（ヅ） 写了： 2023年 5月 15日 14:21 证明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.

YWY 写了： 2023年 5月 15日 19:29 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.

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

newkids_on_the_block 写了： 2023年 5月 15日 20:40 这个做得非常完美。点赞。

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

YWY 写了： 2023年 5月 15日 19:29 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} 为整数

（ヅ） 写了： 2023年 5月 16日 14:58 赞，这个想法很好

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

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} 为整数

好！