已知
$a(n)=11+42n+49n^2+18n^3\;\;\;\;\;\;\;\;n=0,1,2,3,\cdots$
$g(x)=11+120x+435x^2+\cdots+a(n)x^n$
請求 $g(x)$ 有理式型態的生成函數。
難度 ✩ ✩ ✩ ✩
很久以前求學階段，我一直不明白某些無窮級數可以表示成有理式型態，另外，我在求解 OEIS 數列時，總有志工補充有理式型態的生成函數，後來閱讀過思考的樂趣一書才恍然大悟，它的妙用。
這題目是小朋友在學校上學期數學素養課程自選的題材，它不是我所擅長的部份 (求解有理式型態的生成函數)，我只能教他把 $g(x)$ 乘上有理式分母會變成有理式分子，以此證明無窮級數可以等於有理數型態。
另外，生成函數的有理式表示法，讓我想起控制系統的轉移函數 (Transfer Function) ，看來找個時間研究它們之間的關聯。
如果a(n)只有常數項，例如a(n)=11，那只需簡單的等比級數就可以寫出g(x)。
回覆刪除而現在a(n)有高次方的項，則可以用微積分解決：
a(n)=11+42n+49n^2+18n^3=(n+1)(11+31n+18n^2)
所以g(x)每一個項可寫成：
a(n)x^n
=(n+1)(11+31n+18n2)x^n
=(d/dx)[(11+31n+18n^2)x^(n+1)]
這樣次方就降到了二次，只要重覆這個過程，就可以將g(x)寫成幾個有理式的和。
看了一些定義，越看越糊塗。
刪除問題：請求 g(x) 有理式型態的生成函數。這點看不懂，
把數列變作多項式的實際意義在哪裏呢？
有些數列可以用這個方法來找出常項，例如斐波那契數列：1, 1, 2, 3, 5, 8, ...
刪除可以先找出它的生成函數：
f(x)=1+x+2x^2+3x^3+5x^4+...
(1-x)f(x)=1+0x+1x^2+1x^3+2x^4+...
(1-x)f(x)=1+x^2f(x)
f(x)=1/(1-x-x^2)
這個時候我們可以用partial fraction將它拆成兩個分數：
f(x)=1/(sqrt(5)(1-phi))-1/(sqrt(5)(1-phi hat)) where phi=1.618..., phi hat=-0.618...
這樣就可以再用幾何級數找出斐波那契數列的常項
http://web.math.sinica.edu.tw/math_media/d323/32302.pdf
刪除http://www.math.ntu.edu.tw/~msa/act/mathcamp/95page/lecture/I.doc
也許這兩篇，可以多了解生成函數一點，只是有理式型態隱藏數列係數在其中，可以說是另類資料壓縮。
簡單來說
回覆刪除g(x)=a(0)x^0+a(1)x^1+a(2)x^2+a(3)x^3+...+a(n)x^n
分為x=1和x≠1的情況來討論：
x=1時，
g(1)
=a(0)+a(1)+a(2)+a(3)+...+a(n)
=11(n+1)+42(1+2+3...+n)+49(1^2+2^2+3^2+...+n^2)+18(1^3+2^3+3^3+...+n^3)
將等冪求和公式代入。
=11(n+1)+42[n(n+1)/2]+49[n(n+1)(2n+1)/6]+18[n(n+1)/2]^2
公因式(n+1)提出，整理
=(n+1)(n+2)(27n^2+71n+33)/6
x≠1時，
g(x)
=a(0)x^0+a(1)x^1+a(2)x^2+a(3)x^3+...+a(n)x^n
=(11+42*0^1+49*0^2+18*0^3)x^0
+(11+42*1^1+49*1^2+18*1^3)x^1
+(11+42*2^1+49*2^2+18*2^3)x^2
+...
+(11+42*n^1+49*n^2+18*n^3)x^n
拆括弧整理。
=11(1+x+x^2+x^3+...+x^n)
+42(1^1*x^1+2^1*x^2+3^1*x^3+...+n^1*x^n)
+49(1^2*x^1+2^2*x^2+3^2*x^3+...+n^2*x^n)
+18(1^3*x^1+2^3*x^2+3^3*x^3+...+n^3*x^n)
令K(x)=1+x^1+x^2+x^3+...+x^n
則g(x)可用下列關係式表示：
g(x)=11K+42(K'x)+49(K'x)'x+18((K'x)'x)'x
其中'代表導函數。利用積法則展開，稍加整理，得到下式：
g(x)=11K+109K'x+103K''x^2+18K'''x^3
x≠1，利用等比級數求和得K(x)=[1-x^(n+1)]/(1-x)，K'(x)和更高階的導數就可用商法則求出，代入就是所求g(x)。
但是繼續做下去傷神傷時，我還是先止步，希望有更簡潔的解法。
哈，打字時z423x5c6已經先發佈留言，不知道方法是否等價?
刪除西瓜的解法繁複，看起來方法應該等價
刪除哈哈！偷懶只打幾行字，搶先發佈留言！
刪除我和西瓜的解法重點都在重覆時用導數，以及最基本的1+a+a^2+...=1/(1-a)，方法應該等價。
期待其他方法的出現
謝謝z423x5c6補充，對了想知道你和西瓜網路名稱的意義，能介紹一下嗎？
刪除我的名稱...是以前玩online game的時候亂打出來的XD
刪除一直沿用至今
在小學的綽號「西瓜」，前面加上「赤子」(赤子之心之意)。
刪除原來如此，我的 Bridan 是因為大學時代有兩樣喜愛活動 Bridge + Dance，所以名字就是這樣拼出來。
刪除偷用了計算機，得解如下：
回覆刪除11[1-x^(n+1)]/(1-x)+109[(nx^(n+1)-(n+1)x^n+1)/(1-x)^2]x^2+103[-(n(n+1)x^(n-1))/(1-x)+(2(1-x^(n+1)))/(1-x)^3-(2(n+1)x^n)/(1-x)^2]x^2+18[-((n-1)n(n+1)x^(n-2))/(1-x)-(3n(n+1)x^(n-1))/(1-x)^2+(6(1-x^(n+1)))/(1-x)^4-(6(n+1)x^n)/(1-x)^3]x^3
有些沒有化簡是因為，wolframalpha爆了。
以後(或許很遙遠)如果有錢，我想買一個PC版的mathematica，方便我做繁複的計算。
刪除讀大學時進行研究，學校可以買教育版，你就可以用到爽。
刪除符號計算數學軟體可以使用 Maxima.
回覆刪除謝謝行天下分享 Maxima，看一下 License，它是 GNU General Public License version 2.0 (GPLv2)，很適合我們業餘非商業使用。
刪除a(x)= \sum_{i=0} ^{n}a_{i}x^{i}
回覆刪除,f(x)=\sum_{i=0}^{n}a(i)x^{i}
f(x)是否有通解!?
這個問題不簡單，因為 f(x) 的係數，前幾項就算不出來，何況通解，怎麼會想出這樣的題目？
刪除我只是天馬行空地將上面係數全部挖空，就發現這個問題。
刪除題目修改一下：
p(n)=a_{0}+\sum_{i=1}^{n}a_{i}x^{i}
,f(x)=p(0)+\sum_{i=1}^{n}p(i)x^{i}
不錯，能自行研究問題，或許有意想不到的東西在其中。
刪除看到這個，突然想到, 證明 Pi 為無理數的方法，與數列也有關。另外，思維也與證明\sqrt{2}為無理數的方式雷同。
回覆刪除https://en.wikipedia.org/wiki/Proof_that_π_is_irrational
請參閱 Cartwright's proof.
謝謝補充，若能化約成有理式，作圖就能很簡單。只是很難直接想到，數列與有理式會有關聯性。
刪除