初等數(shù)論3函數(shù)方程的遞歸解法

1、3函數(shù)方程的遞歸解法（上）上節(jié)最后幾個例題清楚地表明，對于由自然數(shù)的函數(shù)組成的方程，代換法是一個相當有效的方法. 但是，這種方法也會有失效的時候. 請看例1中由養(yǎng)兔問題而得到的函數(shù)方程：如果分別令就得到加在一起，得仍然未能求得我們所需要的函數(shù)，即無法用n的代數(shù)式來表示.這時候，使用一種叫遞歸法的方法，也許會獲得成功.我們知道，定義在自然數(shù)上的函數(shù)，當自變量n依次取1，2，3，等值時，就形成一個數(shù)列因而可以借助于數(shù)列對這種函數(shù)組成的函數(shù)方程加以研究.給出一個數(shù)列，通?？捎腥N方法：一是用通項公式，一是用遞推公式，一是用遞歸公式. 所謂通項公式，就是用自然數(shù)n的表達式來表示數(shù)列的“通項”的公式.

2、所謂遞推公式，就是由含有數(shù)列前邊的若干項的表達式來表示后邊某一項的公式. 如果這種表達式中僅含數(shù)列前邊的若干項（允許有常數(shù)系數(shù)），這個公式就叫遞歸公式.例如自然數(shù)列，用通項公式來表示是 （51）用遞推公式來表示就是 （52）用遞歸公式來表示又成為 （53）又如自然數(shù)的平方組成的數(shù)列它的這三個公式分別是通項公式： （54）遞推公式： （55）遞歸公式： （56）這里有幾個關(guān)系值得注意：第一，通項公式與其他兩個公式的關(guān)系. 從函數(shù)方程的觀點看來，遞推、遞歸公式實際上都是函數(shù)方程，而通項公式則是它們的解. 這一點，從（51）（53），（54）（56）可以明顯地看出來.第二，遞推公式與遞歸公式間的關(guān)系

3、. 從定義上看，遞歸公式也是一種遞推公式，二者是從屬關(guān)系，或特殊與一般的關(guān)系. 不過為了敘述上的方便，我們把只含數(shù)列中的項（可以帶有系數(shù)）的遞推公式叫遞歸公式. 遞歸公式的一般形式是 （57）這是用數(shù)列中連續(xù)k項的表達式來表示緊接著的后一項. 這里，是常數(shù)系數(shù). 公式（57）更精確地稱做是k階遞歸公式.一般來說，由遞推公式能夠推導出遞歸公式. 以（55）的遞推公式為例.因為同樣地有后式減去前式，移項得類似地有后式減去前式，移項得 （58）這是一個三階遞歸公式.第三，三個公式與數(shù)列的關(guān)系. 一旦給出通項公式，數(shù)列便被唯一地確定了. 但遞推公式特別是遞歸公式卻不然. 給出一個遞歸公式后，會有無窮多

4、數(shù)列都滿足這個遞歸公式. 這是因為，由k階遞歸公式的數(shù)列，它的前k項無法由遞歸公式本身確定. 但當給出了這個數(shù)列的前k項的值后，遞歸公式就唯一地確定了數(shù)列. 我們把數(shù)列前k項的值叫初值條件. 同一個遞歸公式，由于初值條件不同，將得到不同的數(shù)列.例如，遞推公式（58）是一個三階遞歸公式. 只有當初值條件取時，才對應(yīng)自然數(shù)的平方的數(shù)列. 事實上，如果改變初值條件，比如取時，不難算得：數(shù)列就不再是自然數(shù)平方數(shù)列了.一般說來，遞歸公式（57）可以對應(yīng)無窮多的數(shù)列，只要選取不同的初值條件，亦即對數(shù)列的前k項給以不同的值就行了. 反過來說，有無窮多個數(shù)列滿足遞歸公式（57）. 只有在初值條件給出后，數(shù)列才

5、完全確定.特別是，我們能夠構(gòu)造出首項為1，公比為q的等比數(shù)列，使它滿足遞歸公式（57）：事實上，只要公比滿足方程 （58）就可以了. 方程（58）兩邊同除以，得. （59）這就是說，公比q應(yīng)當是方程（59）的根. 這樣一來，一個等比數(shù)列，只要當它的公式q滿足以k階遞歸公式（57）的相當系數(shù)為系數(shù)的代數(shù)方程（59）時，它必能滿足這個遞歸公式.方程（59）叫遞歸公式（49）的特征方程.還應(yīng)當指出：如果一個數(shù)列滿足遞歸公式（57），那末給數(shù)列的各項乘以相同的常數(shù)，所得的新數(shù)列仍滿足原遞歸公式（57）；如果兩個數(shù)列都滿足同一個遞歸公式（57），那末它們對應(yīng)項的和所組成的新數(shù)列仍滿足原遞歸公式（57）；

6、由此又得到：如果兩個數(shù)列都滿足同一個遞歸公式（57），那末，給兩數(shù)列的各項分別乘以常數(shù)（同一數(shù)列的各項要乘同一常數(shù)，但兩數(shù)列所乘的常數(shù)可不必相同），再把對應(yīng)項加起來，所成的數(shù)列仍滿足原遞歸公式（57）.上述這些性質(zhì)都顯而易見，證明也并不難.應(yīng)用所有這些結(jié)果，即可解某些定義在自然數(shù)上的函數(shù)方程了.例15 解由例1的養(yǎng)兔問題而得的函數(shù)方程 （5）解 對應(yīng)的特征方程是 （60）解這個方程，得如前所述，數(shù)列滿足遞歸公式（5）. 這里A，B是待定的常數(shù). 它們滿足初值條件解由方程（61），（62）組成的方程組，得. 就是 （63）這就是說，第n個月，共有大兔對.誠然，公式（63）是不便于實際計算的. 但利用下列近似數(shù)值和常用對數(shù)表，即可求得的近似值：例如n=12時，1.6180312 =321.992，(-0.61803)12 =0.003，321.9920.003=321.989. 321.989×0.447211.44. 即一年后大兔有144對. 使用數(shù)學歸納法或其他方法，可以證明對任何n