Cours et vidéos

Cours en ligne Vidéos classées

Concours corrigés

HECS
HECE

Programme de concours

HECS

Chaîne Youtube


Pour me soutenir



Autour du site

Auteur du site.
Cours particuliers.

Dans ce chapitre nous allons étudier le principe de récurrence sous tout les aspects exigibles en prépa ECS. Vous pouvez visionnez les vidéo si vous avez quelques lacunes, ou bien si vous vous sentez d'attaque, travailler directement les exercices proposés issus presque tous des concours.

Plan


Principe de récurrence


Dans cette vidéo je vous explique le principe de récurrence avec deux exemples d'applications ainsi que quelques conseils simples pour bien mener votre récurrence.

Synopsis :

Niveau d'accessibilité : Terminale.

Prérequis : Connaître un petit peu le formalisme ensembliste (ensembles des entiers naturels, symbole d'appartenance, symbole "pour tout"). Savoir manipuler les inéquations.


Exercices


Exercice (suite géométrique) : Soit $(u_n)_{n\in\mathbb N}$ une suite réelle et $q\in\mathbb R$ tels que $$\forall n\in\mathbb N,\ u_{n+1}=qu_n.$$ Montrer par récurrence que $\forall n\in\mathbb N,\ u_n=q^nu_0$.

Afficher le corrigé

On pose $P_n:"u_n=q^nu_0"$.

Initialisation : Si $n=0$, on a $q^0u_0=u_0$ donc $P_0$ est vraie.

Hérédité : Si $P_n$ est vraie on a $u_n=q^nu_0$. On multiplie cette équation par $q$, alors $qu_n=q^{n+1}u_0$. Mais par hypothèse $u_{n+1}=qu_n$ par conséquent $u_{n+1}=q^{n+1}u_0$ ce qui prouve $P_{n+1}$. On a donc prouvé que $P_n\Longrightarrow P_{n+1}$, c'est à dire l'hérédité.

Par récurrence on a montré que $\forall n\in\mathbb N,\ u_n=q^nu_0$.

Ce type d'exercice apparaît par exemple dans :


Exercice (suite sous-géométrique) : Soit $(u_n)_{n\in\mathbb N}$ une suite réelle et $q\in\mathbb R^+$ tels que $$\forall n\in\mathbb N,\ u_{n+1}\leq qu_n.$$ Montrer par récurrence que $\forall n\in\mathbb N,\ u_n\leq q^nu_0$.

Afficher le corrigé

On pose $P_n:"u_n\leq q^nu_0"$.

Initialisation : Si $n=0$, on a $q^0u_0=u_0$ donc nécessairement $u_0\leq q^0u_0$ (l'égalité impliquant l'inégalité au sens large) et $P_0$ est vraie.

Hérédité : Si $P_n$ est vraie on a $u_n\leq q^nu_0$. On multiplie cette équation par $q$, $q$ étant positif on a $qu_n\leq q^{n+1}u_0$. Mais par hypothèse $u_{n+1}\leq qu_n$ par conséquent : $$u_{n+1}\leq qu_n\leq q^{n+1}u_0,$$ d'où $u_{n+1}\leq q^{n+1}u_0$, donc $P_{n+1}$ est vraie.

Par récurrence on a montré que $\forall n\in\mathbb N,\ u_n\leq q^nu_0$.

Ce type d'exercice apparaît par exemple dans :


Exercice (suite sous géométrique, adapté de ECRICOME 2012, exercice 1, 6.(a)) : Soit $f:\mathbb R\to\mathbb R$ une fonction telle que $$\forall (x,y)\in\mathbb R,\ |f(x)-f(y)|\leq\frac{1}{2}|x-y|.$$ On suppose d'autre part qu'il existe $\alpha\in\mathbb R$ tel que $f(\alpha)=\alpha$. On considère la suite réelle définie pour $n\in\mathbb N$ par : $$\begin{cases} u_{n+1}=f(u_n)\\ u_0=0 \end{cases}$$

Montrer que $\forall n\in\mathbb N,\ |u_n-\alpha|\leq\frac{1}{2^n}|u_0-\alpha|$ et en déduire la limite de $u_n$.

Afficher le corrigé

On pose la propriété $P_n:"|u_n-\alpha|\leq\frac{1}{2^n}|u_0-\alpha|"$ pour $n\in\mathbb N$.

Initialisation (n=0) : On a que $\frac{1}{2^0}|u_0-\alpha|=|u_0-\alpha|$ donc forcément $|u_0-\alpha|\leq\frac{1}{2^0}|u_0-\alpha|$, donc $P_0$ est vraie. D'où l'initialisation.

Hérédité : Supposons $P_n$ vraie, c'est à dire $|u_n-\alpha|\leq\frac{1}{2^n}|u_0-\alpha|$ et montrons $P_{n+1}$. Comme $u_{n+1}=f(u_n)$ et $f(\alpha)=\alpha$ on a que : $$|u_{n+1}-\alpha|=|f(u_n)-f(\alpha)|.$$ D'autre part, comme $\forall (x,y)\in\mathbb R,\ |f(x)-f(y)|\leq\frac{1}{2}|x-y|$, en posant $x=u_n$ et $y=\alpha$, on a aussi que : $$|u_{n+1}-\alpha|=|f(u_n)-f(\alpha)|\leq \frac{1}{2}|u_n-\alpha|.$$ Mais par hypothèse de récurrence $|u_n-\alpha|\leq\frac{1}{2^n}|u_0-\alpha|$ donc $\frac{1}{2}|u_n-\alpha|\leq\frac{1}{2^{n+1}}|u_0-\alpha|$ et il suit que : $$|u_{n+1}-\alpha|\leq \frac{1}{2}|u_n-\alpha|\leq\frac{1}{2^{n+1}}|u_0-\alpha|,$$ c'est à dire $|u_{n+1}-\alpha|\leq\frac{1}{2^{n+1}}|u_0-\alpha|$ et $P_{n+1}$ est démontrée. D'où l'hérédité.

Par récurrence pour tout $n\in\mathbb N$, $|u_n-\alpha|\leq\frac{1}{2^n}|u_0-\alpha|$.

Limite : On observe que $\lim_{n\to+\infty}\frac{1}{2^n}=0$, donc comme $|u_n-\alpha|\leq\frac{1}{2^n}|u_0-\alpha|$, alors nécessairement $\lim_{n\to+\infty}u_n=\alpha$.


Exercice (EDHEC 2009) : On considère une suite réelle $(u_n)_{n\in\mathbb N^*}$ et un réel $\alpha>1$ tel que : $$\forall n\in\mathbb N^*,\ u_n=n \alpha(u_n-u_{n+1}).$$

Montrer que pour $n\geq 2$, on a : $u_n=u_1\Pi_{k=1}^{n-1}\left(1-\frac{1}{k\alpha}\right)$.

Afficher le corrigé

On pose $P_n:"u_n=u_1\Pi_{k=1}^{n-1}\left(1-\frac{1}{k\alpha}\right)"$.

Initialisation (n=2) : On a que $u_1=\alpha(u_1-u_2)$ donc en réorganisant $u_2=\frac{1}{\alpha}u_1(\alpha-1)$ (ce qui a du sens car $\alpha\neq 0$) soit encore $u_2=u_1\left(1-\frac{1}{\alpha}\right)$ qui est exactement $P_2$. D'où l'initialisation.

Hérédité : Si $P_n$ est vraie, on a $u_n=u_1\Pi_{k=1}^{n-1}\left(1-\frac{1}{k\alpha}\right)$. Or $u_n=n \alpha(u_n-u_{n+1})$ donc $u_{n+1}=u_n\left(1-\frac{1}{n\alpha}\right)$. Il suit que si $P_n$ est vraie $$u_{n+1}=u_n\left(1-\frac{1}{n\alpha}\right)=u_1\Pi_{k=1}^{n-1}\left(1-\frac{1}{k\alpha}\right)\left(1-\frac{1}{n\alpha}\right)=u_1\Pi_{k=1}^{n}\left(1-\frac{1}{k\alpha}\right)$$ et donc $P_{n+1}$ est vraie. D'où l'hérédité.

Par récurrence, le résultat est démontré pour tout $n\in\mathbb N\backslash\{0,1\}$.


Exercice (probabilité; ECRICOME 2010, Problème partie III, 2.a) : Montrer que pour toute famille $(D_1,\dots,D_m)$ d'évènements, on a $P(D_1\cup D_2\cup \dots\cup D_m)\leq P(D_1)+P(D_2)+\dots+P(D_m).$

Afficher le corrigé

On pose la propriété $D_m:"\text{Pour toute famille d'évènements }(D_1,\dots,D_m),\ P(D_1\cup D_2\cup \dots\cup D_m)\leq P(D_1)+P(D_2)+\dots+P(D_m)"$.

Initialisation (m=1) : On a $P(D_1)=P(D_1)$ donc $P(D_1)\leq P(D_1)$, par conséquent $P_1$ est vraie. D'où l'initialisation.

Hérédité : Supposons $P_m$ vraie et montrons $P_{m+1}$. Soit $(D_1,\dots,D_{m+1})$ une famille de $m+1$ évènements. Par propriété de la probabilité, on a : $$\begin{align} P(D_1\cup D_2\cup \dots\cup D_m\cup D_{m+1})&=P\left((D_1\cup D_2\cup \dots\cup D_m)\cup D_{m+1}\right)\\ &\leq P(D_1\cup D_2\cup \dots\cup D_m)+P(D_{m+1}). \end{align}$$ Mais comme $P_m$ est supposée vraie, on a $P(D_1\cup D_2\cup \dots\cup D_m)\leq P(D_1)+P(D_2)+\dots+P(D_m)$, par conséquent : $$\begin{align} P(D_1\cup D_2\cup \dots\cup D_m\cup D_{m+1})&\leq P(D_1\cup D_2\cup \dots\cup D_m)+P(D_{m+1})\\ &\leq P(D_1)+P(D_2)+\dots+P(D_m)+P(D_{m+1}), \end{align}$$ et donc $P_{m+1}$ est vraie. D'où l'hérédite.

Par récurrence $P_m$ est vraie pour tout $m\in\mathbb N^*$.


Exercice (binôme de Newton) : Montrer par récurrence que $\forall (a,b)\in\mathbb R^2,\ \forall n\in\mathbb N^*,\ (a+b)^n=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^kb^{n-k}$.

Afficher le corrigé

Rappel : Pour cet exercice il est fondamental de se souvenir de la relation du triangle de Pascal : $$\forall n\in\mathbb N^*,\forall k\in\{0,\dots,n-1\},\begin{pmatrix}n\\ k\end{pmatrix}+\begin{pmatrix}n\\ k+1\end{pmatrix}=\begin{pmatrix}n+1\\ k+1\end{pmatrix}$$

On pose la proriété $P_n: "(a+b)^n=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^kb^{n-k}"$ avec $n\in\mathbb N^*$.

Initialisation (n=1) : On observe que $$\sum_{k=0}^1\begin{pmatrix}1\\ k\end{pmatrix}a^kb^{1-k}=\begin{pmatrix}1\\ 0\end{pmatrix}a^0b^{1-0}+\begin{pmatrix}1\\ 1\end{pmatrix}a^1b^{1-1}=a+b,$$ par conséquent $P_1$ est vraie. D'où l'initialisation.

Hérédité : Supposons $P_n$ vraie et montrons $P_{n+1}$. En utilisant $P_n$, on a déjà que : $$\begin{align} (a+b)^{n+1}&=(a+b)(a+n)^n\\ &=(a+b)\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^kb^{n-k}\\ &=a\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^kb^{n-k}+b\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^kb^{n-k}\\ &=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^{k+1}b^{n-k}+\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^kb^{n+1-k}. \end{align}$$ Dans la seconde somme on effectue un décalage d'indide qui donne : $$(a+b)^{n+1}=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^{k+1}b^{n-k}+\sum_{k=-1}^{n-1}\begin{pmatrix}n\\ k+1\end{pmatrix}a^{k+1}b^{n+1-(k+1)},$$ et dans la première somme, on observe que $n-k=n+1-(k+1)$ de sorte que : $$(a+b)^{n+1}=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}a^{k+1}b^{n+1-(k+1)}+\sum_{k=-1}^{n-1}\begin{pmatrix}n\\ k+1\end{pmatrix}a^{k+1}b^{n+1-(k+1)}.$$ On va maintenant rassembler ces deux sommes. Pour se faire, on va enlever le n-ième terme de la première somme et enlever le (-1)-ième terme de la seconde. $$\begin{align} (a+b)^{n+1}&=\sum_{k=0}^{n-1}\begin{pmatrix}n\\ k\end{pmatrix}a^{k+1}b^{n+1-(k+1)}+\begin{pmatrix}n\\ n\end{pmatrix}a^{n+1}b^{0} +\sum_{k=0}^{n-1}\begin{pmatrix}n\\ k+1\end{pmatrix}a^{k+1}b^{n+1-(k+1)} +\begin{pmatrix}n\\ 0\end{pmatrix}a^{0}b^{n+1}\\ &=\begin{pmatrix}n\\ n\end{pmatrix}a^{n+1}b^{0} +\sum_{k=0}^{n-1}\left(\begin{pmatrix}n\\ k\end{pmatrix}+\begin{pmatrix}n\\ k+1\end{pmatrix}\right)a^{k+1}b^{n+1-(k+1)} +\begin{pmatrix}n\\ 0\end{pmatrix}a^{0}b^{n+1}. \end{align}$$ Ensuite grâce à la relation de Pascal (rappelé en début de corrigé) et le fait que $\begin{pmatrix}n\\ n\end{pmatrix}=1=\begin{pmatrix}n+1\\ n+1\end{pmatrix}$ et que $\begin{pmatrix}n\\ 0\end{pmatrix}=1=\begin{pmatrix}n+1\\ 0\end{pmatrix}$, on a : $$(a+b)^{n+1}=\begin{pmatrix}n+1\\ n+1\end{pmatrix}a^{n+1}b^{0} +\sum_{k=0}^{n-1}\begin{pmatrix}n+1\\ k+1\end{pmatrix}a^{k+1}b^{n+1-(k+1)} +\begin{pmatrix}n+1\\ 0\end{pmatrix}a^{0}b^{n+1}.$$ Finalement en décalant l'indice de la somme de 1 et en réassemblant les termes, on a que : $$(a+b)^{n+1}=\begin{pmatrix}n+1\\ n+1\end{pmatrix}a^{n+1}b^{0} +\sum_{k=1}^{n}\begin{pmatrix}n+1\\ k\end{pmatrix}a^{k}b^{n+1-k} +\begin{pmatrix}n+1\\ 0\end{pmatrix}a^{0}b^{n+1}=\sum_{k=0}^{n+1}\begin{pmatrix}n+1\\ k\end{pmatrix}a^{k}b^{n+1-k}.$$ On a donc montré $P_{n+1}$ en partant de $P_n$. D'où l'hérédité.

Conclusion : Par récurrence $P_n$ est vraie pour tout $n\in\mathbb N^*$.

On pourra aussi voir la démonstration en vidéo.


Exercice (variante du binôme de Newton adaptée de HEC mathII 2013, 2.a)b)c)) : Pour $x\in\mathbb R$, on pose : $$x^{<\!n>}=\begin{cases}\Pi_{k=1}^n(x+k-1) & \text{ si } & n\geq 1\\ 1 & \text{ si } & n=0\end{cases}.$$

1) Soit $r\in\mathbb R$, exprimer $r^{<\!n+1>}$ en fonction de $r^{<\!n>}$.

2) En déduire pour $k\in[\![0,n]\!],\ r\in\mathbb R,\ s\in\mathbb R$ la relation $(r+s+n)r^{<\!k>}s^{<\!n-k>}=r^{<\!k+1>}s^{<\!n-k>}+r^{<\!k>}s^{<\!n-k+1>}$.

3) Montrer par récurrence que pour tout $n\in\mathbb N$, on a : $(r+s)^{<\!n>}=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}r^{<\!k>}s^{<\!n-k>}$.

Afficher le corrigé

1) On a $r^{<\!n+1>}=r(r+1)\dots (r+n-1)(r+n)=r^{<\!n>}(r+n)$.

2) On a : $$\begin{align} (r+s+n)r^{<\!k>}s^{<\!n-k>}&=((r+k)+(s+n-k))r^{<\!k>}s^{<\!n-k>}\\ &=(r+k)r^{<\!k>}s^{<\!n-k>}+r^{<\!k>}(s+n-k)s^{<\!n-k>}\\ &=r^{<\!k+1>}s^{<\!n-k>}+r^{<\!k>}s^{<\!n-k+1>} \end{align}$$

3) On fait une récurrence sur $P_n: "(r+s)^{<\!n>}=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}r^{<\!k>}s^{<\!n-k>}"$. L'initialisation est immédiate et l'hérédité suit les mêmes idées que la résolution de l'exercice précédent, à l'exception du fait que certaines lignes devront être justifiées à l'aide de 1) et 2). Si vous avez du mal, des détails supplémentaires sont disponibles dans le corrigé du sujet en ligne.


Exercice (nombres complexes; HEC 2011, 12.) :

1) Soit $z_1$ et $z_2$ deux nombres complexes tels que $|z_1+z_2|=|z_1|+|z_2|$. Montrer qu'il existe $\theta\in [0,2\pi[$ tel que $z_1=|z_1|e^{i\theta}$ et $z_2=|z_2|e^{i\theta}$.

2) Soit $z_1,z_2,\dots,z_p$, $p$ nombre complexes avec $p\geq 2$ vérifiant $\left|\sum_{k=1}^p z_k\right|=\sum_{k=1}^p|z_k|$. Montrer qu'il existe $\theta\in[0,2\pi[$ tel que $\forall k\in[\![1,p]\!],z_k=|z_k|e^{i\theta}$.

Afficher le corrigé

Remarque : Pour la question 2) de cet exercice, il sera important de se souvenir de l'inégalité triangulaire inverse (valable pour les réels ou les complexes) : $|a-b|\geq |a|-|b|$.

1) On peut déjà réécrire $z_1$ et $z_2$ sous forme polaire $z_1=|z_1|e^{i\theta_1}$ et $z_2=|z_2|e^{i\theta_2}$ avec $\theta_1,\theta_2\in[0,2\pi[$. On a alors : $$\begin{align} |z_1+z_2|=|z_1|+|z_2|&\Longleftrightarrow |z_1+z_2|^2=(|z_1|+|z_2|)^2\\ &\Longleftrightarrow ||z_1|e^{i\theta_1}+|z_2|e^{i\theta_2}|^2=|z_1|^2+2|z_1||z_2|+|z_2|^2\\ &\Longleftrightarrow ||z_1|(\cos\theta_1+i\sin\theta_1)+|z_2|(\cos\theta_2+i\sin\theta_2)|^2=|z_1|^2+2|z_1||z_2|+|z_2|^2\\ &\text{ après quelques calculs de module...}\\ &\Longleftrightarrow |z_1|^2+|z_2|^2+2|z_1||z_2|(\cos\theta_1\cos\theta_2+\sin\theta_1\sin\theta_2)=|z_1|^2+2|z_1||z_2|+|z_2|^2\\ &\Longleftrightarrow 2|z_1||z_2|\cos(\theta_2-\theta_1)=2|z_1||z_2|\text{ (grâce à une formule trigo)}\\ &\Longleftrightarrow \cos(\theta_2-\theta_1)=1\text{ (car les nombres complexes sont non nuls.)} \end{align}$$ Or comme $\theta_1,\theta_2\in[0,2\pi[$, la condition $\cos(\theta_2-\theta_1)=1$ est équivalente à $\theta_1=\theta_2$. Il suit alors que $z_1=|z_1|e^{i\theta_1}$ et $z_2=|z_2|e^{i\theta_1}$ d'où l'existence du $\theta$ ($=\theta_1$) recherché.

2) On fait une récurrence sur $$P_p:"\forall(z_1,\dots,z_p)\in\mathbb C^p,\ \left|\sum_{k=1}^p z_k\right|=\sum_{k=1}^p|z_k|\Longrightarrow \exists\theta\in[0,2\pi[,\forall k\in[\![1,p]\!],z_k=|z_k|e^{i\theta}"$$ avec $p\geq 2$

Initialisation (n=2) : $P_2$ est vraie d'après 1).

Hérédité : Supposons la propriété vraie au rang $p$. Soient $z_1,z_2,\dots,z_p,z_{p+1}$, $p+1$ nombres complexes vérifiant $\left|\sum_{j=1}^{p+1}z_j\right|=\sum_{j=1}^{p+1}|z_j|$. Pour appliquer $P_p$, nous allons essayer de montre que $\left|\sum_{j=1}^{p}z_j\right|=\sum_{j=1}^{p}|z_j|$. Par l'inégalité triangulaire, nous avons déjà que : $$\left|\sum_{j=1}^{p}z_j\right|\leq\sum_{j=1}^{p}|z_j|.$$

D'autre part grâce à l'inégalité triangulaire inverse, on a aussi : $$\begin{align} \left|\sum_{j=1}^{p}z_j\right|&=\left|\sum_{j=1}^{p+1}z_j-z_p\right|\\ &\geq\left|\sum_{j=1}^{p+1}z_j\right|-|z_p|\text{(inégalité triangulaire inverse)}\\ &=\sum_{j=1}^{p+1}|z_j|-|z_p|\text{ (par hypothèse sur les }z_i)\\ &=\sum_{j=1}^{p}|z_j|. \end{align}$$ Nous avons donc montré l'inégalité dans les deux sens donc $\left|\sum_{j=1}^{p}z_j\right|=\sum_{j=1}^{p}|z_j|$. En appliquant l'hypothèse de récurrence $P_p$, on en déduit que $\exists\theta\in[0,2\pi[,\forall k\in[\![1,p]\!],z_k=|z_k|e^{i\theta}$. De la même manière, on peut montrer également que $\left|\sum_{j=2}^{p+1}z_j\right|=\sum_{j=2}^{p+1}|z_j|$ et donc aussi que $\exists\theta'\in[0,2\pi[,\forall k\in[\![2,p+1]\!],z_k=|z_k|e^{i\theta'}$. Pour terminer on observe que les deux familles de nombres complexes $(z_1,\dots,z_p)$ et $(z_2,\dots,z_{p+1})$ ont des termes en communs, donc nécessairement $\theta=\theta'$ et donc $\exists\theta\in[0,2\pi[,\forall k\in[\![1,p+1]\!],z_k=|z_k|e^{i\theta}$, ce qui prouve $P_{p+1}$. D'où l'hérédité

Par récurrence $P_p$ est vraie pour tout $p\geq 2$, ce qu'il fallait démontrer.


La liste d'exercice qui suit fait appel à d'autres chapitres. Pour vous y essayer, assurez vous d'être au point sur le chapitre considéré. Attention, certaines questions demanderont d'avoir fait une partie du sujet.

Contacter l'auteur du site : frederic.millet @ math-sup.fr