\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint}
\usepackage[dvips]{color}
\usepackage{bclogo}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
%\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\textwidth 19cm \textheight 26cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{blue}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{empty}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
%\tableofcontents

\begin{center}\section*{\textcolor{red}{Correction des exercices de démonstrations par récurrence}}\end{center}




\subsection{}%http://www.lyc-cassin-gonesse.ac-versailles.fr/IMG/pdf/all_suites.pdf
On définit, pour tout entier $n\geqslant 1$, le $n\ieme$ nombre triangulaire par $t_n = 1 + 2 +\cdots+ n =\dfrac{n(n+1)}{2}$.

Démontrer que, pour entier $n\geqslant 1$, on a : \[\sum_{k=1}^nt_k =\dfrac{n(n + 1)(n + 2)}{6}.\]
On note $P_n$ la propriété : \og{}$\sum_{k=1}^nt_k =\dfrac{n(n + 1)(n + 2)}{6}$\fg{}, pour $n\geqslant 1$

Démontrons-la par récurrence 
\begin{enumerate}[$\bullet$]
\item Initialisation : Pour $n=1$, $\dfrac{n(n+1)(n+2)}{6}=\dfrac{1\times 2\times 3}{6}=1$ et $t_1=1$ donc la propriété est vraie pour $n=1$.

\item Hérédité : on suppose $\mathscr{P}_n$ vraie pour un rentier $n$ quelconque, donc $\sum_{k=1}^nt_k =\dfrac{n(n + 1)(n + 2)}{6}$.

Alors : $\sum_{k=1}^{n+1}t_k =\sum_{k=1}^{n}t_k+t_{n+1}=\dfrac{n(n+1)(n+2)}{6}+\dfrac{(n+1)(n+2)}{2}=\dfrac{n(n+1)(n+2)}{6}+\dfrac{3(n+1)(n+2)}{6}\\
=\dfrac{(n+1)(n+2)[n+3]}{6}=\dfrac{(n+1)[(n+1)+1][(n+1)+2]}{6}$, c.q.f.d.

La propriété est héréditaire.
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.

\subsection{}
Démontrer par récurrence que pour tout entier $n\geqslant 1$ , on a :

\[S_n=\dfrac{1}{1\times 2}+\dfrac{1}{2\times 3}+\dfrac{1}{3\times 4}+\cdots+\dfrac{1}{n(n+1)}=1-\dfrac{1}{n+1}\]

\begin{enumerate}[$\bullet$]
\item Initialisation : Pour $n=1$, $S_1=\dfrac{1}{2} et 1-\dfrac{1}{n+1}=1-\dfrac{1}{2}=\dfrac{1}{2}$ donc la propriété est vraie pour n=1.

\item Hérédité : on suppose la propriété vraie pour un rang $n$ quelconque, donc $S_n=1-\dfrac{1}{n+1}$.

Alors : $S_{n+1}=S_n+\dfrac{1}{(n+1)(n+2)}=1-\dfrac{1}{n+1}+\dfrac{1}{(n+1)(n+2)}=1-\dfrac{(n+2)-1}{(n+1)(n+2)}=1-\dfrac{n+1}{(n+1)(n+2)}=1-\dfrac{1}{n+2}$ c/q.f.d.

La propriété est héréditaire
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.

\subsection{}
La suite de Fibonacci est la suite $\left(F_{n}\right)_{n\in\mathbb{N}}$ définie par $F_{1}=F_{2}=1$ et, pour tout entier naturel $n$ non nul, \[F_{n+2}=F_{n+1}+F_{n}.\]
Démontrer par récurrence sur $n$ que, pour tout entier naturel $n$ non nul : \[F_{1}^2+F_{2}^2+\cdots+F_{n}^2=F_{n}\times F_{n+1}.\]

\begin{enumerate}[$\bullet$]
\item Initialisation : 
Pour $n=1$, $F_1^2=1^2=1$ et $F_1F_2=1\times 1=1$ donc $F_1^2=F_1\times F_2$ ; la propriété est vraie pour $n=1$.

\item Hérédité : on suppose la propriété vraie pour un rang $n$ quelconque, donc $F_1^2+\cdots+F_n^2=F_n\times F_{n+1}$.

Au rang $n+1$ :

$F_1^2+F_2^2+\cdots+F_n^2+F_{n+1}^2=\left[F_1^2+F_2^2+\cdots+F_n^2\right]+F_{n+1}^2=F_n\times F_{n+1}+F_{n+1}^2=F_n\times F_{n+1}+F_{n+1}^2=F_{n+1}\left[F_n+F_{n+1}\right]=\boxed{\textcolor{red}{F_{n+1}\times F_{n+2}}}$.

La propriété est héréditaire
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.


\subsection{}
Démontrer que, pour tout entier naturel n, l’entier $3^{2n}-2^n$ est un multiple de 7.

Soit $\mathscr{P}_n$ la propriété : $\og{}3^{2n}-2^n=7k_n$\fg{}, $k_n\in\mathbb{Z}$.

Effectuons une démonstration par récurrence :
\begin{enumerate}[$\bullet$]
\item Initialisation : Pour $n=0$, $3^0-2^0=1-1=0=7\times 0=7\times k_0$ avec $k_0=0\in\mathbb{Z}$. La propriété est vraie pour $n=0$

\item Hérédité :  on suppose la propriété vraie pour un rang $n$ quelconque, donc $3^{2n}-2^n=7k_n$, $k_n\in\mathbb{Z}$, donc $3^{2n}=2^n+7k_n$

Alors, au rang $n+1$ : 

$3^{2(n+1)}-2^{n+1}=3^{2n}\times 3^2-2^{n+1}=9\times 3^{2n}-2^{n+1}=9\times \left(2^n+7k_n\right)-2\times 2^n=(9-2)\times 2^n+9\times 7k_n=7\times 2^n+9\times 7k_n=7\left(2^n+k_n\right)=7\times k_{n+1}$ en posant $k_{n+1}=2^n+k_n\in\mathbb{Z}$.

La propriété est héréditaire
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.


\subsection{}
On considère la suite $\left(u_n\right)$ définie par $u_0 = 0$ et pour tout $n\in\mathbb{N}$ : $u_{n+1}=\sqrt{\dfrac{1+u_n}{2}}$.

Montrer, par récurrence, que pour tout $n\geqslant 1$ on a : \[\dfrac{1}{\sqrt{2}}\leqslant u_n\leqslant 1\]

Effectuons une démonstration par récurrence :
\begin{enumerate}[$\bullet$]
\item Initialisation :Pour $n=1$ : $u_1=\sqrt{\dfrac{1}{2}}=\dfrac{1}{\sqrt{2}}$ donc la proprété est vraie pour $n=1$.

\item Hérédité :  on suppose la propriété vraie pour un rang $n$ quelconque, donc $\dfrac{1}{\sqrt{2}}\leqslant u_n\leqslant 1$.

Alors : $\dfrac{1}{\sqrt{2}}\leqslant u_n\leqslant 1^2\Rightarrow 1+\dfrac{1}{\sqrt{2}}\leqslant 1+u_n\leqslant 2\Rightarrow\dfrac{1}{2}+\dfrac{2}{2\sqrt{2}}\Rightarrow \dfrac{+u_n}{2}\leqslant 1\Rightarrow \dfrac{1}{2}\leqslant \dfrac{+u_n}{2}\leqslant 1$ (car $\dfrac{1}{2}\leqslant \dfrac{1}{2}+\dfrac{1}{2\sqrt{2}}$).

D'où, puisque la fonction $x÷mapsto\sqrt{x}$ est croissante :

$\dfrac{1}{\sqrt{2}}\Rightarrow \sqrt{\dfrac{1+u_n}{2}=u_{n+1}}\leqslant \sqrt{1}=1$ c.q.f.d

La propriété est héréditaire
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.

\subsection{}
Soit $f$  la fonction définie par $f(x)=\dfrac{1}{1-x}$  pour tout $x\neq1$.

Démontrer que, pour tout entier $n\geqslant 1$,  \[f^{(n)}(x)=\dfrac{n!}{(1-x)^{n+1}}\]  où $f^{(n)}$  désigne la dérivée n-ième  de $f$  et 

$n!=1\times 2\times 3\times \cdots\times n$

On corrigera cet exercice dans le chapitre sur la dérivation.

\subsection{}
Soit $\left(u_n\right)$ la suite définie par $u_0=2$ et, pour tout $n\in\mathbb{N}$, $u_{n+1}=2u_n-n$.

Démontrer que, pour tout $n$, $u_{n}=2^n+n+1$.

Démonstration par récurrence :
\begin{enumerate}[$\bullet$]
\item Iniialisation : Pour $n=0$ : $u_0=2$ et $2^n+n+1=2^0+0+1=1+1=2$ donc la propriété est vraie pour $n=0$.

\item Hérédité : on suppose la propriété vraie pour un rang $n$ quelconque donc $u_{n}=2^n+n+1$.

Au rang $n+1$ : $u_{n+1}=2u_n-n=2\times \left(2^n+n+1\right)-=2^{n+1}+2n+2-n=2^n+1}+n+2$ c.q.f.d.
La propriété est héréditaire
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.


\subsection{}
Montrer que la suite $\left(u_n\right)$ définie par $u_0=1$, $u_1=1$ et, pour tout $n\in\mathbb{N}$ , par $u_{n+2}=2u_{n+1}-u_n-2$ est monotone.

Montrons que la suite est décroissante.

Montrons que $u_{n+1}-u_n\leqslant 0$ pour tout $n$.

\begin{enumerate}[$\bullet$]
\item initialisation : $u_0=u_1=1$ donc c'est vrai pour $n=0$

\item Hérédité : on suppose que $u_{n+1}-u_n\leqslant 0$ pour un entier $n$ quelconque.

Au rang $n+1$ :

$u_{n+2}-u_{n+1}=\left[2u_{n+1}-u_n-2\right]-u_{n+1}=u_{n+1}-u_n-2=\underbrace{\left[u_{n+1}-u_n\right]}_{\leqslant 0}-2\leqslant 0$.

La propriété est héréditaire.
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.


\subsection{}
Montrer que, pour tout entier $ n\geqslant$ 1 ,    \[\sum_{k=1}^n k\times k!=(n+1)!-1\] .

\begin{enumerate}[$\bullet$]
\item initialisation : $\sum_{k=1}^1 k\times k!=1\times 1!=1\times 1=1$ et $(1+1)!-1=2!-1=2-1=1$.

La propriété est vraie pour $n=1$?

\item Hérédité : on suppose que $\sum_{k=1}^n k\times k!=(n+1)!-1$ pour un entier $n$ quelconque.

Au rang $n+1$ : $\sum_{k=1}^{n+1} k\times k!=\sum_{k=1}^n k\times k!+(n+1)(n+1)!=(n+1)!-1+(n+1)(n+1)!=(n+1)!\left[(n+1)+1\right]=1=(n+1)!\times (n+2)-1=(n+2)!-1$. c.q.f.d
La propriété est héréditaire.
\end{enumerate}
D'après l'axiome de récurrence, a propriété est vraie pour tout $n\geqslant 1$.
.
\label{fin}
\end{document}  