Soit P un prédicat concernant un paramètre entier n.
P(n) vrai  signifie donc : "n possède la propriété n".
On suppose que:
Il s'en suit que:
On en conclut que P(n) est vrai  ∀ n ∈ ℕ.
C'est le principe même du 'raisonnement par récurrence' sous sa forme la plus simple.
Il y a, bien sûr quelques variantes:
Evidemment si au lieu de P(0) vrai on sait seulement que P(n0) est vrai on a seulement:
P(n) vrai pour n ≥ n0.
Si on sait que P(0) est vrai et que ∀n P(n) ⇒ P(n+2), on en conclut que P(n) est vrai pour n pair
Si on sait que P(1) est vrai et que ∀n P(n) ⇒ P(n+2), on en conclut que P(n) est vrai pour n impair
Si on sait que P(0) et P(1) sont  vrais et que ∀n P(n) ⇒ P(n+2), on en conclut que P(n) est vrai pour tout  n .
On peut aussi faire une récurrence sur ℤ.
Si P(0) est vrai, si ∀n P(n) ⇒ P(n+1) et ∀n P(n) ⇒ P(n-1), on en conclut que P(n) est vrai  ∀  n ∈ ℤ.

On a aussi des formes de 'récurrence multiple'.
Soit au niveau de l'hypothèse de récurrence:
Alors ∀ n P(n) est vrai.

Soit au niveau du nombre des variables:
Alors P(m,n) est vrai ∀ (m,n) ∈ ℕ×ℕ

On a enfin la 'récurrence forte' Alors P(n) est vrai ∀ n.
Voir les exercices de ce paragraphe pour des exemples.

Nous avons déjà vu des exemples de raisonnement par récurrence:
Nombre de parties d'un ensemble
Relation entre les coefficients C n p
Le point faible de toutes les formes de raisonnement par récurrence est qu'ils vérifient des propriétés, mais qu'ils ne les établissent pas directement. On ne peut pas trouver par récurrence un résultat dont on n'a a priori aucune idée. Ce qui fait qu'en pratique on est obligé, quand on ne connaît pas le résultat de traiter 'manuellement' un grand nombre de petites valeurs  de la variable pour avoir une idée de la loi. C'est seulement après ce travail, disons d'intuition, que le raisonnement par récurrence viendra conforter le chercheur dans sa conviction.