日常生活中，常常會有機智問答，如給定一個數列 $1,2,3,4,5,X$ ，請問下一項$X$是什麼，我們自然會回答 $6$ ，下一項是 $7$ ，事實上我們發現公式可以寫成 $a_k = k \quad k=1,2,3,...$
我們可以定義正式一個問題如下:
--------------------------------------------------------------------------
$(Q)$給定 $n$ 個整數，如何找到 $f$ 使得 $(C) : a_k = f(k) , k = 1,2,3,...n $
--------------------------------------------------------------------------
而根據知識，我們可以找到無窮多個多項式 $f$ 可以滿足$(C)$，而恰好存在唯一一個 $n-1$ 次多項式(polynomial) 可以滿足$(C)$，這問題的連續版本在數值分析(Numerical Analysis)領域稱為 interpolation ，也就是給定 $ S \subset \mathbb{R}^2$，找到一個公式$f$ 使得 $ \forall (x,y) \in S \quad f (x) = y $ [註: 這跟統計上迴歸分析不同的是，interpolation 要完全 fit !!，但是如果存在$(x,y_1),(x,y_2) \in S$,$y_1 \neq y_2$，因為函數無法一對多，則無法使用 interpolation !! ]
而問題$(Q)$ 在筆者讀高中的時候發現的一個公式，會找到一個最低項的多項式(如果只有紙跟筆的話)，分享給讀者~
先定義差分數列 $ b_k = a_{k+1}- a_{k}$ ，$\{b_k\}^{n-1}_{k=1}$ 會比 $a_k$ 少一項，記做 $\{\Delta a_k\}^{n-1}_{k=1}$ ，每做一次差分會少一項。
我們持續做會得到很多差分數列，取它們的第一項，記做 $\vec{a} :=< a_1 , \Delta a_1 , ..... \Delta^{n-1} a_1 >$ 再來定義 $\vec{b}:= <C^{k-1}_0, C^{k-1}_1 , ....C^{k-1}_{n-1} >$
所以 $$f(k) := \vec{a}\cdot \vec{b} = \sum^{n-1}_{i=0}\left[\Delta^{i}a_1 \cdot C^{k-1}_{i} \right] \qquad \text{(Plus & Minus 2007)} $$
[註: 事實上我們只要做到差分數列是常數數列就可以停止了 !! ]
[舉例來說]
如下圖: 給定六個數字 $\{ a_k \}= \{1,2,4,8,15,26\} $
$\{\Delta^{1}a_k\} = \{1,2,4,7,11\}$
$\{\Delta^{2}a_k\} = \{1,2,3,4\}$
$\{\Delta^{3}a_k\} = \{1,1,1\}$
$\vec{a}=<a_1,\Delta a_1,\Delta^2 a_1, \Delta^3 a_1> = <1,1,1,1>$
$$ f(k) = C^{k-1}_{0}+C^{k-1}_{1}+C^{k-1}_{2}+C^{k-1}_{3} $$
展開得到
$$ f(k) = 1 + (k-1) + \frac{(k-1)(k-2)}{2} + \frac{(k-1)(k-2)(k-3)}{6} $$
[檢查]
很明顯 $f(1) , f(2) , f(3)$ 都滿足要求
計算 $f(4) = 1 + 3 + \frac{3\cdot 2}{2} + \frac{3\cdot 2 \cdot 1}{6} = 8$
$f(5) = 1 + 4 + \frac{4\cdot 3}{2} + \frac{4\cdot 3 \cdot 2}{6} = 15 $
$f(6) = 1 + 5 + \frac{5\cdot 4}{2} + \frac{5\cdot 4 \cdot 3}{6} = 26 $
我們得到了 $f$ ，這是最低項多項式可以滿足 $(C)$
[小結]
這公式當初是數感發現的，是個非常漂亮的公式，而原理應該可以用泰勒展開式的證明!!
[額外補充]
另外，還可以查詢 OEIS 大辭典，收集了數學家發現的整數數列，可以告訴你下一項是什麼 !! 還有這數列實際上會應用的地方
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2017.08
留言
張貼留言