Soit $\mathcal{P}(n)=$“le nombre entier $n$ est divisible par $2$”. Alors $\mathcal{P}(1)$ est fausse, $\mathcal{P}(2)$ est vraie, $\mathcal{P}(3)$ est fausse, etc. Donc on peut tout de suite résoudre tous les cas: $\mathcal{P}(n)$ est vraie si $n$ est pair, fausse si $n$ est impair.

Supposons qu’un certain univers contienne une infinité de galaxies. Soit $\mathcal{P}(n)$ la propriété “il existe, dans cet univers, une galaxie dans laquelle on peut trouver exactement $n$ planètes sur lesquelles on trouve de la vie”.
Si on fixe un $n$ et qu’on se pose la question de savoir si $\mathcal{P}(n)$ est vraie ou fausse, on n’a qu’un seul moyen d’obtenir la réponse: parcourir tout l’univers jusqu’à trouver une galaxie contenant exactement $n$ planètes sur lesquelles on trouve la vie.

Dans l’exemple du dessus (galaxies), il n’y a aucune corrélation du genre entre les propriétés $\mathcal{P}(n)$ pour des $n$ différents, puisque savoir que $\mathcal{P}(n)$ est vraie n’implique pas forcément que $\mathcal{P}(n+1)$ soit vraie aussi.

Supposons que l’on ait devant nous une très longue table sur laquelle sont posés une infinité d’ordinateurs, numérotés $1,2,3,\dots$. On découvre avec effroi que sur chacun de ces ordinateurs est installé un système opérationnel propriétaire, issu d’une grande compagnie. On suppose que ces ordinateurs sont tous allumés, et que pour tout $n$, le $n$-ème ordinateur envoie constamment des données non-cryptées vers son voisin $n+1$. Dans ce cas, il est absolument certain que si l’ordinateur $n$ est infecté par un virus, alors l’ordinateur $n+1$ est infecté aussi. En d’autres termes, si on définit la propriété $\mathcal{P}(n)=$“le $n$ème ordinateur est infecté par un virus”, on sait que si $\mathcal{P}(n)$ est vraie, alors $\mathcal{P}(n+1)$ est vraie aussi.
Ceci a la conséquence suivante: si un seul de ces ordinateurs est infecté, alors tous les suivants le sont aussi. En particulier, si le premier est infecté, alors tous sont infectés.

Nous allons montrer que pour tout $n\in {\mathbb{N}}^{\ast }$, $$\boxed{1+2+3+4+\cdots +n=\frac{n(n+1)}{2}}$$ Commençons par nommer les deux membres de l’identité ci-dessus, en posant $$a_n:=1+2+3+4+\cdots +n,\text{ et }{b}_n:=\frac{n(n+1)}{2}.$$ Pour un $n$ spécifique pas trop grand, on peut toujours le vérifier en calculant la valeur de $a_n$, puis celle de $b_n$, puis de voir si elles sont égales. Par exemple,

• pour $n=1$, on a $a_1=1$ et $b_1=\frac{1\cdot 2}{2}=1$, et donc $a_1=b_1$
• pour $n=2$, on a $a_2=1+2=3$ et $b_2=\frac{2\cdot 3}{2}=3$, et donc $a_2=b_2$.

On voit donc que $a_1=b_1$ et $a_2=b_2$.
On pourrait continuer à vérifier la relation “$a_n=b_n$” pour des $n$ toujours plus grands, en calculant séparément les nombres $a_n$ et $b_n$ “à la main”, et en vérifiant qu’ils sont effectivement égaux. Mais ceci n’exclut pas qu’il existe un $n$, éventuellement très grand, pour lequel $a_n\ne b_n$!
Définissons donc, pour tout $n⩾1$, la propriété $\mathcal{P}(n)$ comme étant: “pour l’entier $n$, on a $a_n=b_n$”. Montrons, par récurrence, que $\mathcal{P}(n)$ est vraie pour tout $n⩾1$.

1. Initialisation: on a déjà vérifié plus haut, “à la main”, que $a_1=b_1$, et donc on sait que $\mathcal{P}(1)$ est vraie.
2. Pas d’induction: supposons que pour un $n$ donné (dont on n’a pas besoin de spécifier la valeur), $\mathcal{P}(n)$ est vraie , c’est-à-dire que l’on a effectivement
   $$a_n=b_n.$$
   Pour montrer que ceci entraîne que $\mathcal{P}(n+1)$ est vraie, on va faire un calcul, à l’issue duquel on obtiendra que $a_{n+1}=b_{n+1}$. Or la structure du problème fait que $a_{n+1}$ peut être relié à $a_n$. En effet,
   $$a_{n+1}=1+2+3+4+\cdots +n+(n+1)=a_n+(n+1).$$
   Mais, puisque l’on est en train de supposer que $a_n=b_n$, on peut l’utiliser et faire un peu d’arithmétique:
   $$\begin{array}{rl}{a}_{n+1}& =b_n+(n+1)\\ & =\frac{n(n+1)}{2}+(n+1)\\ & =\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}.\end{array}$$
   Mais puisque
   $$\frac{(n+1)(n+2)}{2}=\frac{(n+1)((n+1)+1)}{2}=b_{n+1},$$
   on a bien montré que $a_{n+1}=b_{n+1}$. Ceci montre que si $\mathcal{P}(n)$ est vraie, alors $\mathcal{P}(n+1)$ est vraie aussi.

On a donc bien montré que $\mathcal{P}(n)$ est vraie pour tout $n⩾1$.

Posons, pour tout $n⩾1$, $a_n=10^n-1$, et considérons l’affirmation $\mathcal{P}(n)$ définie par “$a_n$ est un multiple de $9$”.

1. Pour $n=1$, on a $a_1=10^1-1=9$, qui est un multiple de $9$.
2. Supposons que $\mathcal{P}(n)$ est vraie, c’est-à-dire que $a_n$ est un multiple de $9$. Ceci s’exprime en disant qu’il existe un entier $k$ tel que $a_n=9k$. Remarquons alors qu’on peut écrire
   $$\begin{array}{rl}{a}_{n+1}=10^{n+1}-1& =10\cdot 10^n-1\\ & =10(a_n+1)-1\\ & =10(9k+1)-1=9(\underset{=:k^{\prime }}{\underbrace{10k+1}}).\end{array}$$
   Or puisque $k$ est un entier, $k^{\prime }=10k+1$ est aussi un entier. Donc $a_{n+1}=9k^{\prime }$: $a_{n+1}$ est aussi un multiple de $9$, et donc $\mathcal{P}(n+1)$ est vraie.

Ceci montre que $\mathcal{P}(n)$ est vraie pour tout $n⩾1$.