\documentclass[4apaper,11pt,french]{article}
\linespread{1}

\newcommand{\typedoc}{Cours}          %%%%%%%%%%%%%%% 1ere ligne du titre de la feuille
\newcommand{\Ch}{Le raisonnement par r\'ecurrence}  %%%%%%%%%%%%%%%% 2eme ligne et en haut à droite après
\newcommand{\ch}{Chapitre 2}		 %%%%%%%%%%%%%%% En haut à gauche (numero chapitre)
\newcommand{\Cl}{TG3}
\newcommand{\Annee}{2016-2017}
	
\newcommand{\serie}{Scientifique}
\newcommand{\num}{0}	
\newcommand{\tps}{1 semaine}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%		Package

\input macro_final.tex

\setcounter{NumLecon}{2}

\geometry{tmargin=2cm,bmargin=2.4cm,hmargin=1.5cm}
%\geometry{verbose,letterpaper,tmargin=1.8cm,bmargin=1.8cm,lmargin=1.5cm,rmargin=1.5cm}

\renewcommand{\arraystretch}{1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Premiere page
\begin{document}
 
 
%\DocCha

\Chacha{wire.eps}{The Wire}{David Simon}{Télécharger c'est tuer l'industrie, tuons les tous}{Thurston Moore (Sonic Youth)}{
``Sur écoute'' (The Wire) est une série télévisée américaine, créée par David Simon et Ed Burns.\\
Elle a pour sujet la criminalité dans la ville de Baltimore, à travers la vision de ceux qui la vivent au quotidien : policiers, trafiquants en tous genres, politiques, enseignants, journalistes, résidents de Baltimore, etc.
\\
Avec un aspect de quasi-documentaire par son réalisme et son non-manichéisme, la série est acclamée par la critique, bien qu'elle n'ait pas connu un succès commercial important. Elle est souvent considérée comme la meilleure série télévisée jamais diffusée à la télévision, et l'une des fictions les plus abouties dans les années 2000, notamment pour sa représentation réaliste quasi littéraire de la vie urbaine, et son exploration profonde des thèmes socio-politiques de l'Amérique. 
\\
Le tour de force de la série est de s'engager, sur le plan social, en montrant sans détour les pans les plus sombres du décor américain, son revers le plus inavouable, tout en mettant en scène une multitude de points de vue réalistes qui multiplient les questions dérangeantes sans jamais proposer de solution miracle. Il n'y a pas de fausse objectivité rassurante et pas de subjectivité accusatrice sous-jacente, l'épisode ne fait que montrer le plus passivement possible, il en résulte un étrange bourdonnement qui persiste longtemps après sa diffusion.
}{0.5}{0.5}{
\item Comprendre le principe du raisonnement par récurrence
\item Rédiger une démonstration par récurrence
}

\TITRE{dominos.eps}{0.8}

\begin{Intro}{Introduction}
Lorsque l'on cherche à démontrer qu'une proposition est toujours vraie, 
on peut commencer par regarder des cas particuliers. 
Cependant, ceci ne prouve pas qu'une proposition est vraie tout le temps. \\
Il s'avère donc nécessaire de mettre en place des raisonnements logiques pour arriver à une conclusion
valide. Il en existe plusieurs types, dont certains que vous connaissez déjà, et vous allez en découvrir
un nouveau dans ce chapitre, fondamental en classe de Terminale Scientifique.

Encore une fois, un grand merci à Téhessin, mon mentor absolu...
\end{Intro}



\section{Découverte}
\subsection{Présentation du raisonnement en Syldavie}

Il existe en Syldavie une terrible maladie qui frappe depuis des siècles les petits syldaves et 
les fait naître avec un unique mais énorme cheveu sur la tête.\\
C'est Vaclav \textsc{Grtschtsz} qui, le premier, contracta cette maladie en 1643 
après être rentré en contact avec des vénusiens : ce fait peu connu marque la cause de 
l'apparition de la maladie en Syldavie. Depuis, tous ses descendants ont souffert de ce 
terrible mal et aucun médicament terrestre ne semble en mesure de stopper cette calamité.\\
Après de longues années de recherches, les scientifiques syldaves viennent de mettre en évidence 
que cette maladie était bien génétique et que l'allèle associé à cette maladie était dominant. 
\\
%Norbert, un descendant de Vaclav \textsc{Grtschtsz}, souffre de cette maladie. 
Résumons les faits :

\begin{itemize}
\item  Notons $n$ la $n^{\text{ème}}$ génération aprés Vaclav et $\mathscr P(n)$ la 
proposition~:~<<~la $n^{\text{ème}}$ génération est infectée par la maladie~>>
\item Un premier syldavien est infecté en 1643, donc $\mathscr P(0)$ est vraie ;
\item Si un des parents de la $k^{\text{ème}}$ génération est 
atteint, alors ses enfants de la $(k+1)^{\text{ème}}$ génération seront également 
infectés, puisque la maladie est portée par un allèle dominant.
Ceci se traduit par \[ \mathscr P(k)\ \text{vraie}{\red\Longrightarrow} \mathscr P(k+1)\ \text{vraie}\]
\item Nous en déduisons immédiatement que, quelque soit la génération $n$ des descendants 
de Vaclav, ceux-ci seront infectés, c'est à dire que $\mathscr P(n)$ est vraie $\forall n\in\N$. 
\end{itemize}
Nous venons de faire un \textbf{raisonnement par récurrence}.\\
Remarquons que l'on ne sait rien sur la contamination de syldaves ne descendant pas de Vaclav, puisque l'on n'a 
aucune information sur un éventuel mode de contagion de la maladie. D'où l'importance pour un syldave
quelconque de regarder l'initialisation !


Le raisonnement par récurrence permet de démontrer des propositions mathématiques 
vraies pour tout entier naturel $n$ (ou une partie d'entre eux). 
Les étapes de la démonstration seront les mêmes, et en mathématiques
aussi, l'hérédité sera la partie la plus difficile à montrer (mais vous ne pourrez pas vous 
permettre d'y passer des années !!)

Voyons ce que cela donne sur un exemple un peu plus mathématique.


\subsection{Présentation du raisonnement en mathématiques}

\noindent \begin{minipage}{13cm}
Voici un  test de fin d'étude  maternelle en Syldavie :  prenez un cube,
placez en-dessous  deux autres cubes, et encore en-dessous trois cubes,
etc. \\
Combien y a-t-il de cubes bleus  au total sur le dessin ci-dessus ? \\
On peut encore les compter à la main, mais que faire si je vous demande le nombre de cubes 
lorsqu'on a placé 100 rangées ? $n$ rangées ?\\

\textit{Le dessin nous donne une idée : si nous complétons la figure pour former un rectangle, 
il y a deux fois plus de cubes ! \\}
\end{minipage}
\begin{minipage}{5cm}
\begin{center}
  \includegraphics[height=4cm]{cube}
\end{center} 
\end{minipage}

\noindent On en déduit qu'il y a  \,$\dfrac{4\times (4+1)}{2}$\, cubes, \qquad et donc \qquad $1+2+3+4=\dfrac{4\times 5}{2}$
\\
On a envie de penser que si l'on a placé $100$ rangées, on a $\dfrac{100\times 101}{2}$ cubes, \hfill 
et donc \qquad $1+2+3+...+100=\dfrac{100\times 101}{2}$
\\
Et en généralisant, on a envie de conjecturer que pour tout $n\geq 1$ on a \qquad $1+2+3+...+n=\dfrac{n\times(n+1)}{2}$\\
Mais ceci ne prouve rien ...Reprenons alors la méthode adoptée pour étudier la génétique syldave.

\begin{itemize}
\item \textbf{Proposition : }Nous allons essayer de prouver que la proposition suivante est vraie pour tout entier naturel non nul $n$

\[\mathscr P(n)~:~\text{``}~ 1+2+3+\cdots+n=\dfrac{n(n+1)}{2}~\text{''}\]

\item \textbf{Initialisation :} Il est facile de vérifier que  $1=\dfrac{1(1+1)}{2}$,  donc la proposition est initialisée à $n=1$
\hfill $\mathscr P(1)\ \text{ est vraie}$

\item \textbf{Hérédité :} Supposons qu'une  ``génération'', appelons-la par exemple la $k^{\text{ème}}$ , 
soit ``~infectée~''. \\
Plus sobrement on dira : soit $k$ un entier supérieur à 1. 
Supposons que $\mathscr P(k)$ soit vraie.\\
Essayons alors de montrer que cela implique
que la génération suivante, la $(k+1)^{\text{ème}}$ , sera elle aussi infectée, c'est à dire
\[\mathscr P(k)\ \text{ vraie} {\red \Longrightarrow } \mathscr P(k+1)\ \text{ vraie}\]

Il s'agit donc de montrer que $1+2+3+\cdots+k+(k+1)=\dfrac{(k+1)(k+1+1)}{2}$ sachant que $1+2+3+\cdots+k=\dfrac{k(k+1)}{2}$.\\
Or 
\renewcommand{\arraystretch}{1.7}
\begin{center}
\begin{tabular}{rccl}
$1+2+3+\cdots+k+(k+1)$ &=& $\ds\underbrace{1+2+3+\cdots+k}$&$+(k+1)$ \\
                                   &=& $\dfrac{k(k+1)}{2}     $                     & $+(k+1)$\\
                                   &= & $(k+1)\pa{\dfrac{k}{2}+1}$ & \\
                                   &=&$(k+1)\pa{\dfrac{k+2}{2}}$  &\\
                                   &=& $\dfrac{(k+1)(k+1+1)}{2}$

\end{tabular}
\end{center}

Nous en déduisons que $\mathscr P(k+1)$ est  vraie elle aussi. \hfill  La proposition est donc héréditaire à partir de $1$.

\item \textbf{Conclusion : }Nous avons vérifié que la proposition était vraie au rang 1 
et qu'elle était héréditaire à partir de 1. \\
Nous en déduisons donc que la proposition est toujours vraie, 
quelque soit l'entier naturel $n\geq 1$ grâce au principe admis suivant 
\end{itemize}


\Cadre[Principe du raisonnement par récurrence]{Soit $\mathscr P$ une proposition définie 
sur $\N$. Si :
\begin{itemize}
\item La proposition est \underline{initialisée} à au rang $0$ (i.e si $\mathscr P(0)$ est vraie)
\item La proposition est \underline{héréditaire} à partir du rang $0$ (i.e si \,$\forall n\geq 0$ \,
on a \, $\mathscr P(n)$\, vraie \,$\Longrightarrow \mathscr P(n+1)$ \,vraie)
\end{itemize}
Alors : \qquad\qquad
La proposition $\mathscr P(n)$ est vraie  $\forall n\in\N$.}

\Dem[Hors Programme]{
Supposons qu'il existe au moins un entier $n$ pour lequel $\mathscr P(n)$ n'est pas vraie, 
et appelons $m$ le plus petit d'entre eux.\\
Comme $m$ est le plus petit d'entre eux, et que $m\neq 0$ (car on a déjà vérifié 
l'initialisation) on sait que pour tout $0\leq n < m$, $\mathscr P(n)$ est vraie. 
En particulier $\mathscr P(m-1)$ est vraie.\\
Mais d'après le caractère héréditaire de la proposition, on sait que cela entraine $\mathscr P(m)$ vraie aussi. 
Ce qui est absurde ...
}

\Rqs{
\item Le principe du raisonnement par récurrence sur un intervalle du type \textlbrackdbl 
$ N,+\infty  [$ est identique, ainsi que sa démonstration. Il suffit de remplacer $0$ par $N$.
\item Tout comme dans l'exemple syldave, il peut arriver que des propositions soient héréditaires,
mais qu'elles ne soient pas initialisées. 
On ne pourra alors évidemment pas dire que ces propositions sont vraies !
}

\section{Deux exemples classiques}
\subsection{Trame de rédaction à connaître par coeur}

\begin{ExoC}
 Prenons un cube, rajoutons trois autres cubes
pour former un carré, puis cinq autres cubes pour former un plus
grand carré, puis sept autres cubes pour former un carré encore
plus grand...
\\
Nous voulons maintenant connaître le nombre de cubes présents à la $n^{\text{ème}}$ étape.


\begin{enumerate}
\item Proposez une formule générale inspirée du résultat de notre petite activité de \textit{maternelle}. 
\item Démontrez par récurrence votre proposition, en complétant la trame ci-dessous.
\end{enumerate}
\begin{itemize}
 \item \textcolor{blue}{\textbf{Proposition :} On veut montrer que notre proposition $\mathscr P(n)~:~ ...$  \\
est vraie pour tout $n \geq ... $}\\
 \item {\blue\textbf{Initialisation :}  Pour $n=...$\\
 \begin{tabular}{L{7cm}|L{7cm}}
  \quad& \tabularnewline
  %\quad& \tabularnewline
  %\quad& \tabularnewline
  \quad \tabularnewline
 \end{tabular}\\
Donc notre proposition est vraie au rang ...$\qquad$\\
\item \textbf{Hérédité :} Soit $k$ un entier supérieur ou égal à ... \hfill  
Montrons que $\mathscr P(k)$ vraie  $\Longrightarrow \mathscr P(k+1)$ vraie.\\
Il s'agit donc de montrer que ... \\
sachant ...}\\
$\begin{array}{llcr}
\text{Or }& 1+3+5+ \dots + ... + ... & = & ...\\\\
%&& = & \\\\
%&& = &
\end{array}$\\
{\blue Ainsi, notre proposition est vraie au rang ... \hspace{2cm}
Donc, notre proposition est ... \\
 \item \textbf{Conclusion :}
Notre proposition est ...\hspace{5cm} et ...\\
Elle est donc vraie pour tout $n \geq ...$}
\end{itemize}
\end{ExoC}

\subsection{Tout seul comme un grand}
\begin{ExoC}
On note $(u_n)_{n\in\N}$ la suite définie par $u_0=0$ et $u_{n+1}=\sqrt{u_n+6}$.\\
Démontrer par récurrence que $\forall n \in \N$ on a $0 \leq u_n \leq u_{n+1}\leq 3$.
\end{ExoC}

\Sol{
\begin{itemize}
 \item \textbf{Proposition :} On veut montrer que $\mathscr P(n) : `` 0 \leq u_n \leq u_{n+1} \leq 3 ''$ est vraie $\forall n \geq 0$.
 \item \textbf{Initialisation :} pour $n=0$\\
 \begin{tabular}{L{5cm}|C{3cm}}
$u_0=0$ &  $0\leq 0\leq \sqrt{6} \leq 3$  \tabularnewline
$u_1=\sqrt{0+6}=\sqrt{6}\simeq 2.4$ &   $0\leq u_0\leq u_1 \leq 3$ \tabularnewline
 \end{tabular}
\hfill Donc $0\leq u_0 \leq u_1\leq 3$ et $\mathscr P(0)$ est vraie.\\
\item \textbf{Hérédité :} Soit $k \geq 0$ un entier. \qquad  Montrons que\quad  $\mathscr P(k)$ vraie
$\Longrightarrow \mathscr P(k+1)$ vraie.\\
Il s'agit donc de montrer que \quad $0 \leq u_{k+1} \leq u_{k+2}\leq 3 $\quad , c'est-à-dire \quad $ 0 \leq \sqrt{u_k+6} \leq \sqrt{u_{k+1}+6} \leq 3$
\qquad sachant que l'on a \quad $0 \leq u_k \leq u_{k+1}\leq 3$
\begin{eqnarray*}
\text{Or } \quad  0  \leq  u_{k} \leq u_{k+1} \leq  3  & \stackrel{+6}{\iff} &  6  \leq  u_k+6\leq  u_{k+1}+6  \leq  9 \\
& \stackrel{\sqrt{~}}{\iff} &  \sqrt{6}  \leq  \sqrt{u_k + 6}  \leq  \sqrt{u_{k+1} + 6}  \leq  \sqrt{9} \quad \text{ car la fonction }\sqrt{~~} \text{ conserve l'ordre sur les positifs} \\
& \iff & 0  \leq  u_{k+1}\leq  u_{k+2}  \leq  3
\end{eqnarray*}
Donc $\mathscr P(k+1)$ est vraie. La proposition est héréditaire à partir de 0.\\
 \item \textbf{Conclusion :} La proposition est vraie au rang $0$ et héréditaire à partir de $0$.\\
Elle est donc vraie pour tout $n \geq 0 $
\end{itemize}
\Rq{On en déduit que la suite $(u_n)$ est bornée et  croissante.
}
}

\section{Pour bien assimiler}
\begin{ExoF}
 On donne ci-dessous trois propositions vraies. 
\begin{enumerate}
\begin{multicols}{2}
 \item Pour tout entier $n\geq 5$, $2^n > n^2$
 \item Pour tout réel $x>0$, $(x+1)^3 \geq 1+3x$
 \item Pour tout entier $n \geq 1$, $\sum_{k=1}^n (2k-1)^3=2n^4-n^2$
 \end{multicols}
\end{enumerate}
Pour lesquelles peut-on envisager une démonstration par récurrence (que l'on ne fera pas) ?
\end{ExoF}

\begin{ExoF}
 La suite $(u_n)$ est définie, pour tout entier naturel $n$, par : 
$\left\{ \begin{array}{l} u_0=2 \\ u_{n+1}=2 u_n -3  \end{array} \right.$\\
Démontrer par récurrence que, pour tout entier naturel $n$, on a $u_n=3-2^n$
\end{ExoF}

\begin{ExoF}
 On considère la suite $(u_n)_{\N}$ définie par son premier terme $u_0$ et pour tout $n$ par la 
 relation \\
$u_{n+1}=3u_n+1$. Démontrer chacune des propositions suivantes.
\begin{multicols}{2}
\begin{enumerate}
\item La proposition \og $u_n \leq u_{n+1}$ \fg est héréditaire.
 \item La proposition \og $u_n \geq u_{n+1}$ \fg est héréditaire.
 \item Si $u_0=1$ la suite $u$ est croissante.
 \item Si $u_0=-2$, la suite $u$ est décroissante.
 \item Su $u_0=-0.5$, la suite $u$ est stationnaire.
 \end{enumerate}
 Illustrer graphiquement les trois derniers résultats.
\end{multicols}

\end{ExoF}

\begin{ExoF}
 \begin{enumerate}
  \item Montrer que les deux propositions suivantes sont héréditaires\\
  $(A)$ : \og $10^n-1$ est un multiple de $9$ \fg \qquad\qquad \qquad\qquad 
  $(B)$ : \og $10^n+1$ est un multiple de $9$ \fg
\item Sont-elles vraies pour tout entier naturel $n$ ?
 \end{enumerate}
\end{ExoF}


\begin{ExoF}
On considère la suite $(u_n)$ définie sur $\N$ par \quad $ u_0=3\qquad \text{et}\qquad u_{n+1}=2+\dfrac{1}{u_n}$\\
Montrer que, pour tout $n\in\N$ on a \quad $ 2\leq u_n\leq 3$
\end{ExoF}


\begin{ExoF}
\begin{enumerate}
 \item  Démontrer que $$\sum\limits_{k=0}^{n} k^2=\dfrac{n(n+1)(2n+1)}{6}$$
\item On  note $S_n$ la somme des cubes des $n$ premiers entiers naturels non nuls.
\begin{enumerate}
\item Calculer $S_1$, $S_2$ et $S_3$.
\item Démontrer par récurrence que, pour tout entier naturel $n\geq 1$, on a $S_n=\left(\sum_{k=1}^n k\right)^2$\footnote{On
utilisera la formule démontrée dans le cours sur la somme des $n$ premiers entiers.}
\item Quel est l'entier $n$ pour lequel $S_n=\nombre{3025}$ ?
\end{enumerate} 
\item On note $P_n$ la somme des cubes des $n$ premiers entiers naturels \textbf{pairs} non nuls.
\begin{enumerate}
 \item Calculer $P_1$, $P_2$ et $P_3$.
\item Démontrer par récurrence que, pour tout entier naturel $n\geq 1$, on a $P_n=2n^2(n+1)^2$
\item Quel est l'entier $n$ pour lequel $P_n=\nombre{1800}$ ?
\end{enumerate}
\item On note $I_n$ la somme des cubes des $n$ premiers entiers naturels \textbf{impairs} non nuls.
\begin{enumerate}
\item Calculer $I_1$, $I_2$ et $I_3$.
\item Démontrer par récurrence que, pour tout entier naturel $n\geq 1$, on a $I_n=n^2(2n^2-1)$
\item Quel est l'entier $n$ pour lequel $I_n=\nombre{41328}$ ?
\end{enumerate}
\end{enumerate}
\end{ExoF}

\begin{ExoF}
Montrer que $4^n-1$ est un multiple de $3$ pour tout entier naturel $n$.
\end{ExoF}

\begin{ExoF}
Démontrer par récurrence que pour tout entier naturel $n$, $2^{3n}-1$ est un multiple de $7$.
\end{ExoF}


\begin{ExoF}
Pour tout entier $n\geq 1$, on note la fonction $f_n$ définie sur $\R$ par $f_n(x)=x^n$. \\
On rappelle la proposition suivante, énoncée en 1S, mais non démontrée :
$$\forall n \in \N^*,\quad \text{on a} \quad f_n \text{ est dérivable sur } \R \quad \text{et} \quad
f_n'(x)=nx^{n-1}$$
\begin{enumerate}
 \item Démontrer que pour $n=1$ la proposition est vraie.
 \item Vérifier que les formules de 1S pour $n=2$ et $n=3$ correspondent à la formule 
 générale énoncée ci-dessus.
 \item Démontrer par récurrence que pour tout entier $n\geq 1$, on a $f_n'(x)=nx^{n-1}$.
\end{enumerate}
\end{ExoF}

\begin{ExoF}
 Démontrer que pour tout entier $n\geq 0$, l'\textbf{inégalité de Bernoulli} est vraie :
$$\forall x >0 \text{ , on a } (1+x)^n \geq 1+nx$$
\end{ExoF}

\begin{ExoF}
\begin{enumerate}
 \item Rappeler ce que signifie l'écriture $\left(\begin{array}{c}
                                                   n \\ k
                                                  \end{array}\right)$ pour $n$ et $k$ entiers tels que $0 \leq k \leq n$.
\item Compléter la propriété suivante, vu en première :\\
\indent Pour tous $n$ et $k$ entiers tels que $0 \leq k \leq n$, on a  $\left(\begin{array}{c}
                                                   n \\ k
                                                  \end{array}\right) + \left(\begin{array}{c}
                                                   n \\ k+1
                                                  \end{array}\right) = $
\item Ecrire les 5 premières lignes du triangle de Pascal.
 \item Démontrer que pour tous réels $a$ et $b$ on a 
$$(a+b)^3 = a^3 + 3 a^2 b + 3 ab^2 + b^3$$
%ainsi que 
%$$(a+b)^4 = a^4 + 4a^3b + 6 a^2 b^2 + 6 a^2b^2 +4ab^3 + b^4$$
\item Quel lien observe-t-on entre les coefficients de développement et le triangle de Pascal ?
\item Démontrer par récurrence que pour tout $n \geq 1$ on a :
$$(a+b)^n=\sum_{k=1}^n \left(\begin{array}{c}
                                                   n \\ k
                                                  \end{array}\right)a^{n-k}b^k$$
formule appelée \textbf{formule du binôme de Newton}.
\item \textit{Application} : développer $(a+b)^5$ sans calcul.
\end{enumerate}
\end{ExoF}


\section{Quelques exercices corrigés }
\begin{ExoC}
Démontrer que pour tout $n\in\N$ on a \quad $\sum\limits_{k=0}^{n} k^2=\dfrac{n(n+1)(2n+1)}{6}$
\end{ExoC}

\Sol{ On considère la propriété $\mathscr P$, définie pour tout $n\in\N$, par : 
$$ \mathscr P(n):\sum\limits_{k=0}^{n} k^2=\dfrac{n(n+1)(2n+1)}{6}$$
\begin{itemize}
\item \textbf{Initialisation} : Pour $n=0$, on a $0=0$, donc $\mathscr P(0)$ est vraie.
\item \textbf{Hérédité} : Supposons que $\mathscr P(n)$ soit vraie i.e que $\sum\limits_{k=0}^{n} k^2=\dfrac{n(n+1)(2n+1)}{6}$ pour un certain rang $n$ et montrons que $\mathscr P(n+1)$ est vraie.\\
$$ \sum\limits_{k=0}^{n+1} k^2=\sum\limits_{k=0}^{n} k^2+(n+1)^2=\dfrac{n(n+1)(2n+1)}{6}+(n+1)^2=\dfrac{n(n+1)(2n+1)}{6}+\dfrac{6(n+1)^2}{6}$$
$$=\dfrac{n(n+1)(2n+1)+6(n+1)^2}{6}=\dfrac{(n+1)[n(2n+1)+6(n+1)]}{6}=\dfrac{(n+1)(2n^2+7n+6}{6}$$
Or, $(n+2)(2n+3)=2n^2+3n+4n+6=2n^2+7n+6$, par conséquent :
$$ \sum\limits_{k=0}^{n+1} k^2=\dfrac{(n+1)(n+2)(2n+3)}{6}$$
la propriété est donc héréditaire, et donc on a montré par récurrence que $$\sum\limits_{k=0}^{n} k^2=\dfrac{n(n+1)(2n+1)}{6}\qquad \forall n\in\N$$
\end{itemize}
}


\begin{ExoC}
Considérons la suite $(u_n)$, définie pour tout $n\in\N$, par : \quad
$\left\{ \begin{array}{l} u_0=1 \\u_1=2\\ u_{n+2}=5u_{n+1} -6u_n  \end{array} \right.$\\
Démontrer que pour tout $n\in\N$ \quad $ u_n=2^n$
\end{ExoC}

\Sol{Notons $ \mathscr P(n):u_n=2^n$
\begin{itemize}
\item \textbf{Initialisation} : $u_0=2^0=1$, par conséquent $\mathscr P(0)$ est vraie.
\item \textbf{Hérédité} : Supposons que $\mathscr P(i)$ soit vraie $\forall i\leq n$, montrons que $\mathscr P(n+1)$ est vraie i.e montrons que $u_{n+1}=2^{n+1}$\\
On a : $ u_{n+1}=5u_{n} -6u_{n-1}=5\times 2^n-6\times 2^{n-1}=10\times 2^{n-1}-6\times 2^{n-1}=4\times 2^{n-1}=2^{n+1} $
\end{itemize}
On en conclut donc, par récurrence, que $u_n=2^n$, $\forall n\in\N$}

\begin{ExoC}Démontrer que, pour tout entier $n \geq 2$, la fonction $f_n$, définie 
sur $\R$ par $f_n(x)=x^n$, est dérivable sur $\R$, avec $f'_n(x)=nx^{n-1}$
\end{ExoC}

\Sol{Notons $\mathscr P(n):f_n$ est dérivable
\begin{itemize}
\item \textbf{Initialisation} : $f_2(x)=x^2$, on a :
$$ \dfrac{f_2(x+h)-f(x)}{h}=\dfrac{(x+h)^2-x^2}{h}=\dfrac{x^2+2xh+h^2-x^2}{h}=2x+h$$
qui tend vers $2x$ lorsque $h$ tend vers $0$, par conséquent $\mathscr P(2)$ est vraie.
\item \textbf{Hérédité} : Supposons que $\mathscr P(i)$ soit vraie $\forall i\geq n$, montrons que $\mathscr P(n+1)$ est vraie i.e montrons que $f_{n+1}$ est une fonction dérivable.
\\
Notons que $f_{n+1}(x)=x^{n+1}=x^n\times x=f_n\times f_1$, or le produit de deux fonctions dérivables est une fonction dérivable, par conséquent $f_{n+1}$ est dérivable et sa dérivée vaut :
$$ f'_{n+1}(x)=f'_n(x)f_1(x)+f_n(x)f'_1(x)=nx^{n-1}x+x^{n-1}x=nx^n+x^n=(n+1)x^n \qquad \text{ Cqfd}$$
\end{itemize}
}

\begin{ExoC}
On considère la suite $(u_n)$ définie par $u_0=0$ et pour tout entier naturel $n$ :\quad $ u_{n+1}=\sqrt{\dfrac{1+u_n}{2} }$\\
Montrer, par récurrence, que pour tout $n\geq 1$ on a $ \dfrac{1}{\sqrt{2} }\leq u_n\leq 1$ 
\end{ExoC}

\Sol{\begin{itemize}
\item \textbf{Initialisation} : $u_1=\sqrt{\dfrac{1}{2} }=\dfrac{1}{ \sqrt{2} }$, donc \quad 
$ \dfrac{1}{ \sqrt{2} }\leq u_1 \leq 1$
\item \textbf{Hérédité} : Supposons que, pour un entier $n\geq 1$ on ait \quad $ \dfrac{1}{\sqrt{2} }\leq u_n\leq 1$\\
Montrons que $ \dfrac{1}{\sqrt{2} }\leq u_{n+1}\leq 1$.
On a 
$$\dfrac{1}{\sqrt{2} }\leq u_n\leq 1 \iff \dots\dots \iff 
\sqrt{\dfrac{1+\sqrt{2}}{\sqrt{2}}}\leq \sqrt{\dfrac{1+u_n}2} \leq 1$$
Or $\sqrt{\dfrac{1+\sqrt{2}}{\sqrt{2}}} > \dfrac{1}{\sqrt{2}}$.\\
Donc on a bien  $$  \dfrac{1}{\sqrt{2} }\leq u_{n+1}\leq 1$$
Ainsi, pour tout $n\geq 1$,  $ \dfrac{1}{\sqrt{2} }\leq u_n\leq 1$ 
\end{itemize}}
\end{document}

















