%----------------------------------------------------------------------------------------
%	CHAPITRE 02 : RAISONNEMENT PAR RECURRENCE
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_3.pdf} 

\chapter{Raisonnement par r�currence}

\begin{remarque}
Ce chapitre ne concerne que les �l�ves de la fili�re S.
\end{remarque}

\section{Le principe de r�currence}

\begin{theoreme}
Soit $\mathcal{P}_n$ une propri�t� d�pendant d'un nombre entier $n$. Si :
\begin{itemize}
\item $\mathcal{P}_{0}$ est vraie [initialisation]
\item pour un entier $k$ fix�, $\mathcal{P}_k \Longrightarrow \mathcal{P}_{k+1}$ [h�r�dit�]
\end{itemize}
alors $\mathcal{P}_n$ est vraie pour tout entier $n\geqslant0$.
\end{theoreme}

Ce th�or�me est tr�s important car il permet de d�montrer des �galit�s conjectur�es (suppos�es vraies � l'aide d'observations).

\begin{exemple}\label{ch2somme}
Posons : $$\mathcal{P}_n\qquad : \qquad\forall n\in\N*,\  1+2+3+\cdots + n=\dfrac{n(n+1)}{2}.$$
D�montrons que $\mathcal{P}_n$ est vraie pour tout entier naturel $n$ non nul.
\begin{itemize}
\item \textbf{Initialisation.}

Cette �tape consiste � v�rifier que la propri�t� est vraie pour le plus petit entier $n$ possible ; ici, il faut donc montrer que $\mathcal{P}_1$ est vraie.

D'une part, le membre gauche de l'�galit� est �gal � 1.

D'autre part, le membre droit de l'�galit� est �gal � : $\dfrac{1\times(1+1)}{2}=1$.

\medskip

Ainsi, $\mathcal{P}_1$ est vraie. L'initialisation est alors faite.

\item \textbf{H�r�dit�.}

Cette �tape consiste � supposer que la propri�t� est vraie pour un entier $k$ fix� et qu'en cons�quence, elle l'est aussi au rang suivant, c'est-�-dire que $\mathcal{P}_{k+1}$ est vraie.

\medskip

Supposons donc que $\mathcal{P}_k$ soit vraie. Alors :
$$ 1+2+3+\cdots+k=\dfrac{k(k+1)}{2}\qquad\text{(on appelle cela l'hypoth�se de r�currence)}$$
et montrons, gr�ce � cela, que :
$$ 1+2+3+\cdots+k+(k+1)=\dfrac{(k+1)(k+2)}{2}.$$
On a :
$$
\begin{aligned}
1+2+3+\cdots+k+(k+1) & = \dfrac{k(k+1)}{2}+k+1\\
& = \dfrac{k(k+1)}{2}+\dfrac{2(k+1)}{2}\\
& = \dfrac{k(k+1)+2(k+1)}{2}\\
& = \dfrac{(k+1)(k+2)}{2}\quad\text{(en mettant en facteur }k+1)
\end{aligned}
$$

Ainsi, $\mathcal{P}_{k+1}$ est vraie.

Nous avons ici d�montr� que si $\mathcal{P}_k$ �tait vraie, alors $\mathcal{P}_{k+1}$ l'�tait aussi, ce qui se note math�matiquement : $\mathcal{P}_k\Longrightarrow\mathcal{P}_{k+1}$ (si $\mathcal{P}_k$ est vraie, alors $\mathcal{P}_{k+1}$ aussi).
\end{itemize}

L'h�r�dit� est alors d�montr�e. Ainsi, $\mathcal{P}_n$ est vraie pour tout entier $n\geqslant1$.
\end{exemple}

\begin{exercice}
D�montrer par r�currence la propri�t� suivante :
$$
\mathcal{P}_n\qquad : \qquad \forall n\in\N*,\ 1^2+2^2+3^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}.
$$
\end{exercice}

\begin{exercice}
D�montrer par r�currence la propri�t� suivante :
$$
\mathcal{P}_n\qquad : \qquad \forall n\in\N*,\ 1^3+2^3+3^3+\cdots+n^3=\dfrac{n^2(n+1)^2}{4}.
$$
\end{exercice}

\section{D�montrer une minoration ou une majoration}

\begin{exemple}
Reprenons la suite \suite{u}{n}{} d�finie dans l'exercice \ref{ch1ex3} :
$$
\begin{cases}
u_0=2\\
u_{n+1}=\sqrt{2u_n-1}\qquad\forall n\in\N
\end{cases}
$$
D�montrons par r�currence la propri�t� suivante :
$$
\mathcal{P}_n\qquad : \qquad\forall n\in\N,\ u_n\geqslant1.
$$
\begin{itemize}
\item \textbf{Initialisation.}

$u_0=2\geqslant1$ donc $\mathcal{P}_0$ est vraie. L'initialisation est alors v�rifi�e.

\item \textbf{H�r�dit�.}

Supposons que pour un entier $k$ fix�, $u_k\geqslant1$.

Montrons alors que $u_{k+1}\geqslant1$, c'est-�-dire : $\sqrt{2u_k-1}\geqslant1$.

\medskip

Nous avons :
$$
\begin{aligned}
u_k\geqslant1 & \Longrightarrow 2u_k\geqslant2\\
& \Longrightarrow 2u_k-1\geqslant1\\
& \Longrightarrow \sqrt{2u_k-1}\geqslant\sqrt{1}\quad\text{(car la fonction $x\mapsto\sqrt{x}$ est croissante)}\\
& \Longrightarrow u_{k+1}\geqslant1.
\end{aligned}
$$

L'h�r�dit� est alors d�montr�e.
\end{itemize}

Ainsi, pour tout entier naturel $n$, $u_n\geqslant1$, ce qui signifie que \suite{u}{n}{} est minor�e.

\begin{remarque}
Ceci coupl� au fait que la suite est d�croissante (voir exercice \ref{ch1ex3}) montre que \suite{u}{n}{} converge.
\end{remarque}
\end{exemple}

\begin{exercice}
Montrer que la suite \suite{u}{n}{} d�finie par :
$$
\begin{cases}
u_0=-1\\
u_{n+1}=\sqrt{3u_n+4}\qquad\forall n\in\N
\end{cases}
$$
est major�e par 4.
\end{exercice}

\begin{exemple}
Reprenons ici la suite \suite{u}{n}{} d�finie dans l'exemple \ref{ch1ex4} :
$$
\begin{cases}
u_0=2\\
u_{n+1}=\dfrac{1}{2}\left(u_n+\dfrac{2}{u_n}\right)\qquad\forall n\in\N
\end{cases}
$$
et montrons qu'elle est minor�e par $\sqrt{2}$.

\medskip

Nous allons nous aider des variations de la fonction $f$ d�finie par :
$$f(x)=\dfrac{1}{2}\left(x+\dfrac{2}{x}\right)$$
puisque $u_{n+1}=f\left(u_n\right)$.

La d�riv�e de $f$ est :
$$ f'(x)=\dfrac{x^2-2}{2x^2}$$
d'o� le tableau de variation suivant :
\begin{center}
\begin{tikzpicture}[draw=ocre]
\tkzTabInit[color,%
						colorC=ocre!20,%
						colorL=ocre!20,%
						colorV=ocre!20]{$x$/0.7,$f'(x)$/0.5,$f$/1.5}{$-\infty$,$-\sqrt{2}$,$\sqrt{2}$,$+\infty$}
\tkzTabLine{,+,z,-,z,+}
\tkzTabVar{-/,+/,-/,+/}
\end{tikzpicture}
\end{center}

Montrons maintenant par r�currence que $u_n\geqslant\sqrt{2}$ pour tout entier naturel $n$.

\begin{itemize}
\item \textbf{Initialisation.}

$u_0=2\geqslant\sqrt{2}$ donc l'initialisation est v�rifi�e.

\item \textbf{H�r�dit�.}

Supposons que pour un entier naturel $k$ fix�, $u_k\geqslant\sqrt{2}$.

Alors,
$$
f\left(u_k\right)\geqslant f\left(\sqrt{2}\right)
$$
car sur \intervFO{\sqrt2}{+\infty}, $f$ est strictement croissante donc en prenant l'image des termes $u_k$ et $\sqrt2$, on ne change pas leur ordre relatif (on ne change donc pas le sens de l'in�galit�).

Or, $f\left(u_k\right)=u_{k+1}$ et $f\left(\sqrt2\right)=\sqrt2$. D'o� :
$$ u_{k+1}\geqslant\sqrt2.$$
L'h�r�dit� est alors d�montr�e.
\end{itemize}
Ainsi, la suite est minor�e par $\sqrt{2}$.

\begin{remarque}
Il �tait ici n�cessaire d'utiliser les variations de la fonction $f$. Essayez de d�montrer la minoration sans ces variations et vous vous rendrez vite compte des difficult�s.
\end{remarque}
\end{exemple}

\begin{exercice}
Montrer que la suite \suite{u}{n}{} d�finie par :
$$
\begin{cases}
u_0=5\\
u_{n+1}=\sqrt{\dfrac{2u_n+1}{u_n+1}}\qquad\forall n\in\N
\end{cases}
$$
est minor�e par $\lambda$, o� $\lambda$ est une solution de l'�quation $\lambda^3+\lambda^2-2\lambda-1=0$ (on admettra que $0<\lambda<5$).
\end{exercice}

\section{Corrig�s des exercices}

\begin{correction}
$$
\mathcal{P}_n\qquad : \qquad \forall n\in\N*,\ 1^2+2^2+3^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}.
$$
\begin{itemize}
\item \textbf{Initialisation.}

D'une part, $1^2=1$ ;

D'autre part, $\dfrac{1(1+1)(2\times1+1)}{6}=\dfrac{1\times2\times3}{6}=1$.

\medskip

Ainsi, $\mathcal{P}_1$ est vraie. L'initialisation est alors faite.

\item \textbf{H�r�dit�.}

Supposons que pour un entier $k$ fix�, $\mathcal{P}_k$ soit vraie. Alors :
$$
1^2+2^2+3^2+\cdots+k^2=\dfrac{k(k+1)(2k+1)}{6}.
$$
Montrons qu'en cons�quence :
$$
\begin{aligned}
1^2+2^2+3^2+\cdots+k^2+(k+1)^2 & =\dfrac{(k+1)(k+1+1)(2(k+1)+1)}{6}\\
& =\dfrac{(k+1)(k+2)(2k+3)}{6}.
\end{aligned}
$$

On a :
$$
\begin{aligned}
1^2+2^2+3^2+\cdots+k^2+(k+1)^2 & = \dfrac{k(k+1)(2k+1)}{6}+(k+1)^2\\
& = \dfrac{k(k+1)(2k+1)}{6}+\dfrac{6(k+1)(k+1)}{6}\\
& = \dfrac{(k+1)[k(2k+1)+6(k+1)]}{6}\\
& = \dfrac{(k+1)(2k^2+7k+6)}{6}.
\end{aligned}
$$
Le discriminant de $2k^2+7k+6$ est :
$$\Delta=7^2-4\times2\times6=49-48=1.$$
Ainsi, il admet deux racines :
$$
k_1=\dfrac{-7-\sqrt{1}}{2\times2}=-2\qquad\text{et} k_2=\dfrac{-7+\sqrt{1}}{2\times2}=-\dfrac{3}{2}.
$$
Le polyn�me $2k^2+7k+6$ se factorise donc sous la forme :
$$
\begin{aligned}
2k^2+7k+6 & = 2(k-k_1)(k-k_2)\\
& = 2(k+2)\left(k+\dfrac{3}{2}\right)\\
& = (k+2)(2k+3).
\end{aligned}
$$
Par cons�quent, 
$$
1^2+2^2+3^2+\cdots+k^2+(k+1)^2 = \dfrac{(k+1)(k+2)(2k+3)}{6}\;,
$$
et donc, $\mathcal{P}_{k+1}$ est vraie.

\medskip

L'h�r�dit� est alors d�montr�e.
\end{itemize}

Ainsi, $\mathcal{P}_n$ est vraie pour tout $n\geqslant1$.
\end{correction}

\newpage

\begin{correction}
$$
\mathcal{P}_n\qquad : \qquad \forall n\in\N*,\ 1^3+2^3+3^3+\cdots+n^3=\dfrac{n^2(n+1)^2}{4}.
$$
\begin{itemize}
\item \textbf{Initialisation.}

D'une part, nous avons : $1^3=1$ ;

D'autre part, $\dfrac{1^2\times(1+1)^2}{4}=\dfrac{1\times2^2}{4}=\dfrac{4}{4}=1$.

\medskip

Ainsi, $\mathcal{P}_1$ est vraie. L'h�r�dit� est alors v�rifi�e.

\item \textbf{H�r�dit�.}

Supposons que pour un entier $k$ fix�, $\mathcal{P}_k$ soit vraie :
$$
1^3+2^3+3^3+\cdots+k^3=\dfrac{k^2(k+1)^2}{4}.
$$
Montrons qu'en cons�quence, $\mathcal{P}_{k+1}$ l'est aussi, c'est-�-dire :
$$
1^3+2^3+3^3+\cdots+k^3+(k+1)^3=\dfrac{(k+1)^2(k+2)^2}{4}.
$$

On a :

$$
\begin{aligned}
1^3+2^3+3^3+\cdots+k^3+(k+1)^3 & =\dfrac{k^2(k+1)^2}{4}+(k+1)^3\\
& = \dfrac{k^2(k+1)^2}{4}+\dfrac{4(k+1)(k+1)^2}{4}\\
& = \dfrac{(k+1)^2[k^2+4(k+1)]}{4}\\
& = \dfrac{(k+1)^2(k^2+4k+4)}{4}\\
& = \dfrac{(k+1)^2(k+2)^2}{4}\quad\text{(identit� remarquable).}
\end{aligned}
$$
Ainsi, $\mathcal{P}_{k+1}$ est vraie. L'h�r�dit� est donc d�montr�e.
\end{itemize}
\end{correction}

\begin{correction}
La suite \suite{u}{n}{} est d�finie par :
$$
\begin{cases}
u_0=-1\\
u_{n+1}=\sqrt{3u_n+4}\qquad\forall n\in\N
\end{cases}
$$
Montrons par r�currence que pour tout entier naturel $n$, $u_n\leqslant4$.
\begin{itemize}
\item \textbf{Initialisation.}

$u_0=-1\leqslant4$ donc l'initialisation est v�rifi�e.

\item \textbf{H�r�dit�.}

Supposons que pour un entier naturel $k$ fix�, $u_k\leqslant4$. Alors :
$$
\begin{aligned}
u_k\leqslant4 & \Longrightarrow 3u_k\leqslant12\\
& \Longrightarrow 3u_k+4\leqslant16\\
& \Longrightarrow \sqrt{3u_k+4}\leqslant\sqrt{16}\\
& \Longrightarrow u_{k+1}\leqslant4.
\end{aligned}
$$
L'h�r�dit� est alors d�montr�e.
\end{itemize}
Ainsi, pour tout entier naturel $n$, $u_n\leqslant4$. La suite \suite{u}{n}{} est donc major�e par 4.

\begin{remarque}
On pourrait aussi continuer et d�montrer que la suite est croissante, donc convergente.
\end{remarque}
\end{correction}

\begin{correction}\label{ch2ex4}
$$
\begin{cases}
u_0=5\\
u_{n+1}=\sqrt{\dfrac{2u_n+1}{u_n+1}}\qquad\forall n\in\N
\end{cases}
$$
Posons :
$$
f(x)=\sqrt{\dfrac{2x+1}{x+1}}
$$
d�finie sur $\intervOO{-\infty}{-1}\cup\intervFO{\dfrac{1}{2}}{+\infty}$.

Avec la formule :
$$
\left(\sqrt{u}\right)^\prime=\dfrac{u^\prime}{2\sqrt{u}}\;,
$$
on trouve que la d�riv�e de $f$ est :
$$
f^\prime(x)=\dfrac{\frac{1}{(x+1)^2}}{2\sqrt{\frac{2x+1}{x+1}}}.
$$
Ainsi, $f^\prime(x)>0$ sur \intervOO{-\infty}{-1} et sur \intervFO{\dfrac{1}{2}}{+\infty}, ce qui donne :
\begin{center}
\begin{tikzpicture}
\tikzset{node style/.append style = {fill=gray!10}}
\tkzTabInit{$x$/0.7,$f'(x)$/0.5,$f$/1}{$-\infty$,$-1$,$-\frac{1}{2}$,$+\infty$}
\tkzTabLine{,+,d,h,z,+}
\tkzTabVar{-/,+DH/,-/,+/}
\end{tikzpicture}
\end{center}
Montrons maintenant par r�currence que $u_n\geqslant\lambda$.
\begin{itemize}
\item \textbf{Initialisation.}

$u_0=5>\lambda$ donc l'initialisation est v�rifi�e.

\item \textbf{H�r�dit�.}

Supposons que pour un entier naturel $k$ fix�, $u_k\geqslant\lambda$.

Sur \intervFO{-\dfrac{1}{2}}{+\infty}, $f$ est strictement croissante donc :
$$
u_k\geqslant\lambda \Longrightarrow f\left(u_k\right)\geqslant f(\lambda).$$
Or, $u_{k+1}=f\left(u_k\right)$ et $f(\lambda) = \sqrt{\dfrac{2\lambda+1}{\lambda+1}}$.

D'apr�s l'�nonc�, 
$$
\begin{aligned}
\lambda^3+\lambda^2-2\lambda-1=0 & \Longrightarrow \lambda^3+\lambda^2=2\lambda+1\\
& \Longrightarrow \lambda^2(\lambda+1)=2\lambda+1\\
& \Longrightarrow\lambda^2=\dfrac{2\lambda+1}{\lambda+1}\text{ (car $\lambda\neq-1$)}\\
& \Longrightarrow\lambda=\sqrt{\dfrac{2\lambda+1}{\lambda+1}}\text{ (car $\lambda>0$)}
\end{aligned}
$$
Ainsi,
$$ u_k\geqslant\lambda\Longrightarrow u_{k+1}\geqslant\lambda.$$

L'h�r�dit� est alors d�montr�e.
\end{itemize}
Ainsi, la suite \suite{u}{n}{} est minor�e par $\lambda$.

\begin{remarque}
On pourrait d�montrer que la suite est d�croissante, donc convergente et en calculant les premiers termes de \suite{u}{n}{}, on arrive � voir que $u_n$ se rapproche de 1,246979604. Il se trouve que cette valeur est une valeur approch�e de l'une des solutions de l'�quation $x^3+x^2-2x-1=0$, que l'on ne peut pas r�soudre facilement. 

En effet, si on note $\ell$ la limite de \suite{u}{n}{} (puisqu'elle existe), alors $u_{n+1}$ et $u_n$ se  rapprochent de plus en plus de $\ell$ si bien qu'� partir d'un certain rang, on peut �crire :
$$\begin{aligned}
u_{n+1}=\sqrt{\dfrac{2u_n+1}{u_n+1}} & \Longrightarrow\ell\approx\sqrt{\dfrac{2\ell+1}{\ell+1}}\\
& \Longrightarrow \ell^2\approx\dfrac{2\ell+1}{\ell+1}\\
& \Longrightarrow \ell^2(\ell+1)\approx2\ell+1\\
& \Longrightarrow \ell^3+\ell^2-2\ell-1=0.
\end{aligned}$$
On voit alors que les suites peuvent servir � trouver des solutions � certaines �quations. Mais nous y reviendrons dans le chapitre suivant.
\end{remarque}
\end{correction}

\endinput
