\chapter{Suites et récurrence}

\section{Raisonnement par récurrence}

\begin{exointro}{Lycée Carnot, Paris}
Montrer que pour tout entier $n\geq 1$ :
\[
1^2+2^2+3^2+\cdots+(n-1)^2+n^2=\dfrac{n(n+1)(2n+1)}{6}.
\]
\end{exointro}

\begin{prop}
Soit $\mathcal {P}_n$ une propriété dépendant de l'entier naturel $n$.\\
Si 
\begin{itemize}
\item pour un entier $n_0$, $\mathcal {P}_{n_0}$ est vraie (initialisation),
\item pour tout naturel $k \ge n_0$, le fait que $\mathcal {P}_k$ soit vraie implique que $\mathcal {P}_{k+1}$ est vraie (hérédité),
\end{itemize}
alors $\mathcal {P}_n$ est vraie pour tout $n$ supérieur à $n_0$.
\end{prop}

\begin{Remarque}
si le fait que $\mathcal {P}_k$ est vraie implique que $\mathcal {P}_{k+1}$ est vraie alors on dira que la propriété est héréditaire.
\end{Remarque}

\begin{aretenir}
Une démonstration par récurrence comporte impérativement deux étapes : initialisation et hérédité.
\end{aretenir}

\begin{solintro}
\begin{itemize}
\item \emph{Initialisation :} Comme :
\[ 1^2=\dfrac{1\times2\times3}{6}\;, \]
la propriété est vraie au rang $1$.\vspace*{-2em}

\Break

\item \emph{Hérédité :} Soit $k$ un entier non nul arbitrairement fixé ; supposons la propriété vraie au rang $k$ : 
\[ 1^2+2^2+3^2+\cdots+(k-1)^2+k^2=\dfrac{k(k+1)(2k+1)}{6}. \]
On veut montrer que la propriété est vraie au rang $k+1$, soit : 
\begin{align*}
1^2+2^2+\cdots+k^2+(k+1)^2 & =\dfrac{(k+1)(k+2)[2(k+1)+1]}{6}\\
& =\dfrac{(k+1)(k+2)(2k+3)}{6}.
\end{align*}

En utilisant l'hypothèse de récurrence, on a :

\begin{align*}
1^2+2^2+3^2+\cdots+k^2+(k+1)^2
&=\dfrac{k(k+1)(2k+1)}{6}+(k+1)^2 \displaybreak[0]\\
&=\dfrac{k+1}{6}\big[k(2k+1)+6(k+1)\big] \\
&=\dfrac{(k+1)(k+2)(2k+3)}{6}.
\end{align*}

La propriété est donc vraie au rang $k+1$. \par
Ainsi, on a montré que si la propriété est vraie au rang $k$, alors elle est vraie au rang $k+1$. \par
La propriété considérée est donc vraie pour tout rang $n\geq1$ en vertu du principe de récurrence.
\end{itemize}
\end{solintro}


\section{Comportement à l'infini de $(q^n)$}

\begin{prop}
Pour tout entier $a$ strictement positif et pour tout entier naturel $n$, on a :
\[ (1+a)^n \ge 1 + na.\]
\end{prop}

\begin{prop}
Soient $q$ un nombre réel et $n$ un entier naturel.
\begin{itemize}
\item Si $q > 1$, alors $\lim\limits_{n \to +\infty} q^n = +\infty$.
\item Si $q = 1$, alors $q^n = 1$.
\item Si $-1 < q < 1$, alors $\lim\limits_{n \to +\infty} q^n = 0$.
\item Si $q < -1$, alors $(q^n)$ n'a pas de limite en $+\infty$.
\end{itemize}
\end{prop}

\begin{prop}
Toute suite géométrique de raison $q$ telle que $\lvert q \rvert < 1$ converge vers 0.
\end{prop}


\section{Suites arithmético-géométriques}

\begin{defin} 
Une suite $(u_n)$ arthimético-géométrique est une suite définie par son premier terme et par la relation de récurrence :
\[ u_{n+1} = au_n+b, \]
$a$ et $b$ étant des réels non nuls, et $a$ étant de plus différent de 1.
\end{defin}

\begin{Remarques}
\begin{itemize}
\item Si $a$ était égal à 0, on aurait une suite constante.
\item Si $b$ était égal à 0, on aurait une suite géométrique.
\item Si $a$ était égal à 1, on aurait une suite arithmétique.
\end{itemize}
\end{Remarques}

Il n'y a pas de résultat de cours à connaître sur ces suites, mais il est utile de savoir les reconnaître pour comprendre la démarche décrite dans un exercice.

\begin{exointro}{Lycée Descartes, Coumon}
On considère la suite $(u_n)$ définie par $u_0 = 1$ et pour tout entier $n$,
\[ u_{n+1} = 0,5 u_n -3.\]
\begin{questions}
\item Démontrer que la suite $(v_n)$ définie par $v_n = u_n +6$ est une suite géométrique dont on déterminera le premier terme et la raison.
\item Pour tout entier $n$, exprimer $v_n$ en fonction de $n$. En déduire l'expression de $u_n$ en fonction de $n$.
\item Étudier la convergence de la suite $(u_n)$ et donner sa limite en $+\infty$ si elle existe.
\end{questions}
\end{exointro}

\newpage
\begin{solintro}
\begin{questions}
\item Pour démontrer qu'une suite est géométrique, on cherche à exprimer $v_{n+1}$ en fonction de $v_n$.\\
Par définition de $v_n$ et de la relation de récurrence qui définit $u_n$, on a :
\[ v_{n+1} = u_{n+1} + 6.\]
Or,
\[ u_{n+1} = 0,5u_n- 3\;,\]
et comme $u_n = v_n-6$,on a :
\begin{align*}
u_{n+1} & = 0,5(v_n-6)-3\\
& = 0,5v_n-6.
\end{align*}

Finalement, 
\begin{align*}
v_{n+1} & =0,5v_n+6-6\\
& =0,5v_n.
\end{align*}

Cela montre que la suite $(v_n)$ est une suite géométrique de raison $0,5$. 

Son premier terme $v_0$ est égal à $u_0 + 6$, donc $v_0 = 7$.

\item Le terme général de la suite géométrique de raison $0,5$ et de premier terme $7$ est :
\[ v_n = 7 \times (0,5)^n.\]
On en déduit $u_n$ grâce à la relation $u_n = v_n -6$.

Donc,
\[u_n = 7 \times (0,5)^n - 6. \]

\item D'après le cours, comme $-1 < 0{,}5 < 1$, on a :
\[ \lim\limits_{n \to +\infty} (0,5)^n = 0.\]
On en déduit que :
\[ \lim\limits_{n \to +\infty} \left[7 \times (0,5)^n - 6\right] = -6.\]
La suite $(u_n)$ admet donc $-6$ comme limite en $+\infty$.
\end{questions}
\end{solintro}

\endinput