Importance de l'initialisation
Attention : Attention à la phase d'initialisation
La première étape d'initialisation de la récurrence est souvent très simple à réaliser.
Elle semble parfois tellement simple qu'on peut être tenté de l’oublier pour se focaliser sur l'hérédité qui est souvent plus délicate à montrer.
L'exemple suivant montre qu'une récurrence non initialisée peut mener à des résultats absurdes.
Exemple : Récurrence non initialisée
Soit \(\mathcal P_n\) la propriété « \(2^n\) est un multiple de 3 »
.
Cette propriété est héréditaire. En effet :
Si on suppose que \(\mathcal P_k\) est vraie, alors \(2^k=3\times N\) où \(N\) est un entier.
Mais alors \(2^{k+1}=2\times 2^k=2\times 3\times N=3\times(2\times N)\) puisque \(\mathcal P_k\) est vraie.
Cette dernière écriture montre que \(2^{k+1}\) est un multiple de 3, donc que \(\mathcal P_{k+1}\) est vraie.
Pourtant il est bien évident qu'une puissance de 2 ne pourra jamais être divisible par 3 ! ! La propriété n'est pas initialisable et on ne peut tirer aucune conclusion de l'hérédité.