作者JKLee (J.K.Lee)
看板Grad-ProbAsk
标题Re: [理工] 离散_两题证明
时间Fri Jul 26 15:25:53 2019
※ 引述《fmtshk (fmtshk)》之铭言：
: https://i.imgur.com/DnhrSuE.jpg
: 如图，可能这两小题很基本讲义上没给详解，1小题我没证出来，乱写了一些
: https://i.imgur.com/RuN5sAK.jpg
: 求大佬给个提示
: 2小题麻烦帮我看下是否有错
: https://i.imgur.com/UiINdmd.jpg
看起来没错
---
第一小题
证: F(n)*F(n+3) - F(n+1)*F(n+2) = (-1)^(n-1)
---
解:
Lemma 1
Let M = [1 1] , then
[1 0]
M * [F(n) ] = [F(n+1)]
[F(n-1)] [F(n) ]
and
M^n * [F(1)] = [F(n+1)]
[F(0)] [F(n) ]
---
L.H.S. = det[ F(n+3) F(n+1) ]
[ F(n+2) F(n) ]
= det[ [F(n+3)] [F(n+1)] ]
[ [F(n+2)] , [F(n) ] ]
= det[ M^n * [F(3)] , M^n * [F(1)] ]
[ [F(2)] [F(0)] ]
= det( M^n * [F(3) F(1)] )
[F(2) F(0)]
= det(M^n) * det[F(3) F(1)]
[F(2) F(0)]
= det(M)^n * det[2 1]
[1 0]
= (-1)^n * (-1)
= (-1)^(n+1)
= R.H.S.
---
第二小题也可以用这个方法
---
keyword: 矩阵, 费氏数列, Fibonacci number
参考资料:
直接从矩阵推导费氏数列 O(LogN) 的公式解 - fcamel的程式开发心得 - Medium
medium.com/fcamels-notes/直接从矩阵推导费氏数列-o-logn-的公式解
-e091362a275
短网址
https://reurl.cc/aOxo7
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.248.65.154 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1564125955.A.72E.html
※ 编辑: JKLee (111.248.65.154 台湾), 07/26/2019 15:59:12
1F：→ fmtshk: 谢谢，我研究一下 07/27 02:15
※ 编辑: JKLee (111.248.65.154 台湾), 07/27/2019 15:06:26