题解 P1720 【月落乌啼算钱】

蒟蒻Jason周 · 2019-08-13 11:02:08 · 题解

刚拿到这题，乍眼一看，代数式！！！

于是迅速拿起笔在草稿纸上写起

设a=(1+sqrt(5))/2,b=(1-sqrt(5))/2

原式=(a^n-b^n)/sqrt(5)=(a-b)(a^(n-1)+a^(n-2)*b...b^(n-1))

把 a=(1+sqrt(5))/2 , b=(1-sqrt(5))/2 代进式子里

惊奇地发现a-b=1

再把(a^(n-1)+a^(n-2)*b...b^(n-1))算出来就好了

正解我不会

于是开始找规律

n=1:原式=1；

n=2:原式=1；

n=3:原式=2；

n=4:原式=3；

n=5:原式=5；

发现是斐波那契

但是问题又来了，怎么证明呢？

f(n-2)为(x-y)/2

f(n-1)为(xa-yb)/2

f(n)为（xa^2-yb^2）/2

所以f(n)=(x(6+sqrt(10)/4-y(6-sprt(10)/4)/2=((x-y)+(x(1+sqrt(5))/2-y(1-sqrt(5))/2))/2=(x-y)/2+(xa-yb)/2=f(n-2)+f(n-1)

证毕

（观众：你个蒟蒻说那么一大堆废话，快给我滚）

（我：呜呜呜）

所以我就不放代码啦

很水的

我写得那么辛苦，不点个赞再走吗？？？

(っ•̀ω•́)っ✎⁾⁾ 求通过