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

義大利的數學家朱塞佩‧皮亞諾 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},$ 
 
太自然反倒費疑猜的哩☆

日	一	二	三	四	五	六
« 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

FreeSandal

每日彙整: 2017-02-25

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

Recurrence relation

Solving

Solving homogeneous linear recurrence relations with constant coefficients

Roots of the characteristic polynomial

Solving non-homogeneous linear recurrence relations with constant coefficients

輕。鬆。學。部落客