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時命題也成立,通常稱這種形式的歸納法為第一歸納法。
除此之外,數學歸納法還有許多變通的形式,如第二歸納法,逆向歸納法,跳越歸納法,翹翹板歸納法等。