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

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

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

3、. 從定義上看，遞歸公式也是一種遞推公式，二者是從屬關(guān)系，或特殊與一般的關(guān)系. 不過(guò)為了敘述上的方便，我們把只含數(shù)列中的項(xiàng)（可以帶有系數(shù)）的遞推公式叫遞歸公式. 遞歸公式的一般形式是 （57）這是用數(shù)列中連續(xù)k項(xiàng)的表達(dá)式來(lái)表示緊接著的后一項(xiàng). 這里，是常數(shù)系數(shù). 公式（57）更精確地稱做是k階遞歸公式.一般來(lái)說(shuō)，由遞推公式能夠推導(dǎo)出遞歸公式. 以（55）的遞推公式為例.因?yàn)橥瑯拥赜泻笫綔p去前式，移項(xiàng)得類似地有后式減去前式，移項(xiàng)得 （58）這是一個(gè)三階遞歸公式.第三，三個(gè)公式與數(shù)列的關(guān)系. 一旦給出通項(xiàng)公式，數(shù)列便被唯一地確定了. 但遞推公式特別是遞歸公式卻不然. 給出一個(gè)遞歸公式后，會(huì)有無(wú)窮多

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

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

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