On rappelle que $\N$ désigne l'ensemble des entiers naturels, $\Z$ celui des entiers relatifs et $\Q$ celui des nombres rationnels (on ne rappelle pas les opérations entre leurs éléments). Rappelons par contre que, si $a$ et $b$ sont deux entiers (relatifs ou pas) tels que $a\leqslant b$, alors $[\![ a,b]\!]$ désigne l'ensemble des entiers $n$ tels que $a\leqslant n\leqslant b$ (ou encore $[\![ a,b]\!]=[a,b]\cap\Z$). De même, $[\![ a,+\infty[\![$ désigne l'ensemble des entiers $n$ tels que $a\leqslant n$ (ou encore $[\![ a,+\infty[\![ =\left[a,+\infty\right[\cap\Z$). Rappels sur $\ds\binom{n}{k}$.
Théorème : Axiome de récurrence, équivalent à l'existence de $\N$, admis
Soit $n_{0}$ un entier naturel. Soit $(\mathcal{H}(n))_{n\geqslant n_{0}}$ une famille de propositions telles que :
Alors, pour tout entier $n\geqslant n_{0}$, la proposition $\mathcal{H}(n)$ est vraie.
Remarques
Théorème : Récurrence à plusieurs pas
Soit $n_{0}$ un entier naturel. Soit $p$ un entier supérieur ou égal à 2. Soit $(\mathcal{H}(n))_{n\geqslant n_{0}}$ une famille de propositions telles que :
Alors, pour tout entier $n\geqslant n_{0}$, la proposition $\mathcal{H}(n)$ est vraie.
Exemple : Situation typique de récurrence à 2 pas
On définit les polynômes: $P_{0}=1$, $P_{1}=X$ et $\forall n\in\N,\; P_{n+2}=XP_{n+1}-(X+2)P_{n}$.
Théorème : Récurrence forte, plus rare
Soit $n_{0}$ un entier naturel. Soit $(\mathcal{H}(n))_{n\geqslant n_{0}}$ une famille de propositions telle que :
Alors, pour tout entier $n\geqslant n_{0}$, la proposition $\mathcal{H}(n)$ est vraie.
Exemple
Soit $a\in\C$ et $n\in\N$. Soit $(\lambda_{1},\dots,\lambda_{n})\in\C^{n}$ tel que :
$$\ds\sum_{k=0}^{n}{\lambda_{k}(X-a)^{k}}=\Theta$$ Montrer que :
$$\ds\forall k\in[\![0,n]\!],\;\lambda_{k}=0$$