2017年2月18日 星期六

訓練數學感 129 ─ 生成函數 (Generating Function)

https://4rdp.blogspot.com/2017/02/129-generating-function.html?m=0

已知




請求 g(x) 有理式型態的生成函數

很久以前求學階段,我一直不明白某些無窮級數可以表示成有理式型態,另外,我在求解 OEIS 數列時,總有志工補充有理式型態的生成函數,後來閱讀過思考的樂趣一書才恍然大悟,它的妙用。

這題目是小朋友在學校上學期數學素養課程自選的題材,它不是我所擅長的部份 (求解有理式型態的生成函數),我只能教他把 g(x) 乘上有理式分母會變成有理式分子,以此證明無窮級數可以等於有理數型態。


另外,生成函數的有理式表示法,讓我想起控制系統的轉移函數 (Transfer Function) ,看來找個時間研究它們之間的關聯。

原以為生成函數非數學系的人應該一輩子遇不到它,如果你是這樣想那就大錯特錯,其實中學生所學的級數和就是生成函數,只是老師們沒有強調它們就是生成函數,它在大學數學系是放在離散數學課程中。

23 則留言:

  1. 如果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)寫成幾個有理式的和。

    回覆刪除
    回覆
    1. 看了一些定義,越看越糊塗。
      問題:請求 g(x) 有理式型態的生成函數。這點看不懂,
      把數列變作多項式的實際意義在哪裏呢?

      刪除
    2. 有些數列可以用這個方法來找出常項,例如斐波那契數列: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...
      這樣就可以再用幾何級數找出斐波那契數列的常項

      刪除
    3. http://web.math.sinica.edu.tw/math_media/d323/32302.pdf
      http://www.math.ntu.edu.tw/~msa/act/mathcamp/95page/lecture/I.doc
      也許這兩篇,可以多了解生成函數一點,只是有理式型態隱藏數列係數在其中,可以說是另類資料壓縮。

      刪除
  2. 簡單來說
    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)。

    但是繼續做下去傷神傷時,我還是先止步,希望有更簡潔的解法。

    回覆刪除
    回覆
    1. 哈,打字時z423x5c6已經先發佈留言,不知道方法是否等價?

      刪除
    2. 西瓜的解法繁複,看起來方法應該等價

      刪除
    3. 哈哈!偷懶只打幾行字,搶先發佈留言!
      我和西瓜的解法重點都在重覆時用導數,以及最基本的1+a+a^2+...=1/(1-a),方法應該等價。
      期待其他方法的出現

      刪除
    4. 謝謝z423x5c6補充,對了想知道你和西瓜網路名稱的意義,能介紹一下嗎?

      刪除
    5. 我的名稱...是以前玩online game的時候亂打出來的XD
      一直沿用至今

      刪除
    6. 在小學的綽號「西瓜」,前面加上「赤子」(赤子之心之意)。

      刪除
    7. 原來如此,我的 Bridan 是因為大學時代有兩樣喜愛活動 Bridge + Dance,所以名字就是這樣拼出來。

      刪除
  3. 偷用了計算機,得解如下:
    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爆了。

    回覆刪除
    回覆
    1. 以後(或許很遙遠)如果有錢,我想買一個PC版的mathematica,方便我做繁複的計算。

      刪除
    2. 讀大學時進行研究,學校可以買教育版,你就可以用到爽。

      刪除
  4. 符號計算數學軟體可以使用 Maxima.

    回覆刪除
    回覆
    1. 謝謝行天下分享 Maxima,看一下 License,它是 GNU General Public License version 2.0 (GPLv2),很適合我們業餘非商業使用。

      刪除
  5. a(x)= \sum_{i=0} ^{n}a_{i}x^{i}
    ,f(x)=\sum_{i=0}^{n}a(i)x^{i}

    f(x)是否有通解!?

    回覆刪除
    回覆
    1. 這個問題不簡單,因為 f(x) 的係數,前幾項就算不出來,何況通解,怎麼會想出這樣的題目?

      刪除
    2. 我只是天馬行空地將上面係數全部挖空,就發現這個問題。
      題目修改一下:
      p(n)=a_{0}+\sum_{i=1}^{n}a_{i}x^{i}
      ,f(x)=p(0)+\sum_{i=1}^{n}p(i)x^{i}

      刪除
    3. 不錯,能自行研究問題,或許有意想不到的東西在其中。

      刪除
  6. 看到這個,突然想到, 證明 Pi 為無理數的方法,與數列也有關。另外,思維也與證明\sqrt{2}為無理數的方式雷同。
    https://en.wikipedia.org/wiki/Proof_that_π_is_irrational
    請參閱 Cartwright's proof.

    回覆刪除
    回覆
    1. 謝謝補充,若能化約成有理式,作圖就能很簡單。只是很難直接想到,數列與有理式會有關聯性。

      刪除