例：證明由｛a，b，c，d｝四個標識符利用十、一運算符組成的任意算術表達式中，所含標識符的個數一定等於這個表達式中運算符的個數加1。
證設任意的表達式為f，而歸納變元n為f中所含運算符的個數。
奠基n=0，則f由一個標識符組成(因為沒有運算符)，所以命題成立。
歸納假設n≤k時本命題成立，現證n=k+1時本命題也成立。f一定是下述兩種情況之一
f是f1+f2或
f是f1-f2
其中f1，f2所含的運算符個數都小於k+1，對f1，f2使用歸納假設，可得f1+f2，f1-f2中所含標識符個數也比各自所含的運算符的個數多1。
4、廣義歸納法
數學歸納法不僅可用於含有自然數變元n的命題，經推廣後，還可用於含有某些其它集合上的命題，這種集合，稱為歸納集。對於一個含有某個歸納集上的變元x的待證命題P(x)，所用的歸納法稱之為廣義歸納法。
定義設有一個集合A，如果它滿足下麵三個性質
(1)a1，a2，…，an是A中的元素(n≥1)；
(2)如果x是A中元素，則f11(x)，f12(x)，…，f1n1(x)也是A中的元素(n1＞0)；
如果x，y是A中元素，則f21(x，y)，
f22(x，y)，…，f2n2(x，y)也是A中元素(n2＞0)；…；
如果x1，…，xm是A中元素，則fn1(x1，…，xm)、fm2(x1，…，xm)，…，fmnn(x1，…，xm)也是A中元素(m≥1，nm＞0)。
(3)A中的元素僅限於此。
則A稱之為歸納集，a1，a2，…，an稱為該集的開始元素，諸f11稱為該集的生成函數(其中第一下標為該函數的元素，第二下標以區分具有同樣元數的各函數)。
按照上述的定義，自然數集是歸納集，它的開始元素是O，生成函數是f(x)=x+1。
前例中集合｛a，b，c，d｝的元素利用+，-運算所構成的一切表達式的集合是歸納集，開始元素是a，b，c，d，生成函數為f21(x，y)=x+y，f22(x，y)=x-y。
在證明含有某個歸納集A上的變元x的待證命題P(X)可用如下的廣義歸納法。
奠基步要證明P(a1)，P(a2)，…，P(an)成立。這裏a1，a2，…，a是A中的開始元素。
歸納步要證明對於1≤i≤m及1≤j≤n1的所有i，j，對於A中的任何元素x1，x2，…，x1，如果P(x1)，P(x2)，…，P(x1)成立，則P(fu(x1，…，xi)也成立。在例4中，因為表達式所組成的集合是歸納集(記為A)，我們可用廣義歸納法證之。
奠基：對於A中的四個開始元素a，b，c，d，因為它們的標識符個數為1，而運算符個數均為O，所以命題成立。
歸納，對於A中的元素x，y，f21(x，y)=x+y中，我們設
x+y標識符個數為m，運算符個數為n，
x中標識符個數為m1，運算符個數為n1；
y中標識符個數為m2，運算符個數為n2，則
m=m1+m2=(n1+1)+(n2+1)
=(n1+n２+1)+1=n+1
同理可證f22(x，y)=x-y也有如上的結果，故依廣義歸納法，本命題成立。