Sur l'excellent site consacré à l'histoire des mathématiques :

Je vous encourage à écouter une histoire de l'idée du raisonnement par récurrence. On a mis de nombreux siècles pour parvenir à la formalisation actuelle :

C'est ici... (cliquer en bas pour démarrer l'enregistrement.)

On rencontre en chemin le triangle de Pascal, qui fait aussi partie du chapitre sur la combinatoire.