時間序列︰生成函數《六》

2017-02-28 懸鉤子

唐‧孟郊《登科後》

昔日齷齪不足誇，
今朝放蕩思無涯。
春風得意馬蹄疾，
一日看盡長安花。

縱想暢寫生成花，高妙鉤沈難為功，祇得假借書自有，走馬看花總人情。

The book “generatingfunctionology”

$gf3.jpg$

This book was originally published by Academic Press in 1990. A Second Edition appeared in 1994, and the Third Edition is now available from the publisher or from your favorite bookstore.

The Second Edition can be downloaded from this page. If you download the book you are agreeing to the following terms:

Reproduction of the downloaded version is permitted for any valid educational purpose of an institution of learning, in which case only the reasonable costs of reproduction may be charged. Reproduction for profit or for any commercial purposes is strictly prohibited. It is not permitted for a web site other than this one to offer the book directly for downloading. Other web sites are cordially invited to link to this page, but must not take the file and offer it themselves.

…

雞飛時起鴻鵠志，狗跳主迎舊日結，眼前大好勢所趨，豈敢獨闖陰陽界。

Probability-generating function

In probability theory, the probability generating function of a discrete random variable is a power series representation (the generating function) of the probability mass function of the random variable. Probability generating functions are often employed for their succinct description of the sequence of probabilities Pr(X = i) in the probability mass function for a random variable X, and to make available the well-developed theory of power series with non-negative coefficients.

Definition

Univariate case

If X is a discrete random variable taking values in the non-negative integers {0,1, …}, then the probability generating function of X is defined as ^[1]

G(z)=\operatorname {E} (z^{X})=\sum _{x=0}^{\infty }p(x)z^{x},

where p is the probability mass function of X. Note that the subscripted notations G_X and p_X are often used to emphasize that these pertain to a particular random variable X, and to its distribution. The power series converges absolutely at least for all complex numbers z with |z| ≤ 1; in many examples the radius of convergence is larger.

Multivariate case

If X = (X₁,…,X_d ) is a discrete random variable taking values in the d-dimensional non-negative integer lattice {0,1, …}^d, then the probability generating function of X is defined as

G(z)=G(z_{1},\ldots ,z_{d})=\operatorname {E} {\bigl (}z_{1}^{X_{1}}\cdots z_{d}^{X_{d}}{\bigr )}=\sum _{x_{1},\ldots ,x_{d}=0}^{\infty }p(x_{1},\ldots ,x_{d})z_{1}^{x_{1}}\cdots z_{d}^{x_{d}},

where p is the probability mass function of X. The power series converges absolutely at least for all complex vectors z = (z₁,…,z_d ) ∈ ℂ^d with max{|z₁|,…,|z_d |} ≤ 1.

Properties

Power series

Probability generating functions obey all the rules of power series with non-negative coefficients. In particular, G(1⁻) = 1, where G(1⁻) = lim_z→1G(z) from below, since the probabilities must sum to one. So the radius of convergence of any probability generating function must be at least 1, by Abel’s theorem for power series with non-negative coefficients.

Probabilities and expectations

The following properties allow the derivation of various basic quantities related to X:

1. The probability mass function of X is recovered by taking derivatives of G

p(k)=\operatorname {Pr} (X=k)={\frac {G^{(k)}(0)}{k!}}.

2. It follows from Property 1 that if random variables X and Y have probability generating functions that are equal, G_X = G_Y, then p_X = p_Y. That is, if X and Y have identical probability generating functions, then they have identical distributions.

3. The normalization of the probability density function can be expressed in terms of the generating function by

\operatorname {E} (1)=G(1^{-})=\sum _{i=0}^{\infty }f(i)=1.

The expectation of X is given by

\operatorname {E} \left(X\right)=G'(1^{-}).

More generally, the k^th factorial moment, ${\textrm {E}}(X(X-1)\cdots (X-k+1))$ of X is given by

{\textrm {E}}\left({\frac {X!}{(X-k)!}}\right)=G^{(k)}(1^{-}),\quad k\geq 0.

So the variance of X is given by

\operatorname {Var} (X)=G''(1^{-})+G'(1^{-})-\left[G'(1^{-})\right]^{2}.

4. $G_{X}(e^{t})=M_{X}(t)$ where X is a random variable, $G_{X}(t)$ is the probability generating function (of X) and $M_{X}(t)$ is the moment-generating function (of X) .

……

Moment-generating function

In probability theory and statistics, the moment-generating function of a real-valued random variable is an alternative specification of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compared with working directly with probability density functions or cumulative distribution functions. There are particularly simple results for the moment-generating functions of distributions defined by the weighted sums of random variables. Note, however, that not all random variables have moment-generating functions.

In addition to real-valued distributions (univariate distributions), moment-generating functions can be defined for vector- or matrix-valued random variables, and can even be extended to more general cases.

The moment-generating function of a real-valued distribution does not always exist, unlike the characteristic function. There are relations between the behavior of the moment-generating function of a distribution and properties of the distribution, such as the existence of moments.

Definition

In probability theory and statistics, the moment-generating function of a random variable X is

M_{X}(t):=\mathbb {E} \!\left[e^{tX}\right],\quad t\in \mathbb {R} ,

wherever this expectation exists. In other terms, the moment-generating function can be interpreted as the expectation of the random variable $e^{tX}$ .

$M_{X}(0)$ always exists and is equal to 1.

A key problem with moment-generating functions is that moments and the moment-generating function may not exist, as the integrals need not converge absolutely. By contrast, the characteristic function or Fourier transform always exists (because it is the integral of a bounded function on a space of finite measure), and for some purposes may be used instead.

More generally, where $\mathbf {X} =(X_{1},\ldots ,X_{n})$ ^T, an n-dimensional random vector, and t a fixed vector, one uses $\mathbf {t} \cdot \mathbf {X} =\mathbf {t} ^{\mathrm {T} }\mathbf {X}$ instead of tX:

M_{\mathbf {X} }(\mathbf {t} ):=\mathbb {E} \!\left(e^{\mathbf {t} ^{\mathrm {T} }\mathbf {X} }\right).

The reason for defining this function is that it can be used to find all the moments of the distribution.^[1] The series expansion of e^tX is:

e^{t\,X}=1+t\,X+{\frac {t^{2}\,X^{2}}{2!}}+{\frac {t^{3}\,X^{3}}{3!}}+\cdots +{\frac {t^{n}\,X^{n}}{n!}}+\cdots .

Hence:

{\begin{aligned}M_{X}(t)=\mathbb {E} (e^{t\,X})&=1+t\,\mathbb {E} (X)+{\frac {t^{2}\,\mathbb {E} (X^{2})}{2!}}+{\frac {t^{3}\,\mathbb {E} (X^{3})}{3!}}+\cdots +{\frac {t^{n}\,\mathbb {E} (X^{n})}{n!}}+\cdots \\&=1+tm_{1}+{\frac {t^{2}m_{2}}{2!}}+{\frac {t^{3}m_{3}}{3!}}+\cdots +{\frac {t^{n}m_{n}}{n!}}+\cdots ,\end{aligned}}

where m_n is the nth moment.

Differentiating M_X(t) i times with respect to t and setting t = 0 we hence obtain the ith moment about the origin, m_i, see Calculations of moments below.

───

樹莓派、樹莓派之學習、樹莓派之教育

時間序列︰生成函數《五》

2017-02-27 懸鉤子

眼尖心細的讀者或許會覺得作者上一篇的推導太可疑︰

假設

$G(x) = \sum \limits_{n=0}^{\infty} F_n x^n$ ，從遞迴關係可得

$F_{n+2} = F_{n+1} + F_n , \ F_0 = 0, F_1 = 1$

$\longrightarrow F_{n+2} \cdot x^{n+2} = F_{n+1} \cdot x^{n+2} + F_n \cdot x^{n+2}$

$\longrightarrow \sum \limits_{n=0}^{\infty} F_{n+2} x^{n+2} = x \cdot \sum \limits_{n=0}^{\infty} F_{n+1} x^{n+1} + x^2 \cdot \sum \limits_{n=0}^{\infty} F_n x^n$

$\longrightarrow G(x) - x = x \cdot G(x) + x^2 \cdot G(x)$

$\therefore G(x) = \frac{x}{1 - x - x^2}$

如果 $\lambda_{+} , \lambda_{-}$ 是 $1 + x - x^2 = 0$ 的兩個根，而且 $\lambda_{+} > \lambda_{-}$ ，也就是說 $\lambda_{+} = \frac{1 + \sqrt {5} } {2} , \lambda_{-} = \frac{1 - \sqrt {5} } {2}$ ，那麼 $G(x)$ 可改寫為

$\frac{1}{\lambda_{+} - \lambda_{-}} \left( \frac{1}{1 - \lambda_{+} x} - \frac{1}{1 - \lambda_{-} x} \right)$

分明是偷用著費波那契數列的特徵方程式 $r^2 = r + 1$ ，而不是生成函數 $G(x)$ 的分母方程式 $1 - x - x^2 = 0$ 做部分分式分解。非為著辯解，實乃費波那契數列有豐富的性質，不過勸思勸學而已。

Fibonacci Number

The Fibonacci numbers are the sequence of numbers ${F_n}_(n=1)^infty$ defined by the linear recurrence equation

(1)

with . As a result of the definition (1), it is conventional to define .

The Fibonacci numbers for , 2, … are 1, 1, 2, 3, 5, 8, 13, 21, … (OEIS A000045).

Fibonacci numbers can be viewed as a particular case of the Fibonacci polynomials with .

Fibonacci numbers are implemented in the Wolfram Language as Fibonacci[n].

The Fibonacci numbers are also a Lucas sequence , and are companions to the Lucas numbers (which satisfy the same recurrence equation).

FoxTrot by Bill Amend

The above cartoon (Amend 2005) shows an unconventional sports application of the Fibonacci numbers (left two panels). (The right panel instead applies the Perrin sequence).

此處先補足推導過程，再言其他。假設 $\alpha > \beta$ 是分母方程式 $1 - x - x^2 = 0$ 的兩個根。解之可得 $\alpha = \frac{-1 + \sqrt{5}}{2} , \ \beta = \frac{-1 - \sqrt{5}}{2}$ ，當然 $\alpha + \beta = -1 , \ \alpha \cdot \beta = -1$ 。由於

${\alpha}^{-1} = \frac{2}{-1 + \sqrt{5}} = {\lambda}_{+}$ ，

${\beta}^{-1} = \frac{2}{-1 - \sqrt{5}} = {\lambda}_{-}$ 。因此

$\frac{x}{1 - x - x^2} = - \frac{1}{\alpha - \beta} \left( \frac{\alpha}{x -\alpha} - \frac{\beta}{x- \beta} \right)$

$= \frac{{\lambda}_{+} {\lambda}_{-}}{{\lambda}_{+} - {\lambda}_{-}} \left( \frac{1}{{\alpha}^{-1} x - 1} - \frac{1}{{\beta}^{-1} x - 1} \right)$

$\therefore = \frac{1}{\lambda_{+} - \lambda_{-}} \left( \frac{1}{1 - \lambda_{+} x} - \frac{1}{1 - \lambda_{-} x} \right)$ 。

【※ 註︰ ${\lambda}_{+} + {\lambda}_{-} = 1 , \ {\lambda}_{+} {\lambda}_{-} = -1$ 】

事實上，那個 ${\lambda}_{+}$ 就是著名的

黃金比例

黃金比例，又稱黃金分割^[1]，是一個數學常數，一般以希臘字母 $\phi$ 表示^[2]^[3]^[4]。可以透過以下代數式定義：

{\frac {a+b}{a}}={\frac {a}{b}}\,{\stackrel {\text{def}}{=}}\,\phi \quad (a>b>0)

這也是黃金比例一名的由來。
黃金比例的準確值為 ${\frac {1+{\sqrt {5}}}{2}}$ ，所以是無理數，而大約值則為（小數點後20位， A001622）：

\phi =1.61803398874989484820\ldots

應用時一般取1.618，就像圓周率在應用時取3.14一樣。

黃金分割具有嚴格的比例性、藝術性、和諧性，蘊藏著豐富的美學價值，而且呈現於不少動物和植物的外觀。現今很多工業產品、電子產品、建築物或藝術品均普遍應用黃金分割，展現其功能性與美觀性。

A golden rectangle (in pink) with longer side a and shorter side b, when placed adjacent to a square with sides of length a, will produce a similar golden rectangle with longer side a + b and shorter side a. This illustrates the relationship ${\frac {a+b}{a}}={\frac {a}{b}}\equiv \varphi$ .

。她的歷史充滿韻律

Origins

The Fibonacci sequence appears in Indian mathematics, in connection with Sanskrit prosody.^[8]^[13] In the Sanskrit tradition of prosody, there was interest in enumerating all patterns of long (L) syllables that are 2 units of duration, and short (S) syllables that are 1 unit of duration. Counting the different patterns of L and S of a given duration results in the Fibonacci numbers: the number of patterns that are m short syllables long is the Fibonacci number F_m + 1.^[9]

Susantha Goonatilake writes that the development of the Fibonacci sequence “is attributed in part to Pingala (200 BC), later being associated with Virahanka (c. 700 AD), Gopāla (c. 1135), and Hemachandra (c. 1150)”.^[7] Parmanand Singh cites Pingala’s cryptic formula misrau cha (“the two are mixed”) and cites scholars who interpret it in context as saying that the cases for m beats (F_m+1) is obtained by adding a [S] to F_m cases and [L] to the F_m−1 cases. He dates Pingala before 450 BC.^[14]

However, the clearest exposition of the sequence arises in the work of Virahanka (c. 700 AD), whose own work is lost, but is available in a quotation by Gopala (c. 1135):

Variations of two earlier meters [is the variation]… For example, for [a meter of length] four, variations of meters of two [and] three being mixed, five happens. [works out examples 8, 13, 21]… In this way, the process should be followed in all mātrā-vṛttas [prosodic combinations].^[15]

The sequence is also discussed by Gopala (before 1135 AD) and by the Jain scholar Hemachandra (c. 1150).

A page of Fibonacci‘s Liber Abaci from the Biblioteca Nazionale di Firenze showing (in box on right) the Fibonacci sequence with the position in the sequence labeled in Latin and Roman numerals and the value in Hindu-Arabic numerals.

，以及具有旺盛的生育力。

Outside India, the Fibonacci sequence first appears in the book Liber Abaci (1202) by Fibonacci.^[6] Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: a newly born pair of rabbits, one male, one female, are put in a field; rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits; rabbits never die and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was: how many pairs will there be in one year?

At the end of the first month, they mate, but there is still only 1 pair.
At the end of the second month the female produces a new pair, so now there are 2 pairs of rabbits in the field.
At the end of the third month, the original female produces a second pair, making 3 pairs in all in the field.
At the end of the fourth month, the original female has produced yet another new pair, and the female born two months ago also produces her first pair, making 5 pairs.

At the end of the nth month, the number of pairs of rabbits is equal to the number of new pairs (which is the number of pairs in month n − 2) plus the number of pairs alive last month (n − 1). This is the nth Fibonacci number.^[16]

The name “Fibonacci sequence” was first used by the 19th-century number theorist Édouard Lucas.^[17]

The number of rabbits form the Fibonacci sequence

樹莓派、樹莓派之學習、樹莓派之教育

時間序列︰生成函數《四》

2017-02-26 懸鉤子

說到生成函數操作上應注意的事項，首重『表達式』之『所指』、『虛名變數』的『替換』，以及『初始資料』的『應用』。通熟 λ 表達式 α 變換者，想必知之深矣。

於此再度回顧一下變元的『替換規則』的定義︰

$E[x := M]$ 是指將 $E$ 『表達式』中所有『自由出現』的『 $x$ 變元』，都使用 $M$ 『表達項』來取代。我們可以歸納的定義如下︰

$x, y$ 是所指 $E$ 表達式的任意變元
$A, B. M,$ 是所指 $E$ 表達式的任意構成項── 該式在建構過程中的各個合乎語法的子表達式 ──。

一、 $x[x := M] \equiv M$

二、 $y[x := M] \equiv y$ ，只要 $y$ 變元不是 $x$ 變元

三、 $(A B)[x := M] \equiv (A[x := M] B[x := M])$

四、 $(\lambda x. A) [x := M] \equiv (\lambda x. A)$

五、 $(\lambda y. A) [x := M] \equiv (\lambda y. A[x := M] )$ ，只要 $y$ 變元不是 $x$ 變元

假使有一個簡單的函式 $(\lambda x. E)$ ，它不包含著其它『子函式』以及『函式應用』，當我們說『 $(\lambda x. E) \equiv_{\alpha} (\lambda y. E^{\alpha})$ 』是指 $E^{\alpha}$ 是由上面的變元『替換規則』從 $E[x := y]$ 得到的。這時我們講 $(\lambda y. E^{\alpha})$ 是經由『 $\alpha$ 變換』從 $(\lambda x. E)$ 變更『受約束變元 $x$ 』成為『受約束變元 $y$ 』而得來。為什麼那一邊說著『自由的』，這一邊又講著『受約束』？是因為 $E$ 表達式中 $x$ 變元是『自由的』，『抽象封裝』成為『函式』 $(\lambda x. E)$ ，這時那個 $x$ 變元就成『受約束』的了。其次為何要先『限定簡單』的函式呢？如果看一看 $(\lambda x. (y x))$ 的表達式，那麼我們又要如何替換它呢？人們之所以需要『重新命名』受約束變元，是因為『應用化約』可能產生的『命名衝突』，或許『直覺』上講又怎麽會去用了『 $\alpha$ 變換』以後，卻反而又製造了『新的衝突』的呢？因此與其將它『一碼歸一碼』的煩雜分解的說，不如就建立某些『不成文的規矩』，每當提到受約束的變元『重新命名』時，就是說使用從來『不曾出現』或者說『不起衝突』的新的變元名字的意思！這樣不管再複雜的表達式都可以用著『 $\alpha$ 變換』『一步一步』的『系統化』轉換成另一個同等的表達式，於是我們可以說︰

$M \equiv_{\alpha} N$

。再者，與『函式所約束之虛名變元』無關的『自由變元』一般都來自於『函式應用』 ── 比方 $((\lambda x. M) y)$ 的『輸入項』 $y$ 變元 ──，通常除非為了表達清晰起見，人們不會『重新命名』輸入項。如果從『程式計算』的角度講，『計算資料』是程式外部來的，在程式裡當然要叫它什麼名字都可以。於是那個『系統化』的『更名』辦法，自然可以行使於任何『函式』或者『應用』的『子函式表達項』中，也許就不會再有『表達轉換』作法上彼此之歧見的了！！

假使再次細思『 λ 表達式』的歸納定義，最簡單的表達式『始於變元』，然後方在其上建立『函式』，之後才『應用』函式於『變元』之上。因此前面說的那個簡單的函式 $(\lambda x. E)$ 的可能構成是極其有限的，比方說 $E$ 中只能有一個變元，假使 $E$ 有兩個以上的變元，那一定是由『函式應用』或者『多元函式』所產生的。所以它只可能像是 $(\lambda x. x)$ 或者 $(\lambda x. y)$ 這樣。也許有人會想難道它不能是像 $(\lambda x. \ 2\times x)$ 或者 $(\lambda x. + x \ y)$ 的嗎？在某些『應用 λ語言』中，這種語法是合宜的；然而這裡用的卻是『純粹』Pure 的 λ語法，這個『語法集』中根本沒有『什麼是 $\times$ 或 $+$ 』，因此表達所需要用的一切都得在『基元』Primitive 上自己建立。『複雜』與『難題』是兩種不同的『困難性』。許多『難題』表述起來很簡單── 比方說費瑪最後定理︰ $x^n + y^n = z^n, n \geq 3$ 沒有整數解 ──，想解決卻十分困難。而『複雜』是源於構成『部份』眾多或者『結構』縱橫多層，雖然基本『單元』並不『困難』，基礎結構『組件』也很『簡單』，由於『數大層多就是難』這就是 λ 表達式的『寫照』。這個『複雜性』或許也就是『 λ 語法』之所以『方言』崛起的緣故。

─── 摘自《λ 運算︰概念導引《三》》

因此明白若是 $G(x) = \sum \limits_{n=0}^{\infty} a_n x^n$ ，則

$\equiv_{\alpha} \sum \limits_{k=0}^{\infty} a_k x^k$

$\equiv_{\alpha} \sum \limits_{k=1}^{\infty} a_k x^k + a_0$

$\equiv_{\alpha} \sum \limits_{p=0}^{\infty} a_{p+1} x^{p+1} + a_0$

$\equiv_{\alpha} \cdots$ 。

如果已知 $a_0 = 0$ ，那麼也

$= \sum \limits_{k=1}^{\infty} a_k x^k$

$= \sum \limits_{p=0}^{\infty} a_{p+1} x^{p+1}$

且讓我們用曾講過的費波那契序列公式︰

……

為什麼數學上常常要用『遞迴定義』的呢？假使你出於『好玩』，想『定義』一個『數列』，那麼有什麼『簡單』的辦法的呢？

有人說︰這很簡單啊！就給一個 $F_n$ 『公式』Formula 就好了，就好比講這個數列是

$F_n =_{df} \Box \Box, n=0 \cdots \infty$ 。

有人問︰萬一你不知道『那個公式』呢？還是說如果『公式不存在』這樣子就根本『沒辦法』去定義『數列』的呢？

有人答︰『可以』的啊！比方說假使你『知道』

一、 $F_0$ 的『值』

二、曉得如何從 $F_k$ 『計算』出 $F_{k+1}$ 的『值』，這樣就算是不知道 $F_n$ 是能不能夠表達，一樣可以『定義』這個『數列』的啊！

據說義大利的數學家李奧納多‧費波那契 Leonardo Fibonacci 描述各代『兔子生育』總數目時得到這個數列︰

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$

因此 $F_2 = F_1 + F_0 = 1 + 0 = 1, F_3 = F_2 + F_1 = 1 + 1 = 2. \cdots$ ，所以可以逐步的得到『費波那契數列』。當然可以求解那一個『差分方程式』得到

$F_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]$ 。

然而並非所有可以『遞迴定義』的數列，都能有『公式解』，或者說還沒將它『算出來』。所以能這樣從幾個『初始資料』和一個『遞迴關係』來定義東西的方式，自然有它的好處的了。

─── 摘自《λ 運算︰計物數《遞迴補遺》》

談談這個推導過程。假設

$G(x) = \sum \limits_{n=0}^{\infty} F_n x^n$ ，從遞迴關係可得

$F_{n+2} = F_{n+1} + F_n , \ F_0 = 0, F_1 = 1$

$\longrightarrow F_{n+2} \cdot x^{n+2} = F_{n+1} \cdot x^{n+2} + F_n \cdot x^{n+2}$

$\longrightarrow \sum \limits_{n=0}^{\infty} F_{n+2} x^{n+2} = x \cdot \sum \limits_{n=0}^{\infty} F_{n+1} x^{n+1} + x^2 \cdot \sum \limits_{n=0}^{\infty} F_n x^n$

$\longrightarrow G(x) - x = x \cdot G(x) + x^2 \cdot G(x)$

$\therefore G(x) = \frac{x}{1 - x - x^2}$

$\frac{1}{\lambda_{+} - \lambda_{-}} \left( \frac{1}{1 - \lambda_{+} x} - \frac{1}{1 - \lambda_{-} x} \right)$ ，所以 $F_n = [n] G(x)$

$= [n] \left[ \frac{1}{\lambda_{+} - \lambda_{-}} \left( \frac{1}{1 - \lambda_{+} x} - \frac{1}{1 - \lambda_{-} x} \right) \right]$

$= \frac{\sqrt{5}}{5} \cdot [n] \left( \frac{1}{1 - \lambda_{+} x} - \frac{1}{1 - \lambda_{-} x} \right)$

$= \frac{\sqrt{5}}{5} \cdot \left( [n] \frac{1}{1 - \lambda_{+} x} - [n] \frac{1}{1 - \lambda_{-} x} \right)$

$= \frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]$ 。

樹莓派、樹莓派之學習、樹莓派之教育

時間序列︰生成函數《三》

2017-02-25 懸鉤子

若說遞迴關係、差分方程在計算機演算法分析上的重要性容易明白，要講它撐起了數學半邊天，怕是匪夷所思︰

義大利的數學家朱塞佩‧皮亞諾 Giuseppe Peano 提出『自然數』之五條公設的系統。用著『未定義』的『基元』數『零 $0$ 』，以及『後繼數』successor 的概念，打造了一階算術系統，現今稱之為『皮亞諾算術系統』︰

一、 $0$ 是自然數。
二、如果 $n$ 是自然數，則 $n$ 的後繼數也是自然數。
三、 $0$ 不是任何自然數的後繼數。
四、如果兩個自然數的後繼數相等，則這兩個自然數相等。
五、任何關於自然數的命題，假使證明了這個命題對於自然數 $0$ 是真的，如果它對自然數 $n$ 為真時，又可以證明它對 $n$ 後繼數也真，那麼這個命題對所有的自然數都是真的── 數學歸納法 ──。

於是可以將皮亞諾算術表達成︰此處 $S$ 代表某數之後繼數

$\forall n (Sn \neq 0)$
$\forall m, n ((Sm = Sn) \Rightarrow m = n)$
$\varphi[0] \wedge \forall n \ (\varphi[n]\Rightarrow\varphi[Sn]) \Rightarrow \forall n \ (\varphi[n])$ ，就是數學歸納法
$\forall n (n + 0 = n)$
$\forall m, n(m + Sn = S(m + n))$
$\forall n (n \cdot 0 = 0)$
$\forall m, n (m \cdot Sn = (m \cdot n) + m)$

唐賈島《尋隱者不遇》
松下問童子，
言師採藥去。
只在此山中，
雲深不知處。

果真身緣此山中，不識廬山真面目！！

皮亞諾將『算術』公設化變成了祇有『零』、『後繼數』以及『相等』三個關於『計物數』之『基本』的『概念』。抽象了的『自然數』是否一樣『自然』，能如『骨牌』從『零』開始，一個推倒一個以至於『無窮』的嗎？？

─── 摘自《λ 運算︰計物數《上》》

這個自然數的集合 $N = \{ 0, 1, 2, \cdots , k, \cdots \}$ 可用 $a_{n+1} = a_n +1 , \ a_0 = 0$ 遞迴關係給出。若問 $a_n = ?$ ，顯然的 $a_n = n$ 。難到能不是 $(n + 1) = (n) + 1$ 的嗎？要說因為它的非『均質』 homogeneous 性，故無法直接應用『特徵多項式』 $r^n$ 法求取，豈不叫人驚訝！

※ 註︰ $r^{n+1} = r^{n} + 1$ 無法化簡問題也。

苟知其理︰

Recurrence relation

In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.

The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation. However, “difference equation” is frequently used to refer to any recurrence relation.

……

Solving

Solving homogeneous linear recurrence relations with constant coefficients

Main articles: Constant-recursive sequence and Linear difference equation

Roots of the characteristic polynomial

An order-d homogeneous linear recurrence with constant coefficients is an equation of the form

a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},

where the d coefficients c_i (for all i) are constants.

A constant-recursive sequence is a sequence satisfying a recurrence of this form. There are d degrees of freedom for solutions to this recurrence, i.e., the initial values $a_{0},\dots ,a_{d-1}$ can be taken to be any values but then the recurrence determines the sequence uniquely.

The same coefficients yield the characteristic polynomial (also “auxiliary polynomial”)

p(t)=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}

whose d roots play a crucial role in finding and understanding the sequences satisfying the recurrence. If the roots r₁, r₂, … are all distinct, then each solution to the recurrence takes the form

a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},

where the coefficients k_i are determined in order to fit the initial conditions of the recurrence. When the same roots occur multiple times, the terms in this formula corresponding to the second and later occurrences of the same root are multiplied by increasing powers of n. For instance, if the characteristic polynomial can be factored as (x−r)³, with the same root r occurring three times, then the solution would take the form

a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.

^[2]

As well as the Fibonacci numbers, other constant-recursive sequences include the Lucas numbers and Lucas sequences, the Jacobsthal numbers, the Pell numbers and more generally the solutions to Pell’s equation.

For order 1, the recurrence

a_{n}=ra_{n-1}

has the solution a_n = rⁿ with a₀ = 1 and the most general solution is a_n = krⁿ with a₀ = k. The characteristic polynomial equated to zero (the characteristic equation) is simply t − r = 0.

Solutions to such recurrence relations of higher order are found by systematic means, often using the fact that a_n = rⁿ is a solution for the recurrence exactly when t = r is a root of the characteristic polynomial. This can be approached directly or using generating functions (formal power series) or matrices.

……

Solving non-homogeneous linear recurrence relations with constant coefficients

If the recurrence is non-homogeneous, a particular solution can be found by the method of undetermined coefficients and the solution is the sum of the solution of the homogeneous and the particular solutions. Another method to solve an non-homogeneous recurrence is the method of symbolic differentiation. For example, consider the following recurrence:

a_{n+1}=a_{n}+1

This is an non-homogeneous recurrence. If we substitute n ↦ n+1, we obtain the recurrence

a_{n+2}=a_{n+1}+1

Subtracting the original recurrence from this equation yields

a_{n+2}-a_{n+1}=a_{n+1}-a_{n}

or equivalently

a_{n+2}=2a_{n+1}-a_{n}

This is a homogeneous recurrence, which can be solved by the methods explained above. In general, if a linear recurrence has the form

a_{n+k}=\lambda _{k-1}a_{n+k-1}+\lambda _{k-2}a_{n+k-2}+\cdots +\lambda _{1}a_{n+1}+\lambda _{0}a_{n}+p(n)

where $\lambda _{0},\lambda _{1},\dots ,\lambda _{k-1}$ are constant coefficients and p(n) is the inhomogeneity, then if p(n) is a polynomial with degree r, then this non-homogeneous recurrence can be reduced to a homogeneous recurrence by applying the method of symbolic differencing r times.

P(x)=\sum _{n=0}^{\infty }p_{n}x^{n}

is the generating function of the inhomogeneity, the generating function

A(x)=\sum _{n=0}^{\infty }a(n)x^{n}

of the non-homogeneous recurrence

a_{n}=\sum _{i=1}^{s}c_{i}a_{n-i}+p_{n},\quad n\geq n_{r},

with constant coefficients $c i$ is derived from

\left(1-\sum _{i=1}^{s}c_{i}x^{i}\right)A(x)=P(x)+\sum _{n=0}^{n_{r}-1}[a_{n}-p_{n}]x^{n}-\sum _{i=1}^{s}c_{i}x^{i}\sum _{n=0}^{n_{r}-i-1}a_{n}x^{n}.

If P(x) is a rational generating function, A(x) is also one. The case discussed above, where p_n = K is a constant, emerges as one example of this formula, with P(x) = K/(1−x). Another example, the recurrence } $a_{n}=10a_{n-1}+n$ with linear inhomogeneity, arises in the definition of the schizophrenic numbers. The solution of homogeneous recurrences is incorporated as p = P = 0.

且善其工︰

pi@raspberrypi:~ a_{n+2} - a_{n+1} = a_{n+1} -a_nr^2 - 2 r + 1 = 0 = {(r - 1)}^2 a_n = k_1 \cdot 1^n + k_2 \cdot n \cdot 1^n = k_1 + k_2 \cdot n a_{n+1} = a_n + 1 , \ a_0 = 0k_1 + k_2 (n + 1) = k_1 + k_2 \cdot n + 1k_2 = 1a_n = k_1 + na_0 = k_1 + 0 = 0\therefore a_n = nA(x) = \sum_{n=0}^{\infty} a_n x^na_{n+1} = a_n + 1 , \ a_0 = 0\longrightarrow a_{n+1} \cdot x^n = a_n \cdot x^n + 1 \cdot x^n\longrightarrow \sum_{n=0}^{\infty} a_{n+1} x^n = \sum_{n=0}^{\infty} a_n x^n + \sum_{n=0}^{\infty} x^n \longrightarrow \frac{A(x)}{x} = A(x) + \frac{1}{1 - x}\longrightarrow A(x) = \frac{x}{{1-x}^2}\therefore a_n = [n] A(x) = [n] \frac{x}{{1-x}^2} = [n - 1] \frac{1}{{1-x}^2} = n $ 。
※ 註︰
 $\sum_{n=0}^{\infty}(n+1)x^n= \frac{1}{(1-x)^2},$ 
 
太自然反倒費疑猜的哩☆

樹莓派、樹莓派之學習、樹莓派之教育

時間序列︰生成函數《二》

2017-02-24 懸鉤子

雖然今天我們還是可以像歐拉一樣自由的操作生成函數︰

Power series

Main article: Power series

A power series is a series of the form

\sum _{n=0}^{\infty }a_{n}(x-c)^{n}.

The Taylor series at a point c of a function is a power series that, in many cases, converges to the function in a neighborhood of c. For example, the series

\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}

is the Taylor series of $e^{x}$ at the origin and converges to it for every x.

Unless it converges only at x=c, such a series converges on a certain open disc of convergence centered at the point c in the complex plane, and may also converge at some of the points of the boundary of the disc. The radius of this disc is known as the radius of convergence, and can in principle be determined from the asymptotics of the coefficients a_n. The convergence is uniform on closed and bounded (that is, compact) subsets of the interior of the disc of convergence: to wit, it is uniformly convergent on compact sets.

Historically, mathematicians such as Leonhard Euler operated liberally with infinite series, even if they were not convergent. When calculus was put on a sound and correct foundation in the nineteenth century, rigorous proofs of the convergence of series were always required. However, the formal operation with non-convergent series has been retained in rings of formal power series which are studied in abstract algebra. Formal power series are also used in combinatorics to describe and study sequences that are otherwise difficult to handle; this is the method of generating functions.

不管它是收斂與否︰

Introduction

A formal power series can be loosely thought of as an object that is like a polynomial, but with infinitely many terms. Alternatively, for those familiar with power series (or Taylor series), one may think of a formal power series as a power series in which we ignore questions of convergence by not assuming that the variable X denotes any numerical value (not even an unknown value). For example, consider the series

A = 1 - 3X + 5X^2 - 7X^3 + 9X^4 - 11X^5 + \cdots.

If we studied this as a power series, its properties would include, for example, that its radius of convergence is 1. However, as a formal power series, we may ignore this completely; all that is relevant is the sequence of coefficients [1, −3, 5, −7, 9, −11, …]. In other words, a formal power series is an object that just records a sequence of coefficients. It is perfectly acceptable to consider a formal power series with the factorials [1, 1, 2, 6, 24, 120, 720, 5040, … ] as coefficients, even though the corresponding power series diverges for any nonzero value of X.

Arithmetic on formal power series is carried out by simply pretending that the series are polynomials. For example, if

B = 2X + 4X^3 + 6X^5 + \cdots,

then we add A and B term by term:

A + B = 1 - X + 5X^2 - 3X^3 + 9X^4 - 5X^5 + \cdots.

We can multiply formal power series, again just by treating them as polynomials (see in particular Cauchy product):

AB = 2X - 6X^2 + 14X^3 - 26X^4 + 44X^5 + \cdots.

Notice that each coefficient in the product AB only depends on a finite number of coefficients of A and B. For example, the X⁵ term is given by

44X^5 = (1\times 6X^5) + (5X^2 \times 4X^3) + (9X^4 \times 2X).

For this reason, one may multiply formal power series without worrying about the usual questions of absolute, conditional and uniform convergence which arise in dealing with power series in the setting of analysis.

Once we have defined multiplication for formal power series, we can define multiplicative inverses as follows. The multiplicative inverse of a formal power series A is a formal power series C such that AC = 1, provided that such a formal power series exists. It turns out that if A has a multiplicative inverse, it is unique, and we denote it by A⁻¹. Now we can define division of formal power series by defining B/A to be the product BA⁻¹, provided that the inverse of A exists. For example, one can use the definition of multiplication above to verify the familiar formula

\frac{1}{1 + X} = 1 - X + X^2 - X^3 + X^4 - X^5 + \cdots.

An important operation on formal power series is coefficient extraction. In its most basic form, the coefficient extraction operator for a formal power series in one variable extracts the coefficient of $[X^{n}]$ , and is written e.g. $[X^{n}]A$ , so that $[X^{2}]A=5$ and $[X^{5}]A=-11$ . Other examples include

</span

Similarly, many other operations that are carried out on polynomials can be extended to the formal power series setting, as explained below.

就算如波例亞所說，它是個裝序列的『袋子』，知道這個『袋子』的『抽象構造』也有很多的好處︰

The ring of formal power series

The set of all formal power series in X with coefficients in a commutative ring R form another ring that is written R[[X]], and called the ring of formal power series in the variable X over R.

Definition of the formal power series ring

One can characterize $R[[X]]$ abstractly as the completion of the polynomial ring $R[X]$ equipped with a particular metric. This automatically gives $R[[X]]$ the structure of a topological ring (and even of a complete metric space). But the general construction of a completion of a metric space is more involved than what is needed here, and would make formal power series seem more complicated than they are. It is possible to describe $R[[X]]$ more explicitly, and define the ring structure and topological structure separately, as follows.

Ring structure

As a set, $R[[X]]$ can be constructed as the set $R^{\mathbb {N} }$ of all infinite sequences of elements of $R$ , indexed by the natural numbers (taken to include 0). Designating a sequence whose term at index $n$ is $a_{n}$ by $(a_{n})$ , one defines addition of two such sequences by

(a_n)_{n\in\N} + (b_n)_{n\in\N} = \left( a_n + b_n \right)_{n\in\N}

and multiplication by

(a_n)_{n\in\N} \times (b_n)_{n\in\N} = \left( \sum_{k=0}^n a_k b_{n-k} \right)_{n\in\N}.

This type of product is called the Cauchy product of the two sequences of coefficients, and is a sort of discrete convolution. With these operations, $R^{\mathbb {N} }$ becomes a commutative ring with zero element $(0,0,0,\cdots )$ and multiplicative identity $(1,0,0,\cdots )$ .

The product is in fact the same one used to define the product of polynomials in one indeterminate, which suggests using a similar notation. One embeds $R[[X]]$ by sending any (constant) $a \in R$ to the sequence $(a,0,0,\cdots )$ and designates the sequence $(0,1,0,0,\cdots )$ by $X$ ; then using the above definitions every sequence with only finitely many nonzero terms can be expressed in terms of these special elements as $(a_{0},a_{1},a_{2},\cdots ,a_{n},0,0,\ldots )=a_{0}+a_{1}X+\cdots +a_{n}X^{n}=\sum _{i=0}^{n}a_{i}X^{i};$

these are precisely the polynomials in $X$ . Given this, it is quite natural and convenient to designate a general sequence $(a_n)_{n\in\N}$ by the formal expression $\textstyle\sum_{i\in\N}a_i X^i$ , even though the latter is not an expression formed by the operations of addition and multiplication defined above (from which only finite sums can be constructed). This notational convention allows reformulation the above definitions as

\textstyle \left(\sum_{i\in\N} a_i X^i\right)+\left(\sum_{i\in\N} b_i X^i\right) = \sum_{i\in\N}(a_i+b_i) X^i

and $\textstyle \left(\sum_{i\in\N} a_i X^i\right) \times \left(\sum_{i\in\N} b_i X^i\right) = \sum_{n\in\N} \left(\sum_{k=0}^n a_k b_{n-k}\right) X^n.$

which is quite convenient, but one must be aware of the distinction between formal summation (a mere convention) and actual addition.

Topological structure

Having stipulated conventionally that

(a_0, a_1, a_2, a_3, \ldots) = \sum_{i=0}^\infty a_i X^i, \qquad (1)

one would like to interpret the right hand side as a well-defined infinite summation. To that end, a notion of convergence in $R^{\mathbb {N} }$ is defined and a topology on $R^{\mathbb {N} }$ is constructed. There are several equivalent ways to define the desired topology.

We may give $R^{\mathbb {N} }$ the product topology, where each copy of $R$ is given the discrete topology.
We may give $R^{\mathbb {N} }$ the I-adic topology, where $I=(X)$ is the ideal generated by $X$ , which consists of all sequences whose first term $a_{0}$ is zero.
The desired topology could also be derived from the following metric. The distance between distinct sequences (a_n) and (b_n) in R^N, is defined to be

d((a_{n}),(b_{n}))=2^{-k}

where

k

is the smallest natural number such that

a_{k}\neq b_{k}

; the distance between two equal sequences is of course zero.

Informally, two sequences $\{a_{n}\}$ and $\{b_{n}\}$ become closer and closer if and only if more and more of their terms agree exactly. Formally, the sequence of partial sums of some infinite summation converges if for every fixed power of $X$ the coefficient stabilizes: there is a point beyond which all further partial sums have the same coefficient. This is clearly the case for the right hand side of (1), regardless of the values $a_{n}$ , since inclusion of the term for $i=n$ gives the last (and in fact only) change to the coefficient of $X^{n}$ . It is also obvious that the limit of the sequence of partial sums is equal to the left hand side.

This topological structure, together with the ring operations described above, form a topological ring. This is called the ring of formal power series over $R$ and is denoted by $R[[X]]$ . The topology has the useful property that an infinite summation converges if and only if the sequence of its terms converges to 0, which just means that any fixed power of $X$ occurs in only finitely many terms.

The topological structure allows much more flexible use of infinite summations. For instance the rule for multiplication can be restated simply as

\textstyle \left(\sum_{i\in\N} a_i X^i\right) \times \left(\sum_{i\in\N} b_i X^i\right) = \sum_{i,j\in\N} a_i b_j X^{i+j},

since only finitely many terms on the right affect any fixed $X^{n}$ . Infinite products are also defined by the topological structure; it can be seen that an infinite product converges if and only if the sequence of its factors converges to 1.

………

不單祇為了邏輯上之嚴謹，還為著明確合理的『代數運算』法則︰

Operations on formal power series

One can perform algebraic operations on power series to generate new power series.^[1]^[2] Besides the ring structure operations defined above, we have the following.

Power series raised to powers

If n is a natural number we have

\left( \sum_{k=0}^\infty a_k X^k \right)^n = \sum_{m=0}^\infty c_m X^m,

where

c_0 = a_0^n, \quad c_m = \frac{1}{m a_0} \sum_{k=1}^m (kn - m+k) a_{k} c_{m-k},

for m ≥ 1. (This formula can only be used if m and a₀ are invertible in the ring of scalars.)

In the case of formal power series with complex coefficients, the complex powers are well defined at least for series f with constant term equal to 1. In this case, f^α can be defined either by composition with the binomial series (1+x)^α, or by composition with the exponential and the logarithmic series, f^α := exp(αlog(f)), or as the solution of the differential equation f(f^α)′ = αf^αf′ with constant term 1, the three definitions being equivalent. The rules of calculus (f^α)^β = f^αβ and f^αg^α = (fg)^α easily follow.

Inverting series

The series

A = \sum_{n=0}^\infty a_n X^n

in $R[[X]]$ is invertible in $R[[X]]$ if and only if its constant coefficient $a_{0}$ is invertible in $R$ . This condition is necessary, for the following reason: if we suppose that $A$ has an inverse $B=b_{0}+b_{1}x+\cdots$ then the constant term $a_{0}b_{0}$ of $A\cdot B$ is the constant term of the identity series, i.e., it is 1. This condition is also sufficient; we may compute the coefficients of the inverse series $B$ via the explicit recursive formula

</span

An important special case is that the geometric series formula is valid in $K[[X]]$ :

(1 - X)^{-1} = \sum_{n=0}^\infty X^n.

If $R=K$ is a field, then a series is invertible if and only if the constant term is non-zero, i.e., if and only if the series is not divisible by $X$ . This says that $K[[X]]$ is a discrete valuation ring with uniformizing parameter $X$ .

Dividing series

The computation of a quotient $f/g=h$

\frac{\sum_{n=0}^\infty b_n X^n }{\sum_{n=0}^\infty a_n X^n } =\sum_{n=0}^\infty c_n X^n,

assuming the denominator is invertible (that is, $a_{0}$ is invertible in the ring of scalars), can be performed as a product $f$ and the inverse of $g$ , or directly equating the coefficients in $f=gh$ :

c_n = \frac{1}{a_0}\left(b_n - \sum_{k=1}^n a_k c_{n-k}\right).

Extracting coefficients

The coefficient extraction operator applied to a formal power series

f(X) = \sum_{n=0}^\infty a_n X^n

in X is written

\left[ X^m \right] f(X)

and extracts the coefficient of X^m, so that

\left[ X^m \right] f(X) = \left[ X^m \right] \sum_{n=0}^\infty a_n X^n = a_m.

Composition of series

Given formal power series

f(X) = \sum_{n=1}^\infty a_n X^n = a_1 X + a_2 X^2 + \cdots

g(X) = \sum_{n=0}^\infty b_n X^n = b_0 + b_1 X + b_2 X^2 + \cdots,

one may form the composition

g(f(X)) = \sum_{n=0}^\infty b_n (f(X))^n = \sum_{n=0}^\infty c_n X^n,

where the coefficients c_n are determined by “expanding out” the powers of f(X):

c_n:=\sum_{k\in\N, \vert j\vert=n} b_k a_{j_1} a_{j_2} \cdots a_{j_k}.

Here the sum is extended over all (k, j) with k in N and $j\in\N_+^k$ with $|j|:=j_1+\cdots+j_k=n.$

A more explicit description of these coefficients is provided by Faà di Bruno’s formula, at least in the case where the coefficient ring is a field of characteristic 0.

A point here is that this operation is only valid when $f(X)$ has no constant term, so that each $c_{n}$ depends on only a finite number of coefficients of $f(X)$ and $g(X)$ . In other word the series for $g(f(X))$ converges in the topology of $R[[X]]$ .

Example

Assume that the ring $R$ has characteristic 0. If we denote by $\exp(X)$ the formal power series

\exp(X) = 1 + X + \frac{X^2}{2!} + \frac{X^3}{3!} + \frac{X^4}{4!} + \cdots,

then the expression

\exp(\exp(X) - 1) = 1 + X + X^2 + \frac{5X^3}6 + \frac{5X^4}8 + \cdots

makes perfect sense as a formal power series. However, the statement $\exp(\exp(X)) = e \exp(\exp(X) - 1) = e + eX + eX^2 + \frac{5eX^3}{6} + \cdots$

is not a valid application of the composition operation for formal power series. Rather, it is confusing the notions of convergence in $R[[X]]$ and convergence in $R$ ; indeed, the ring $R$ may not even contain any number $e$ with the appropriate properties.

Composition inverse

Whenever a formal series $\textstyle f(X)=\sum_k f_k X^k \in R[[X]]$ has f₀ = 0 and f₁ being an invertible element of R, there exists a series $\textstyle g(X)=\sum_k g_k X^k$ that is the composition inverse of $f$ , meaning that composing $f$ with $g$ gives the series representing the identity function (whose first coefficient is 1 and all other coefficients are zero). The coefficients of $g$ may be found recursively by using the above formula for the coefficients of a composition, equating them with those of the composition identity X (that is 1 at degree 1 and 0 at every degree greater than 1) . In the case when the coefficient ring is a field of characteristic 0, the Lagrange inversion formula provides a powerful tool to compute the coefficients of g, as well as the coefficients of the (multiplicative) powers of g.

Formal differentiation of series

Given a formal power series

f = \sum_{n\geq 0} a_n X^n

in R[[X]], we define its formal derivative, denoted Df or f′, by

Df = \sum_{n \geq 1} a_n n X^{n-1}.

The symbol D is called the formal differentiation operator. The motivation behind this definition is that it simply mimics term-by-term differentiation of a polynomial.

This operation is R–linear:

D(af + bg) = a \cdot Df + b \cdot Dg

for any a, b in R and any f, g in R[[X]]. Additionally, the formal derivative has many of the properties of the usual derivative of calculus. For example, the product rule is valid:

D(fg) = f \cdot (Dg) + (Df) \cdot g,

and the chain rule works as well:

D(f\circ g ) = \left( Df\circ g\right) \cdot Dg,

whenever the appropriate compositions of series are defined (see above under composition of series).

Thus, in these respects formal power series behave like Taylor series. Indeed, for the f defined above, we find that

(D^k f)(0) = k! a_k,

where D^k denotes the kth formal derivative (that is, the result of formally differentiating k times).

當然最好親自動手紙筆練習，熟練後何仿看看 Sympy 之

Formal Power Series

Methods for computing and manipulating Formal Power Series.

class sympy.series.formal.FormalPowerSeries

Represents Formal Power Series of a function.

No computation is performed. This class should only to be used to represent a series. No checks are performed.

For computing a series use fps().

，讓電腦代勞的吧！

2017 年 2 月
日	一	二	三	四	五	六
« 1 月				3 月 »
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28

Definition

Univariate case

Multivariate case

Properties

Power series

Probabilities and expectations

Definition

Solving

Solving homogeneous linear recurrence relations with constant coefficients

Roots of the characteristic polynomial

Solving non-homogeneous linear recurrence relations with constant coefficients

The ring of formal power series

Definition of the formal power series ring

Ring structure

Topological structure

Operations on formal power series

Power series raised to powers

Inverting series

Dividing series

Extracting coefficients

Composition of series

Example

Composition inverse

Formal differentiation of series

輕。鬆。學。部落客