\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}%applemac->latin1 sur pc! 
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,numprint}
\usepackage[dvips]{color}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,bclogo}
\usepackage{pst-eucl}
\usepackage{pstricks-add}
\usepackage{bclogo}
\usepackage{tikz}
\usepackage[francais]{babel}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\everymath{\displaystyle}
\textwidth 19,5cm \textheight 25cm \hoffset 
-1,7cm \voffset -4cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{blue}{\Roman{subsection}}} 
\pagestyle{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}

\begin{center}\section*{\textcolor{blue}{Démonstration par récurrence}}\end{center}

\textbf{\textcolor{red}{Exemples introductif :}}\\
Imaginons que des ouvriers construisant un immeuble aient toutes les instructions nécessaires pour construire un étage d'immeuble sur le mÍme modèle que l'étage qui est au-dessous.\\
Ainsi peuvent-ils construire le deuxième (identique au premier), le troisième (identique au deuxième), le quatrième (identique au troisième) et ainsi de suite ; on peut imaginer qu'ils peuvent alors construire un immeuble aussi haut que l'on veut (en négligeant les contraintes de résistance des matériaux qui limitent les hauteurs d'immeubles).\\

\noindent Le seul problème est qu'il faut \textbf{d'abord avoir construit indépendamment} le premier étage, car on ne peut pas prendre pour modèle un étage  précédent, puisqu'il n'y en a pas !\\

\noindent Autre exemple : faire tomber des dominos en cascade. Il faut d'abord faire tomber le premier domino et ensuite, la chute d'un domino entraine la chute du suivant.\\

\begin{center}
\section*{\textcolor{red}{\fbox{Principe d'une démonstration par récurrence :}}}
\end{center}

Ce principe est basé sur la description de l'ensemble $\mathbb{N}$ des entiers naturels :\\
$\bullet$ Il existe un plus petit entier, 0.\\
$\bullet$ Chaque entier autre que 0 s'obtient en ajoutant 1 à son prédécesseur.\\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{Axiome de récurrence :}
Si une propriété est vraie pour l'entier naturel $n_{0}$ et s'il est prouvé que, lorsqu'elle est vraie pour un entier $p$ quelconque supérieur ou égal à $n_{0}$, alors elle est vraie pour $p+1$, alors elle est vraie pour tout entier $n\geqslant n_{0}$.
\end{bclogo}

\bigskip

\textbf{\textcolor{red}{Exemple rédigé de la démonstration d'une propriété:}}\\

\noindent Soit $\mathscr{H}_n$ une proposition qui dépend d'un entier $n$ naturel. On veut montrer que cette proposition $\mathscr{H}_n$ est vraie pour tout $n\geq n_0$ .\\
\textbf{ \textcolor{blue}{On suit la méthode suivante :}}\\
$\bullet$ On vérifie que $\mathscr{H}_{n_0}$ est vraie. (amorÁage de la récurrence ou initialisation).\\

\noindent $\bullet$ On démontre que la propriété est héréditaire, c'est-à-dire que si l'on suppose que $\mathscr{H}_n$ est vraie à un rang $n\geq n_0$ (hypothèse de récurrence), alors $\mathscr{H}_{n + 1}$ est vraie .\\
Alors, on en déduit que $\mathscr{H}_n$ est vraie pour tout $n \geq n_0$.\\

\textbf{\textcolor{red}{Exemple :}}\\
Soit la suite $\left(u_{n}\right)$ définie par : $u_{0}=3$ et $u_{n+1}=5u_{n}-4$ pour tout $n\in\mathbb{N}$.\\
Démontrer que, pour tout $n\in\mathbb{N}$, $u_{n}=2\times 5^n+1$ .\\

\textbf{\textcolor{red}{Rédaction}}\\
 Notons $\mathscr{H}_n$ l'affirmation :  $u_{n}=2\times 5^n+1$.\\
 
 Effectuons une d\textbf{émonstration par récurrence} :
\begin{enumerate}[$\bullet$]
\item Amor\c cage :  $n = 0$ : $2\times 5^0+1=2\times 1+1=3=u_{0}$ : $\mathscr{H}(0)$ est vraie.

\item Hérédité : On suppose que $\mathscr{H}(n)$ est vraie poiur un entier $n$ quelconque, donc que $u_{n}=2\times 5^n+1$. (hypothèse de récurrence).\\
Il faut alors montrer que $\mathscr{H}_{n+1}$ est vraie.\\

\noindent  On a : $u_{n+1}=5u_{n}-4=5\left(2\times 5^n+1\right)-4=2\times 5^{n+1}+5-4=2\times 5^{n+1}+1$. donc  $\mathscr{H}_{n+1}$ est vraie.
\end{enumerate}

\noindent \textbf{\textcolor{blue}{Conclusion :}} D'après l'axiome de récurrence,  la propriété $\mathscr{H}_n$ est vraie pour tout $n\in\mathbb{N}$. \\

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcdanger]{\textcolor{red}{Remarque}}
Les deux étapes de la démonstration par récurrence sont indispensables ! 
\end{bclogo}

\bigskip

\textbf{Montrons sur deux exemples} que si l'on supprime une étape, la démonstration ne donne rien.\\

\textbf{\textcolor{red}{Exemple 1 :}} (on a l'amor\c cage, mais pas l'hérédité):\\
On appelle nombre de Fermat le nombre $F_{n}=2^{2^n}+1$, ($n\in\mathbb{N}$).\\
Fermat (mathématicien fran\c cais, 1601 - 1665) a affirmé que pour tout $n\in\mathbb{N}$, $F_{n}$ est premier.\\
Effectivement : $F_{0}=3$ est premier ; $F_{1}=5$ est premier ; $F_{2}=17$ est premier ; $F_{3} = 257$ est premier et $F_{4} = \numprint{65537}$ est premier.\\
Comme on ne peut pas montrer que la propriété est héréditaire, on ne peut pas effectuer de démonstration par récurrence et donc pas en déduire que la propriété est vraie pour tout $n$.\\

\noindent D'ailleurs $F_{5}=\numprint{4294967297}=641\times \numprint{6700417}$ n'est pas premier, ce que Fermat n'avait pas trouvé (mais trouvé par Euler).\\
En fait, les nombres de Fermat pour $5\leqslant n\leqslant 32$ ne sont pas premiers. On ne sait pas si $F_{33}$ est premier ou non.\\
On a bien l'initialisation, mais pas l'hérédité.\\

\textbf{Pour plus de renseignements sur les nombres de Fermat}, cliquer \href{http://fr.wikipedia.org/wiki/Nombre_de_Fermat}{ici} ou \href{http://villemin.gerard.free.fr/Wwwgvmm/Decompos/Fermat.htm}{ici}\\

\noindent \textbf{\textcolor{red}{Exemple 2 :}} \\
Soit $P_n$ la propriété : \og 6 divise $7^n+1$ \fg\\
Cette propriété est \textbf{\textcolor{blue}{héréditaire}} à partir de $n=0$.\\
\textbf{En effet :} Supposons $P_n$ vraie donc il existe $k_{n}$  tel que $7^n+1=6k_{n}$, $k_{n}\in\mathbb{Z}}$.\\
Alors $7^{n+1}=7\times 7^n+1=7(6k_{n}-1)+1=42k_{n}-6=6(7k_{n}-1)=6k_{n+1}$ avec $k_{n+1}=7k_{n}-1\in\mathbb{Z}$ donc $P_{n+1}$ est vraie aussi.\\
$P_{n+1}$ est donc toujours vraie lorsque $P_n$ l'est.\\
$P_{n}$ est une propriété \textbf{\textcolor{red}{héréditaire}}.\\

On ne peut pas conclure par une démonstration par récurrence, car nous n'avons pas montré l'initialisation.
\textbf{Or $\mathbf{P_0}$ est faux !}. \\
On ne sait donc pas si la propriété est vraie pour d'autres valeurs enti\ères de $n$ autres que 0.\\

En fait, la propriété est fausse pour toutes les valeurs entières de $n$ ! (facile à montrer en spécialité avec les congruences).\\
  
  \textbf{\textcolor{blue}{Exercices du livre \no 15  ; 16 ; 17 ; 18 ; 19 ; 20 ; 24 page 53}}

%\newpage
%\textbf{\textcolor{red}{Exercices :}}
%\begin{enumerate}
%
%%\item Soit $z$ un nombre complexe. Montrer que, pour tout $n\geqslant 1$, $\left|z^n\right|=|z|^n$.
%
%\item Soit la suite $\left(u_{n}\right)$ définie par : $u_{0}=0$ et, pour tout $n\in\mathbb{N}$, $u_{n+1}=3+2u_{n}$.\\
%Montrer que, pour tout $n$, $u_{n}\geqslant 0$.
%
%\item   On considère la suite $(u_n)$ définie par : $u_0 = 4$ et pour tout $n \geq 1$, $u_{n+1}=\frac14u_n+6$. Montrer que, pour tout n, on a :  $u_n=-\left(\frac14\right)^{n-1}+8$.
%
%\item Montrer que, pour tout entier naturel $n$, l'entier $3^{2n}-2^n$ est un multiple de 7.
%\end{enumerate}
%
%
%\textbf{\textcolor{blue}{Correction}}
%\begin{enumerate}
%
%\item Notons $H_{n}$ l'affirmation : $u_{n}\geqslant 0$. Effectuons une démonstration par récurrence.
%\begin{enumerate}[$\bullet$]
%\item Initialisation : $0\geqslant 0$ donc $u_{0}\geqslant 0$ : $H_{0}$ est vraie.
%
%\item Hérédité : on suppose que $H_{n}$ est vraie pour un rang $n$ quelconque.\\
%$u_{n}\geqslant 0\Rightarrow 2u_{n}\geqslant 0\Rightarrow3+2u_{n}\geqslant 3\geqslant 0$ donc $u_{n+1}\geqslant 0$ : $H_{n+1}$ est donc vraie.
%\end{enumerate}
%D'après l'axiome de récurrence, $u_{n}\geqslant 0$ pour tout $n\in\mathbb{N}$.
%
%\item $\left(u_{n}\right)$ est définie par $u_{0}=4$ et $u_{n+1}=\dfrac{1}{4}u_{n}+6$. Démontrons par récurrence sur $n$ que $u_{n}=-\left(\dfrac{1}{4}\right)^{n-1}+8$.\\
%Notons $\left(\mathscr{H}_{n}\right)$ l'affirmation : $u_{n}=-\left(\dfrac{1}{4}\right)^{n-1}+8$.
%\begin{enumerate}[$\bullet$]
%\item Initialisation : pour $n=0$, $-\left(\dfrac{1}{4}\right)^{n-1}+8=-\left(\dfrac{1}{4}\right)^{-1}+8=-4+8=4=u_{0}$.
%
%\item Hérédité : on suppose que $\left(\mathscr{H}_{n}\right)$ est vraie pour un rang $n$ quelconque. Par conséquent : $u_{n}=-\left(\dfrac{1}{4}^{n+1}\right)+8$.\\
%Alors : $u_{n+1}=\dfrac{1}{4}u_{n}+6$ (par définition de $\left(u_{n}\right)$)\\
%$=\dfrac{1}{4}\times \left[-\left(\dfrac{1}{4}\right)^{n-1}+8\right]+6$ (puisque $\left(\mathscr{H}_{n}\right)$ est supposée vraie)\\
%$=-\left(\dfrac{1}{4}\right)^n+2+6=-\left(\dfrac{1}{4}\right)^n+8$ donc $(\mathscr{H}_{n+1})$ est vraie.
%\end{enumerate}
%D'après l'axiome de récurrence, la propriété est vraie pour tout $n$ : $\boxed{\forall n\in\mathbb{N},~u_{n}=-\left(\dfrac{1}{4}\right)^{n-1}+8}$.
%
%\item Notons $H_{n}$ l'affirmation $3^{2n}-2^n$ est un multiple de 7 et effectuons une démonstration par récurrence.
%\begin{enumerate}[$\bullet$]
%\item Initialisation :Pour $n=0$ : $3^{2\times 0}-2^0=1-1=0$ qui est un multiple de 7 : $H_{0}$ est vraie.
%
%\item Hérédité : supposons que $H_{n}$ soit vraie pour un entier $n$ quelconque. $3^{2n}-2^n$ est un multiple de 7, donc il existe un entier relatif $k_{n}$ tel que : $3^{2n}-2^n=7k_{n}$.\\
%Alors : $3^{2(n+1)}-2^{n+1}=3^{2n+2}-2^{n+1}=3^2\times 3^{2n}-2\times 2^n=(7+2)\times 3^{2n}-2\times 2^n=7\times 3^{2n}+\left[2\times 3^{2n}-2\times 2^n\right]=7\times 3^{2n}+2\left[3^{2n}-2^n\right]=7\times 3^{2n}-2\times 7k_{n}=7\left(3^{2n}-2k_{n}\right)=7k_{n+1}$ en posant $k_{n+1}=3^{2n}-2k_{n}$ qui est un entier relatif (produit et différence d'entiers).
%\end{enumerate}
%D'après l'axiome de récurrence, la propriété est démontrée pour tout $n$.
%\end{enumerate}
%\vspace{0,5cm}

\label{fin}
\end{document} 



