Tümevarım bir teoremdir. Şunu söyler:
P(n) doğal sayılarla parametrize edilmiş bir önerme olsun. Eğer P(0) doğruysa ve her n için P(n) doğru iken P(n+1) de doğruysa, her n∈N için P(n) doğrudur.
Sezgisel olarak bu teoremin kanıtı söyledir: Diyelim ki P(0) doğru ve her n için P(n) doğru iken P(n+1) de doğru. O zaman, P(0) doğru olduğundan P(1) doğru. P(1) doğru olduğundan P(2) doğru. Böyle giderek her n için P(n) doğru olmalı. Tümevarım teoremini sonsuz uzunlukta bir domino taşı dizisi üzerinde görebiliriz. P(n) doğru iken P(n+1)'in doğru olması n numaralı domino taşını devirince n+1 numaralı taşın da devrildiği manasında okuyabiliriz. Tabi ki, P(0)'ın doğru olması 0 numaralı domino taşını devirdiğimiz manasında geliyorsa, bütün domino taşları devrilecektir çünkü bir taşın devrilmesi bir sonrakisinin devrilmesi gerektiriyor.
Tümevarım teoreminin gerçek bir kanıtı şudur: Diyelim ki bir n için P(n) doğru değil, buradan bir çelişki elde etmek istiyorum. Böyle n'lerin en küçüğünü alalım. Tabi ki n=0 olamaz çünkü P(0) doğru. O zaman n=k+1, yazabilirim ve k<n olduğundan P(k) doğrudur. Fakat teoremin varsayımı gereği P(k) doğru ise P(k+1) de doğru olmalı, çelişki. Demek ki her n∈N için P(n) doğru.