費氏數列的特性 (3)

延伸這篇以費氏數列表示費氏數列的想法，可以找出費氏數列和巴斯卡三角形的關係。我沒仔細讀WikiPedia上的說明，好像有些差異，單純自high地記錄找到的關係。

將費氏數列拆成費氏數列的和，並用vector表示各項費氏數列係數的話，容易觀察出巴斯卡三角的特性，這裡只是示意表示，最左邊的欄位表示F(n)的係數，左邊數來第二欄表示F(n-1)的係數，以此類推：

F(n) = [1, 0]
F(n) = [0, 1, 1]
F(n) = [0, 0, 1, 2, 1]
F(n) = [0, 0, 0, 1, 3, 3, 1]
F(n) = [0, 0, 0, 0, 1, 4, 6, 4, 1]

舉例來說，F(n)可以看成 1*F(n-4) + 4*F(n-5) + 6*F(n-6) + 4*F(n-7) + 1*F(n-8)，以 n = 9代入為例，即為34 = 1*5 + 4*3 + 6*2 + 4*1 + 1*1。