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

\newcommand{\ch}{Chapitre 1}
\newcommand{\Ch}{Divers raisonnements  \linebreak[2]  math\'ematiques}
\newcommand{\Cl}{TS}
\newcommand{\Annee}{2013-2014}
	

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

\input macrodwicky.tex

\geometry{hmargin=2cm,vmargin=2.2cm}

\setcounter{NumLecon}{1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Premiere page
\begin{document}

\ddwicky{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 Maîtriser les symboles mathématiques de la démonstration
\item Avoir conscience de différents types de raisonnements logiques
\item Traduire et comprendre les quantificateurs
\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}
L'objectif de ce chapitre est de faire le point sur divers types de raisonnements logiques utilisés en
mathématiques, permettant d'établir des démonstrations.\\
Lorsque l'on cherche à démontrer qu'une proposition est toujours vraie ou au contraire fausse, 
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 les principaux sont exposés ici.\\
A votre niveau, on ne vous demandera pas de savoir faire des démonstrations de cours, mais on peut vous demander 
de savoir les reproduire. Pour cela, la meilleure manière est de les comprendre, notamment dans leur démarche,
et donc dans le type de raisonnement invoqué. De plus, vous constaterez que ces raisonnements sont valables 
pour résoudre des problèmes et des exercices de votre niveau. Vous avez déjà rencontré la plupart d'entre eux,
mais vous allez également découvrir ici le raisonnement par récurrence, fondamental en classe de Terminale Scientifique.
\end{Intro}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Le cours
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 0. Position du pb
%\newpage

\section{Des symboles à connaître}

\subsection{Implication $\Longrightarrow$, réciproque $\Longleftarrow$ et équivalence $\iff$}

\begin{defi}
Le symbole $\Longrightarrow$ signifie \og \textbf{implique} \fg . On peut également traduire une propriété
contenant ce symbole sous la forme \og Si \dots Alors \fg .\\
L'\textbf{implication} est le principe même du raisonnement mathématique :
dans une propriété, une hypothèse entraîne une conclusion.\\
On dit que l'hypothèse est une de \textbf{condition suffisante} pour conclure,
et que la conclusion est une \textbf{condition nécessaire} pour avoir l'hypothèse.
\end{defi}

\Expls{Considérons les propositions vraies suivantes :
\begin{itemize}
 \item Si je m'appelle Ana, alors je suis une fille.\\
\textit{S'appeler Ana est une condition suffisante pour conclure que je suis une fille.
%et être une fille est une condition nécessaire pour s'appeler Ana
}
 \item Si un quadrilatère est un rectangle, alors c'est un parallélogramme.
\textit{Qu'un quadrilatère soit un rectangle est une condition suffisante pour conclure qu'il s'agit d'un 
parallélogramme.%, et qu'un quadrilatère soit un parallélogramme est une condition nécessaire 
%pour qu'il soit un rectangle.
}
 \item $x \geq 10 \Longrightarrow 3x\geq 15$.
\end{itemize}
}

\begin{defi}
La \textbf{réciproque} d'une propriété consiste à retourner la phrase en échangeant l'hypothèse et la 
conclusion, ou encore à changer le sens de la flèche.\\
Une propriété et sa réciproque sont indépendantes et se démontrent séparément.\\
\textit{En effet le fait qu'une propriété soit vraie n'implique pas que sa réciproque le soit !}
\end{defi}

\Expls{Considérons les réciproques des propositions de l'exemple précédent.
\begin{itemize}
 \item Si je suis une fille, alors je m'appelle Ana : FAUX\\
\textit{Pour m'appeler Ana, %il est nécessaire que je sois une fille, mais cela n'est pas suffisant.}
il n'est pas suffisant d'être une fille.}
 \item Si un quadrilatère est un parallélogramme, alors c'est un rectangle : FAUX\\
\textit{Pour qu'un quadrilatère soit un rectangle, 
%il est nécessaire qu'il soit un parallélogramme, mais cela n'est pas suffisant.}
il n'est pas suffisant qu'il soit un parallélogramme.}
 \item $x \geq 10 \Longleftarrow 3x\geq 15$ : FAUX \\
\end{itemize}
}

\begin{defi}
Lorsqu'une propriété et sa réciproque sont vraies, on utilise le symbole $\iff$, qui signifie 
\og \textbf{équivaut à} \fg . On peut également traduire 
ce symbole par \og \textbf{Si et seulement si} \fg .\\
On parle d'\textbf{équivalence} entre l'hypothèse et la conclusion.
%qui sont alors des \textbf{conditions nécessaires et suffisantes} l'une à l'autre.
\end{defi}

\Expls{
\begin{itemize}
 \item $ABC$ est un triangle rectangle en $A$ si et seulement si $BC^2=AB^2+AC^2$
 \item $x\geq 5 \iff 3x \geq 15$
\end{itemize}
}



\subsection{Les quantificateurs pour tout $\forall$ et il existe $\exists$}
\begin{defi}
Les \textbf{quantificateurs}. Ils précisent le domaine de validité d'une propriété.\\
Au lycée, vous devez connaître les symboles $\forall$ et $\exists$, 
qui signifient respectivement \og \textbf{Pour tout} \fg et \og \textbf{Il existe un} \fg , sous entendu \og 
(au moins) \fg . La virgule qui suivra le symbole $\exists$ sera alors 
traduite par \og tel que \fg.\\
\textit{Il est donc essentiel de bien les comprendre pour savoir dans quels cas une propriété peut 
s'appliquer.}
\end{defi}

\Expls{
\begin{itemize}
 \item $\forall x \in \R$, $x^2\geq 0$ 
 \item $\exists x \in \R$, $x^2\geq 100$ 
\end{itemize}
}

\Att{
Lorsqu'on énonce des propositions toujours vraies en français, on sous-entend souvent les quantificateurs.
}
\Expls{
\begin{itemize}
 \item Noël est en décembre (sous entendu \og \textbf{Tous} les ans \fg) 
 \item Un parallélogramme dont les diagonales sont de même longueur est un rectangle 
(sous-entendu \og \textbf{Tous} les parallélogrammes \fg)
 \item Un parallélogramme peut avoir des diagonales de même longueur (sous-entendu \og \textbf{il existe} (au moins) 
un tel parallélogramme \fg)
\end{itemize}
}


\Att{
Les deux quantificateurs \og \textbf{tout} \fg et \og \textbf{il existe} \fg sont liés lorsqu'il s'agit 
d'énoncer le contraire d'une proposition. En effet, le contraire de \og tout \fg n'est pas \og aucun \fg, mais 
\og il existe (au moins) un \fg.\\
}

\Expls{
Le contraire de \og \textbf{Tous} les ans, Noël est en décembre \fg est la proposition \og \textbf{Il existe
une} année (au moins) ou Noël n'est pas en décembre \fg.\\
Le contraire de \og \textbf{Tous} les rectangle sont des parallélogrammes \fg est la proposition \og \textbf{Il existe
un} rectangle (au moins) qui n'est pas un parallélogramme \fg. \\
\textit{Evidemment une proposition et son contraire ne peuvent pas être toutes les deux vraies.}\\
\textit{Pour énoncer le contraire de ces propositions, on a dit qu'il existait au moins un cas où l'hypothèse émise
était vérifiée, mais pas la conclusion. }
}




\begin{exoi}
On définit sur $\N^*$ la suite $(u_n)$ de terme général $u_n=\dfrac1n$.\\
On considère la proposition suivante :
$$\forall \varepsilon >0 ,\, \exists N \in \N ,\, \forall n \geq N \,\text{ on a } \, u_n < \varepsilon$$
\begin{enumerate}
 \item Traduire cette phrase mathématique en français.
 \item On choisit $\varepsilon=1$. 
\begin{enumerate}
 \item Trouver un rang $p$ telle que $u_p < \varepsilon$.
 \item Montrer que pour tout $n\geq p$ on a $u_n < \varepsilon$
 \item Conclure par rapport à la proposition donnée dans ce cas particulier.
\end{enumerate}
 \item Même question pour $\varepsilon = 0.1$, $0.01$ et $ 10^{-6}$.
 \item Peut-on conclure que la proposition est vraie ?
 \item Démontrer cette proposition dans le cas général (ie pour $\varepsilon$ quelconque).
\end{enumerate}
\end{exoi}


\section{Des raisonnements déjà connus}
\subsection{Le contre-exemple}

\Act{
\begin{enumerate}
 \item Démontrer que les propositions suivantes sont fausses :
\begin{enumerate}
 \item \og Aujourd'hui tout est fabriqué en Chine \fg
 \item \og Un quadrilatère dont les diagonales sont de même longueur est un rectangle \fg 
\end{enumerate}
 \item Pour tout entier naturel $n \geq 1$, on considère la proposition $\mathscr P(n)$ : 
\og L'entier $n^2-n+11$ est premier \fg ie qu'il admet exactement deux diviseurs (1 et lui-même).
\begin{enumerate}
 \item La proposition $\mathscr P(1)$ est-elle vraie ?
 \item Faire un tableau de valeurs à la calculatrice de l'expression $n^2-n+11$ pour $n$ allant de $1$ à $10$.\\
Que dire de $\mathscr P(2)$ ? $\mathscr P(3)$ ? $\mathscr P(4)$ ? $\mathscr P(10)$ ?
 \item La proposition $\mathscr P(n)$ est-elle vraie pour tout entier naturel $n$ ?
\end{enumerate}
\end{enumerate}
}

\begin{defi}
Le \textbf{contre-exemple} s'utilise pour montrer qu'il existe au moins un cas où une proposition n'est pas vraie, 
donc qu'elle est fausse.
\end{defi}

\Expl{Montrer par un contre-exemple que la proposition $\mathscr P(n)$ :
\og L'entier $n^2-n+41$ est premier \fg n'est pas vraie pour tout $n\in\N$. 
}

\Sol{
Si on choisit $n=41$, alors $n^2-n+41 = 41^2-41+41 = 41^2$ qui admet pour diviseurs $1$, $41$ et $41^2$. Ce n'est
donc pas un nombre premier.\\
\textit{On peut vérifier que pour tout $0 \leq n < 41$ on a $n^2-n+41$ qui est premier. Mais ce n'est pas 
parce qu'une proposition est vraie sur les $41$ premiers entiers naturels qu'elle l'est pour tous ...}
}

\subsection{La disjonction de cas}
\begin{defi}
On parle de raisonnement par \textbf{disjonction de cas} pour démontrer qu'une proposition est vraie, 
lorsque la démonstration effectuée dépend de la situation, mais que l'on traite tous les cas possibles 
séparément.\\
\textit{Au préalable, on commence par un tri, pour restreindre le nombre de cas à étudier.}
\end{defi}

\Expls{
\begin{itemize}
 \item Aux échecs, le joueur qui a gagné annonce \og Echec et Mat \fg avant que son adversaire joue, car il a
envisagé tous les déplacements adverses possibles et qu'aucun ne l'empêche de gagner.
 \item Montrer par disjonction de cas que pour tout entier naturel $n$, le produit $n(n+1)$ est divisible par 2.
\end{itemize}
}

\Sol{
Considérons les seuls deux cas possibles : $n$ est soit pair, soit impair.
\begin{itemize}
 \item Si $n$ est pair, alors il existe un entier $k$ tel que $n=2k$ et donc $n(n+1)=2k\times (2k+1)$ ce qui est un 
divisible par 2.
 \item Si $n$ est impair, alors il existe un entier $k$ tel que $n=2k+1$ et donc 
$n(n+1)=(2k+1)(2k+1+1)=(2k+1)(2k+2)=2(2k+1)(k+1)$ ce qui est divisible par 2.
\end{itemize}
Donc dans tous les cas, $n(n+1)$ est divisible par 2. La proposition est vraie pour tout $n\in\N$.
}

\subsection{L'absurde et la contraposé}


\begin{defi}
Le raisonnement par l'\textbf{absurde} est une forme de raisonnement logique, consistant 
à démontrer la vérité d'une proposition en prouvant l'absurdité du contraire.\\
\textit{En effet, une proposition est forcément vraie ou fausse, mais jamais les deux à la fois.}\\
\end{defi}


\Expl{
\begin{enumerate}
 \item Montrer par l'absurde que $\forall n\in\N$, $n^2$ impair $\Longrightarrow n$ impair.
 \item Montrer que la réciproque de cette proposition est vraie aussi $\forall n\in\N$.
 \item Traduire ces deux propriétés en une seule.
\end{enumerate}
} 

\Sol{\begin{enumerate}
\item Raisonnons par l'absurde : 
Supposons que la proposition n'est pas vraie pour tout $n\in\N$, ie qu'il existe 
(au moins) un cas où $n^2$ est impair et $n$ pair et plaçons-nous dans ce cas.\\
Comme $n$ est pair, il existe $k\in\N$ tel que $n=2k$ et par conséquent on a $n^2 = 4k^2$.
Donc $n^2$ est pair, ce qui est absurde. Ce cas ne peut pas exister : la proposition 
est vraie pour tout $n\in\N$.
 \item La réciproque à montrer est \og Pour tout $n\in\N$, $n$ impair $\Longrightarrow n^2$ impair \fg .\\ 
Supposons que $n$ est un entier quelconque impair. Alors il existe $k\in\N$ tel que $n=2k+1$. \\
Par conséquent, $n^2 = 4k^2+2k+1 = 2(2k+1) + 1$ qui est un nombre impair.\\
Donc la proposition est vraie pour tout $n\in\N$.
\item $\forall n\in\N$ , $n^2$ impair $\iff n$ impair.
     \end{enumerate}
}

\Cadre[En pratique : mécanisme du raisonnement par l'absurde]{
Pour montrer qu'une proposition $A$ entraîne une proposition $B$ :
\begin{itemize}
 \item On suppose $A$ vraie et la négation de $B$
 \item On montre que cela entraîne contradiction (avec l'hypothèse de $A$ en général)
 \item On en déduit que l'on a forcément $A \Longrightarrow B$ 
\end{itemize}
 }

\begin{defi}
Soit $\mathscr P$ la proposition suivante : 
\begin{center}
\og \textit{Si A est vraie alors B est vraie} \fg \quad 
notée \quad $A \Longrightarrow B$  
\end{center}
La \textbf{contraposée} de $\mathscr P$ est la proposition : 
\begin{center}
\og \textit{Si B n'est pas vraie alors A n'est pas vraie} \fg \quad notée \quad
(Non $B$\,) $\Longrightarrow$ (Non $A$\,) .
\end{center}
 

\end{defi}

\begin{prop}[Définition]
Si une propositon $\mathscr P$ est vraie, alors sa contraposée aussi (et réciproquement).
$$\begin{array}{ccc}
\mathscr P & \text{équivaut à} & \text{Contraposée de }\mathscr P\\
A\Longrightarrow B & \text{ si et seulement si } &  (\text{ Non } B) \Longrightarrow (\text{ Non }A)
\end{array}
$$
On dit que la conclusion $B$ est une \textbf{condition nécessaire} 
à l'hypothèse $A$.\\
Dans le cas où $A \iff B$, on dit que $A$ est une \textbf{condition nécessaire et suffisante} à $B$ (et réciproquement).
\end{prop}


\Dem{
Notons $\mathscr P'$ la contraposée de $\mathscr P$. On veut démontrer l'équivalence 
$\mathscr P \iff \mathscr P'$, donc l'implication et sa réciproque.\\
\fbox{$\mathscr P \stackrel{?}{\Longrightarrow} \mathscr P'$} Raisonnons par l'absurde :\\
Supposons $\mathscr P$ vraie, mais $\mathscr P'$ fausse, à savoir que 
(Non $B$) $\nRightarrow$ (Non $A$), ou encore qu'il existe au moins un cas où $B$ est faux, 
mais $A$ est vrai. Plaçons nous dans ce cas. \\
Comme $A$ est vrai, d'après $\mathscr P$ on a aussi 
$B$ vrai, ce qui est absurde puisque l'on a supposé $B$ faux. Donc $A$ est forcément faux. \\
Ainsi, si une proposition est vraie, alors sa contraposée est vraie aussi.\\
\fbox{$\mathscr P \stackrel{?}{\Longleftarrow} \mathscr P'$} D'après ce qui précède, en supposant 
$\mathscr P'$ vraie, on sait que sa contraposée l'est aussi. \\
Or la contraposée de $\mathscr P'$ est 
$\big(\text{ Non }(\text{ Non } A)\big) \Longrightarrow \big(\text{ Non }(\text{ Non }B)\big)$, 
ie $A \Longrightarrow B$ ou encore $\mathscr P$.\\
Donc $\mathscr P' \Longrightarrow \mathscr P$. \hfill CQFD
}



\Expls{
\begin{itemize}
 \item Si je m'appelle Ana, alors je suis une fille.\\
\textbf{Contraposée (vraie)} : Si je ne suis pas une fille, alors je ne m'appelle pas Ana.\\
\textit{Il est nécessaire d'être une fille pour s'appeler Ana (mais cela n'est pas suffisant).}
 \item Si un quadrilatère est un rectangle, alors c'est un parallélogramme.\\
\textbf{Contraposée (vraie)} : Si un quadrilatère n'est pas un parallélogramme, alors ce n'est pas un rectangle.\\
\textit{Il est nécessaire mais pas suffisant qu'un quadrilatère soit un parallélogramme pour être un rectangle}
 \item $x \geq 10 \Longrightarrow 3x\geq 15$.\\
\textbf{Contraposée (vraie)} : $3x < 15 \Longrightarrow x <10$
 \item Si $ABC$ est un triangle rectangle en $A$, alors $AB^2 + AC^2 = BC^2$\\
\textbf{Contraposée (vraie)} : Si $AB^2 + AC^2 \neq BC^2$ alors $ABC$ n'est pas un triangle rectangle en $A$.
\end{itemize}
}

\Rq{Une proposition ou sa contraposée sont donc équivalentes. Dans un cours, 
on pourrait donc écrire l'une ou l'autre sans perte d'information. \\
En général, le choix de formulation ne se fait pas en fonction de celle que l'on démontre le plus facilement,
mais en fonction de celle que l'on emploie le plus aisément, ou tout simplement celle qu'on a l'habitude de 
rencontrer dans les divers ouvrages : il ne faut pas oublier ce que l'on a reçu en
héritage, provenant de divers horizons, et il est tout à fait normal de
continuer à formuler certaines propriétés comme elles l'ont toujours
été, tout en sachant que dès que l'on en aura besoin, on pourra passer
de l'une à l'autre sans problème.
}

\Expl{
Enoncer alors les contraposées (vraies) des propriétés établies dans l'exemple précédent.
}

\Sol{
\begin{enumerate}
 \item $\forall n\in\N$ , $n$ pair $\Longrightarrow$ $n^2$ pair. 
 \item $\forall n\in\N$ , $n^2$ pair $\Longrightarrow$ $n$ pair.
 \item $\forall n\in\N$ , $n \iff n^2$ pair.
\end{enumerate}
}

\begin{exoi}
\textit{On rappelle que $\forall n\in\N$ , $n$ pair $\iff$ $n^2$ pair.}\\
Montrer par l'absurde que $\sqrt{2}$ est irrationnel, c'est-à-dire qu'il ne s'écrit pas sous la forme d'un quotient 
d'entiers $\dfrac{p}{q}$ avec $p \in \Z$ et $q \in \Z^*$.
\end{exoi}


\pagebreak
\section{Un nouveau raisonnement : La récurrence}

\subsection{Exemple introductif}
Considérons la suite $(u_n)$ définie pour tout $n\in\N$ par :
$$\left\{ \begin{array}{l} u_0=0 \\ u_{n+1}=2u_n +1  \end{array} \right.$$
Cette suite est définie par récurrence (chaque terme se calcule à partir du précédent). \\
\underline{But} : On souhaiterait obtenir une formule explicite de $u_n$ en fonction de $n$. La suite n'est ni géométrique, ni arithmétique, et la formule ne semble pas évidente, par conséquent on va calculer les premiers termes pour se faire une idée. 
\begin{eqnarray*}
& u_0=1\\
& u_1=2\times 1+1=3\\
& u_2= 2\times 3 + 1=7\\
& u_3=2\times 7+1=15\\
& u_4=2\times 15+1=31\\
& u_5=2\times 31+1=63\\ 
\end{eqnarray*}
Bien, en observant les premiers termes de cette suite il semble logique que $u_6=127$, en effet en ajoutant $1$ à chaque terme on obtient les puissances successive de $2$. Autrement dit il \textbf{semble} que $$u_n=2^n-1 \forall n\in\N$$
Attention, une conjecture n'est pas une preuve (ni une affirmation forcément vraie, certaines conjectures se 
révèlent parfois fausses...). Ce n'est que l'énoncé d'une propriété résultant d'un certain nombre d'observations. 
\textbf{Alors comment confirmer, par une démonstration, la propriété conjecturée ci-dessus ? }\\
Notons $\mathscr P(n)$ la propriété définie pour $n\in\N$, par :
$$ \mathscr P(n):u_n=2^n-1$$
Supposons un instant, que pour un certain entier $n$, on ait effectivement la propriété $ \mathscr P(n):u_n=2^n-1$\\
Dans ce cas on aurait : $u_{n+1}=2\times u_n+1=2\times(2^n-1)+1=2^{n+1}-2+1=2^{n+1}-1$
\\Autrement dit si $\mathscr P(n)$ est vraie alors $\mathscr P(n+1)$ aussi.\\
On dit que la propriété $\mathscr P$ est \textbf{héréditaire}. \\
Au final on a vu que la propriété $\mathscr P$ était vraie au rang $n=0$, $1$, $2$, $3$, $4$, $5$ et $6$ (on dit que la propriété est\textbf{ initialisée}). Mais comme la propriété $\mathscr P$ est héréditaire elle sera vraie au rang $7$, puis au rang $8$, puis au rang $9$, $\dots$.
Si bien que notre propriété est finalement vraie à tout rang. Nous venons de faire un \textbf{raisonnement par récurrence} :

\subsection{Principe du raisonnement par récurrence et exemples}

\Cadre[Principe du raisonnement par récurrence]{Soit $\mathscr P$ une propriété définie sur $\N$ (ou sur une partie de $\N$)\\
Si :
\begin{itemize}
\item La propriété est \underline{initialisée} à un certain rang $n_0$ (i.e si $\mathscr P(n_0)$ est vraie)
\item La propriété est \underline{héréditaire} à partir du rang $n_0$ (i.e si pour $n\geq n_0$ $\mathscr P(n)\Longrightarrow \mathscr P(n+1)$)
\end{itemize}
Alors : \\
La propriété est vraie à tout rang plus grand que $n_0$.}

\Expl{
Compléter la démonstration par récurrence suivante, afin de 
montrer que la somme des $n$ premiers entiers non nuls vaut $\dfrac{n(n+1)}{2}$.\\
Pour tout $n \geq \dots$, on note $\mathscr P(n)$ la proposition \og \\
\begin{itemize}
 \item \textbf{Initialisation :} pour $n=$\\
La somme des $n$ premiers entiers non nuls vaut \\
Et $\dfrac{n(n+1)}{2} = $\\\\
Donc $\mathscr P(\dots)$ est vraie.\\
\item \textbf{Hérédité :} On suppose qu'il existe un entier $k \geq \dots $ tel que $\mathscr P(k)$ est vraie,
ie tel que l'on a \\\\
On cherche à montrer $\mathscr P(k+1)$ :  \og \\\\
$\begin{array}{llcr}
\text{Or }& 1+2+3+ \dots + \dots + (k+1) & = & \\\\
&& = & \\\\
&& = &
\end{array}$\\
Donc $\mathscr P(\dots\dots)$ est vraie. La proposition est \\
 \item \textbf{Conclusion}
La proposition est $\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots$ et $\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots$.\\
Elle est donc vraie pour tout $n \geq $
\end{itemize}
}


\Expl{
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 3$.
}

\Sol{Pour tout $n \geq 0$, on note $\mathscr P(n)$ la proposition \og $0 \leq u_n \leq 3$ \fg 
\begin{itemize}
 \item \textbf{Initialisation :} pour $n=0$\\
$u_0=0$ et on a bien $0\leq 0 \leq 3$\\
Donc $0\leq u_0 \leq 3$ et $\mathscr P(0)$ est vraie.\\
\item \textbf{Hérédité :} On suppose qu'il existe un entier $k \geq 0$ tel que $\mathscr P(k)$ est 
vraie, ie tel que l'on a $0 \leq u_k \leq 3$\\
On cherche à montrer $\mathscr P(k+1)$ :  \og $0 \leq u_{k+1} \leq 3$ \fg ou encore $0 \leq \sqrt{u_k+6} \leq 3$
\begin{eqnarray*}
\text{Or }  0  \leq  u_{k}  \leq  3  & \iff &  6  \leq  u_k+6  \leq  9 \\
& \iff &  \sqrt{6}  \leq  \sqrt{u_k + 6}  \leq  \sqrt{9} \quad \text{ car la fonction racine carré conserve l'ordre sur les positifs} \\
& \iff & 0  \leq  u_{k+1}  \leq  3
\end{eqnarray*}
Donc $\mathscr P(k+1)$ est vraie. La proposition est héréditaire.\\
 \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 $
\end{itemize}
}

\subsection{Démonstration mathématique du principe de raisonnement par récurrence \textit{(Hors Programme)}}
\Thc{Soit $\mathscr P$ une propriété définie sur $\N$. Si :
\begin{itemize}
\item $\mathscr P(0)$ est vraie \hfill (Initialisation)
\item $\forall n\in\N$, on a $\mathscr P(n)$ vraie $\Longrightarrow \mathscr P(n+1)$ vraie \hfill (Hérédité)
\end{itemize}
Alors $\mathscr P(n)$ est vraie $\forall n\in\N$
}

\Dem{Raisonnons par l'absurde et supposons qu'il existe $n\in\N$ tel que $\mathscr P(n)$ soit fausse et considérons l'ensemble suivant :
$$ E=\{n\in\N \text{ tels que } \mathscr P(n) \text{ soit fausse }\}$$
$E$ est donc un ensemble non vide et minorée par $0$, par conséquent il admet un plus petit élément $m\geq 0$ ; on a donc $\mathscr P(m)$ fausse et$\mathscr P(n)$ vraie $\forall n \text{tel que} 0\leq n \leq m$. Dans ce cas :
\begin{itemize}
\item Si $m=0$, alors on a $\mathscr P(0)$ fausse ce qui contredit la première hypothèse du théorème.
\item Si $m>0$, alors on a $\mathscr P(m-1)$ vraie et $\mathscr P(m)$ fausse, ce qui contredit la deuxième hypothèse du théorème.
\end{itemize}
Donc $E$ est vide, autrement dit $\mathscr P(n)$ est vraie pour tout $n\in\N$}

\Rq{La démonstration est analogue pour une propriété définie sur un intervalle du type \textlbrackdbl $ n_0,+\infty  [$}





\pagebreak


\subsection{Des exercices d'entrainement}
\begin{exoi}
 On donne ci-dessous trois propositions vraies. 
\begin{enumerate}
 \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{enumerate}
Pour lesquelles peut-on envisager une démonstration par récurrence (que l'on ne fera pas) ?
\end{exoi}

\begin{exoi}
 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{exoi}



\begin{exoi}
 On considère la suite $u$ définie sur $\N$ 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{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}
\end{exoi}

\begin{exoi}
 \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{exoi}




\begin{exoi}
On s'intéresse désormais à la somme $S_n$ des cubes des $n$ premiers entiers naturels impairs.
\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=2n^4-n^2$$
\item Quel est l'entier $n$ pour lequel $S_n=41328$ ?
\end{enumerate} 

\end{exoi}


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

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


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

\begin{exoi}
 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{exoi}

\begin{exoi}
\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{exoi}
\pagebreak

\subsection{Exercices corrigés }
\begin{exoi}Démontrer que $$\sum\limits_{k=0}^{n} k^2=\dfrac{n(n+1)(2n+1)}{6}$$
\end{exoi}

\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{exoi}Considérons la suite $(u_n)$, définie pour tout $n\in\N$, par : 
$$\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$ : $$ u_n=2^n$$
\end{exoi}

\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{exoi}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{exoi}

\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$$
CQFD
\end{itemize}}
\begin{exoi}On considère la suite $(u_n)$ définie par $u_0=0$ et pour tout entier naturel $n$ : $$ 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{exoi}

\Sol{\begin{itemize}
\item \textbf{Initialisation} : $u_1=\sqrt{\dfrac{1}{2} }=\dfrac{1}{ \sqrt{2} }$, donc : 
$$ \dfrac{1}{ \sqrt{2} }\leq u_1 \leq 1$$
\item \textbf{Hérédité} : Supposons que, pour un entier $n\geq 1$ on ait $$ \dfrac{1}{\sqrt{2} }\leq u_n\leq 1$$
Montrons que $ \dfrac{1}{\sqrt{2} }\leq u_{n+1}\leq 1$, pour cela considérons la fonction $f$ définie sur $I=[0;+\infty[$ par $$ f(x)=\sqrt{\dfrac{1+x}{2} }$$
On a $ u_{n+1}=f(u_n)$, de plus la fonction $f$ est dérivable sur $I$ et $$ f'(x)= \dfrac{\frac{1}{2} }{2 \sqrt{\dfrac{1+x}{2} } }=\dfrac{1}{4}\sqrt{\dfrac{2}{1+x} }>0$$
Par conséquent $f$ est une fonction strictement croissante sur $I$. On en déduit alors :
$$ \dfrac{1}{ \sqrt{2} }\leq u_1 \leq 1 \Longrightarrow f\left(\dfrac{1}{ \sqrt{2} }\right)\leq u_{n+1} \leq f(1)$$
Or, $f\left(\dfrac{1}{\sqrt{2}}\right)>\dfrac{1}{\sqrt{2} }$ et $f(1)=1$, donc $$  \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}
