發新話題
打印

費式數列的數學歸納法證明

費式數列的數學歸納法證明

Consider the recurrence relation for Fibonacci numbers \(F(n)=F(n-1)+F(n-2)\). Without solving this recurrence, compare \(F(n)\) to \(G(n)\) defined by the recurrence \(G(n)=G(n-1)+G(n-2)+1\). It seems obvious that \(G(n)>F(n)\)(because of the extra 1). Yet the following is a seemingly valid proof(by induction) that \(G(n)=F(n)-1\). We assume, by induction, that \(G(k)=F(k)-1\) for all \(k\) such that \(1\le k \le n\), and we consider \(G(n+1)\):
\(G(n+1)=G(n)+G(n-1)+1=F(n)-1+F(n-1)-1+1=F(n+1)-1\)
What is wrong with this proof?
請各位老師幫忙  謝謝
(看不出哪裡有錯誤)

TOP

回復 1# P78961118 的帖子

上面的數學歸納法漏掉了檢查初始值的步驟。

而且 \(G(n)\) 數列的遞迴定義式也沒有定義初始條件。

多喝水。

TOP

發新話題