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

\newcommand{\ch}{Chapitre 1}
\newcommand{\Ch}{Divers Raisonnements \linebreak Math\'ematiques}
\newcommand{\Cl}{TS}
\newcommand{\Annee}{2012-2013}
	

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

\input macro_final.tex


\geometry{tmargin=2cm,bmargin=2.4cm,hmargin=2cm}

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

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


\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 qu'un quadrilatère soit un parallélogramme pour être un rectangle 
(mais cela n'est pas suffisant).}
 \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 de 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{ExoF}
\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{ExoF}



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

\Cadre[Problème d'introduction]{
On dispose d'une infinité de dominos, placés \og debouts \fg les uns à la suite des autres et on numérote 
leur position dans l'ordre.\\
On cherche les éventuelles conditions pour être sûr de les faire tous tomber à la chaîne.\\
Pour tout $n\in \N^*$ on note $\mathscr P(n)$ la propriété (dépendant de $n$) 
$$\mathscr P(n) : \og \text{ le } n^{\text{ième}} \text{ domino tombe. } \fg $$
\begin{enumerate}
 \item A quelle(s) condition(s) $\mathscr P(1)$ est-elle vraie ?
 \item Même question pour $\mathscr P(2)$, $\mathscr P(3)$, $\mathscr P(4)$, puis $\mathscr P(10)$ et 
enfin $\mathscr P(65\,468)$.
 %\item Même question pour $\mathscr P(k)$.
 \item A quelle(s) condition(s) $\mathscr P(n)$ est-elle vraie pour tout $n\in\N^*$ ?
\end{enumerate}
}

%\textit{Pour l'enseignant : amener des dominos et les disposer dans divers cas de figure.}\\

\Act{
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.$$
Chaque terme de cette suite se calcule à partir du précédent. On dit que cette suite est définie 
\textbf{par récurrence}. \\\\
\underline{But} : \textit{On souhaiterait pouvoir calculer 
n'importe quel terme sans avoir à calculer chacun des précédents, ie 
conjecturer une formule \textbf{explicite} de $u_n$ en fonction de $n$ et la démontrer pour tout $n\in\N$.}\\
\begin{enumerate}
 \item Pour quel type de suites définies par récurrence connaissez-vous des formules explicites ?\\
La suite $(u_n)$ est-elle de l'un de ces types ? \textit{Justifier}
 \item Calculer à la main les premiers termes de la suite jusqu'à $u_5$.
 \item Etablir à la calculatrice le tableau de valeurs de $(u_n)$ et vérifier vos résultats.
 \item La plupart des calculatrices n'affichent pas dans leur tableau une valeur exacte à partir de $u_{20}$.\\
Grâce aux premières lignes de ce tableau, conjecturer la valeur exacte de $u_{33}$ et $u_{34}$.
\item Ces résultats sont-ils certains ? Que faudrait-il faire pour les vérifier ?
\item Quelqu'un a eu le courage de se lancer dans cette vérification et a trouvé 
$u_{33}=\nombre{8589934591}$, mais pour $u_{34}$, sa calculatrice ne donne qu'une valeur approchée. \\
Vérifier à la calculatrice votre conjecture pour $u_{33}$, puis, sans calculatrice, vérifier
votre conjecture sur $u_{34}$.
\item Conjecturer une formule explicite pour calculer $u_n$. Ce résultat est-il certain pour tout $n\in\N$ ?
 \item Notons $\mathscr P(n)$ la proposition définie pour $n\in\N$, par : $ \mathscr P(n) : \og u_n=\dots\dots\dots\dots\dots\dots \fg$\\
Mettre en place un raisonnement analogue à celui des dominos pour démontrer que $\mathscr P(n)$ est vraie 
pour tout $n\in\N$. 
\end{enumerate}
\Cadre[Conclusion]{
 Vous venez de faire un \textbf{raisonnement par récurrence}. De telles démonstrations servent à prouver 
qu'une proposition est vraie ou fausse pour tout entier à partir d'un certain rang. 
Il faut donc avoir à démontrer quelquechose du genre :\\
\og Démontrer que pour tout entier naturel $n\geq n_0$, la propriété $\mathscr P(n)$ est vraie \fg
}
}

\textit{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é \textbf{supposée} résultant d'un certain nombre d'observations. }\\


\Cadre[Principe et rédaction du raisonnement par récurrence]{
Soit $\mathscr P(n)$ une proposition dépendant d'un entier naturel $n$ et $n_0$ un entier naturel fixé. 
Pour démontrer 
que $\mathscr P(n)$ est vraie pour tout entier $n\geq n_0$, on procède en trois étapes.
\begin{itemize}
 \item \textbf{Initialisation de la propriété}\\
On vérifie que la proposition est vraie pour l'entier $n_0$\\
\textit{Lorsqu'il s'agit d'une égalité à vérifier, on calcule séparément les deux membres de l'égalité, puis on les compare}
 \item \textbf{Hérédité} 
\begin{itemize}
 \item On suppose qu'il existe (au moins) un entier $k \geq n_0$ tel que la proposition $\mathscr P(k)$
est vraie (c'est l'hypothèse de récurrence).
 \item Eventuellement on énonce $\mathscr P(k)$ et $\mathscr P(k+1)$ (conseillé)
 \item On démontre que $\mathscr P(k)$ vraie entraine $\mathscr P(k+1)$ vraie aussi.\\
\textit{Lorsqu'il s'agit d'une égalité à démontrer, on part d'un membre, on transforme son écriture grâce 
à l'hypothèse de récurrence (on précise l'endroit où on l'utilise) et on retrouve l'autre membre.}
\end{itemize}
 \item \textbf{Conclusion} \\
 On peut alors conclure que la propriété $\mathscr P(n)$ est vraie pour tout entier $n\geq n_0$.
\end{itemize}
}

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

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

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

\begin{ExoF}
 On donne ci-dessous trois propositions vraies. 
\begin{enumerate}
 \item Pour tout entier $n\geq 4$, $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{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}
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{ExoF}

\begin{ExoF}
 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{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}
\begin{enumerate}
 \item Montrer que pour tout $n\in\N$  on a $\sum_{k=1}^n k^2=\dfrac{n(n+1)(2n+1)}{6}$
\item 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{enumerate}
\end{ExoF}


\begin{ExoF}
 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$ et $f_n'(x)=nx^{n-1}$
\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}




\begin{ExoL}
Déclic : n$^{\circ}$ 29-32 p 32\\

Symbole : \textbf{Algorithme} \og Les tours de Hanoï \fg  p 16
\end{ExoL}


\end{document}
