歸納法證整除

證「對所有正整數 $n$,某式是 $m$ 的倍數」的歸納法:起始驗證 $n=1$;歸納假設寫成「$n=k$ 的式子 $=mq$,$q$ 是整數」;歸納步驟把 $n=k+1$ 的式子拆成「$n=k$ 的式子」加上一個明顯是 $m$ 倍數的部分。

拆法有兩種:多項式就展開後分組,例如證 $n^3+2n$ 是 $3$ 的倍數時,$(k+1)^3+2(k+1)=(k^3+2k)+3(k^2+k+1)$;指數式就湊出原式,例如 $a^{k+1}-1=a(a^k-1)+(a-1)$;兩個指數相減就補一項再扣一項,例如 $a^{k+1}-b^{k+1}=a(a^k-b^k)+a\cdot b^k-b\cdot b^k=a(a^k-b^k)+(a-b)b^k$。常見漏洞是沒寫出 $q$ 是整數,或拆完剩下的部分沒說明為何是倍數。

例:$4^n-1$ 是 $3$ 的倍數。$n=1$:$3$。設 $4^k-1=3q$,則 $4^{k+1}-1=4(4^k-1)+3=3(4q+1)$。