Outils pour utilisateurs

Outils du site


math:2:nzq

Nombres entiers et récurrence, nombres rationnels

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 :

  • la proposition $\mathcal{H}(n_{0})$ est vraie,
  • pour tout $n\geqslant n_{0}$; la proposition $\left[\mathcal{H}(n)\implies\mathcal{H}(n+1)\right]$ est vraie.

Alors, pour tout entier $n\geqslant n_{0}$, la proposition $\mathcal{H}(n)$ est vraie.

Remarques

  • On peut montrer par récurrence que, pour tout entier naturel $n$ non nul, on a :
    $$\ds\sum_{k=1}^{n}{k}=\frac{n(n+1)}{2}$$ $$\ds\sum_{k=1}^{n}{k^{2}}=\frac{n(n+1)(2n+1)}{6}$$ $$\ds\sum_{k=1}^{n}{k^{3}}=\left(\frac{n(n+1)}{2}\right)^{2}$$ $$\ds\sum_{k=0}^{n}{q^{k}}=\begin{cases} n+1 & \text{si}\; q=1\\ \ds\frac{1-q^{n+1}}{1-q} & \text{si}\; q\ne1 \end{cases}$$ Cette dernière somme s'applique encore dans le cas où $q\in\C$.
    Remarque : Même si le programme officiel ne l'exige pas, il convient de connaître les résultats des sommes 2 et 3 de cette liste ainsi qu'une technique pour les retrouver (la récurrence n'étant pas la seule).
  • Soit $(u_{n})_{n\geqslant p}$ une suite réelle. Pour tout couple $(m,n)$ d'entiers tels que $n\geqslant m\geqslant p$, on a :
    $${\ds\sum_{k=m}^{n}{\left[u_{k+1}-u_{k}\right]}=u_{n+1}-u_{m}}$$ Remarque : Il convient de connaitre ce résultat dit de télescopage.

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 :

  • les $p$ propositions $\mathcal{H}(n_{0}),\dots,\mathcal{H}(n_{0}+p-1)$ sont vraies,
  • pour tout $n\geqslant n_{0}$ la proposition $\left[\left(\mathcal{H}(n)\,\text{et}\,\dots\,\text{et}\,\mathcal{H}(n+p-1)\right)\implies\mathcal{H}(n+p)\right]$ est vraie.

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}$.

  1. Montrer que $P_{n}$ est un polynôme unitaire de degré $n$ pour tout entier $n\geqslant0$.
  2. Montrer que $P_{2n+1}$ admet 0 pour racine pour tout entier $n\geqslant0$. Que vaut $P_{2n}(0)$ pour tout entier $n\geqslant0$ ?

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 :

  • la proposition $\mathcal{H}(n_{0})$ est vraie,
  • pour tout $n\geqslant n_{0}$ la proposition $\left[\left(\mathcal{H}(n_{0})\,\text{et}\,\dots\,\text{et}\,\mathcal{H}(n)\right)\implies\mathcal{H}(n+1)\right]$ est vraie.

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$$

math/2/nzq.txt · Dernière modification: 2020/05/12 08:29 par Alain Guichet