费布那西数列Fibonacci

费布那西数列Fibonacci 費布那西數列Fibonacci Sequence公式推導,二, 費氏數列,F= F= 1,F= F+ F。 1 2 n n –1 n–2 < F>,1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , … n 明顯可看出,F、F、F、…均為F的倍數。 69123 欲證明,對一切的自然數m、n,F | F mm n Pf,首先先證明一個常用式,,,F,F+ F,F= F,F+ F,F,乘前加一、乘後減一,pq p–1q–1 p+1q–1 pq–2 證明,F,F+ F,F= F,,F + F,+ F,F pq p–1q–1 pq–1q–2p–1q–1 =,F+ F,,F + F,F p p–1q–1pq–2 = F,F+ F,F得證 p+1q–1 pq–2 接著用數學歸納法來證明,對一切的自然數m、n,F | F mm n (1)當n = 2時,F= F + F= F,F + F,F 2m 2m–12m–2 22m–112m–2 = F,F + F,F,由,, 32m–222m–3 = F,F + F,F,再由,, 42m–332m–4 =… = F,F + F,F,再由,, mm+1m–1m = F,,F + F, mm+1m–1 故得知F | F m2m (2)假設n = k時,F | F,設F = c F,c 為正整數 mk mk mm 當n = k + 1時,F= F + F= F,F + F,F (k+1)m (k+1)m–1(k+1)m–2 2(k+1)m–11(k+1)m–2 = F,F + F,F,由,, 3(k+1)m–22(k+1)m–3 =… = F,F + F,F,再由,, mkm+1m–1km = F,F + F,cF,再由,, mkm+1m–1m = F,,F + cF,也是的倍數F mkm+1m–1m故依數學歸納法得證,對一切的自然數m、n,F | F mm n