3、減元過渡

為了實現歸納過渡,我們根據證明需要,減少一些元的個數,這也是一種退的策略。

例:在一塊平地上站有n個人,對每個人來說,他們到其他人的距離均不相同,每人都有一支水槍,當發出火災信號時,每人都用水槍擊中距他最近的人,證明,當n為奇數時其中至少有一人身上是幹的。

證明:當n=1時,結論顯然成立,設命題對n=2k-1成立,下證當n=2k+1時命題也成立,設A與B兩人之間的距離在所有的兩人間的距離中為最小,撤出A、B兩人,則由歸納假設知,在剩下的2k-1個人中間,至少有一人C的身上是幹的,再把A、B兩人加進去,由於AC>AB,BC>AB,所以A、B兩人都不會用水槍去擊C,從而C身上仍然是幹的,所以對一切奇數n命題都成立。

這裏先撤出兩人的目的是為了利用歸納假設,之所以撤進A、B兩人,是為了方便地把他們加進去,先退而後進,使問題順利地得到解決。

4、削弱命題

所謂削弱命題,就是先證明一個較原命題為弱的命題,然後以此為基礎再去解決原命題,從而起到減少難度,分散難點的作用,其目的仍是退中求進。

例:設函數f對一切自然數n都有定義,f(n)皆為自然數,且有f(n+1)>f(f(n)),證明,對一切自然數n,都有f(n)=n。

證明:我們先來證明一個較弱的命題:

命題A、若自然數m≥n,則有f(m)≥n,在證得這個命題(A)後,再設法證f(n)=n。

對n使用數學歸納法。

當n=1時,對一切自然數m≥1,都有f(m)≥1,命題(A)成立。

假設當n=k時,命題(A)成立,下證當n=k+1時,命題(A)也成立,即證對一切m≥k+1都有f(m)≥k+1。

由m≥k+1得m-1≥k,應用歸納假設有f(m-1)≥k,注意到f(m-1)也是一個自然數,於是兩次應用歸納假設,有f(f(m-1))≥k,結合題目條件,即得:

f(m)=f(m-1)+1>f(f(m-1))≥k

既然f(m)是大於k的自然數,當然就有

f(m)≥k+1

所以當n=k+1時,命題(A)也成立,這樣我們便證明了對一切自然數n,命題(A)都成立,下證對一切自然數n,都有f(n)=n、

在命題(A)中,取m=n,即得:

f(n)≥n()

結合題目條件和不等式(),又有:

f(n+1)>f(f(n))≥f(n)、

這表明f嚴格單調上升,且有n+1>f(n),與()聯立,即得:

n≤f(n)<n+1

既然f(n)是自然數,故知必有f(n)=n、

5、程式變通

我們知道,數學歸納法有兩個基本步驟,這就是先對n的一切具體的數值驗證命題能否成立,接著再試圖在“命題已對n的較小值成立”的前提下,推出它對n的較大值也成立,這兩個步驟缺一不可,絲毫沒有通融的餘地。

但是,有時為了便於實現歸納過渡,順應問題的具體特點,在不違背數學歸納法基本規則的前提下,靈活實施變通,這也是一種退中求進的思維策略。

例如,數學歸納法的最基本的形式是:

(1)驗證命題對最初的一個n值成立,通常是對n=1驗證;

(2)在假定n=k時命題成立的前提下,驗證當n=k+1時命題也成立,通常稱這種形式的歸納法為第一歸納法。

除此之外,數學歸納法還有許多變通的形式,如第二歸納法,逆向歸納法,跳越歸納法,翹翹板歸納法等。