Re: [理工] 離散_兩題證明
: 如圖，可能這兩小題很基本講義上沒給詳解，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://www.ptt.cc/bbs/Grad-ProbAsk/M.1564125955.A.72E.html
※ 編輯: JKLee (111.248.65.154 臺灣), 07/26/2019 15:59:12
→
07/27 02:15,
4年前
, 1F
07/27 02:15, 1F
※ 編輯: JKLee (111.248.65.154 臺灣), 07/27/2019 15:06:26
討論串 (同標題文章)
