\documentclass[french,12pt]{article}

\usepackage{a4}
\usepackage[latin1]{inputenc}
\usepackage{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{euscript,latexsym,pifont}
\usepackage{enumerate,theorem}
\usepackage{vmargin, indentfirst, fancyheadings} 
\setpapersize{A4}

\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}

\theoremstyle{break}
\newtheorem{exo}{Exercice}

\begin{document}

\setlength{\headrulewidth}{0pt}
\cfoot{\thepage}
\chead{Mathématiques S1}
\lhead{IMP}
\rhead{2005/2006}
\pagestyle{fancy}

\title{Entiers Naturels}
\author{}
\date{}

\maketitle
\thispagestyle{fancy}

\begin{exo}
Montrer par r\'ecurrence que $(n!)$ est la suite d\'efinie par $\begin{cases} u_{0}=1\\ u_{n+1}=(n+1)u_{n} \end{cases}$
\end{exo}


\begin{exo}
Montrer que pour tout $n\in \N$:
\begin{enumerate}
\item{\em}$3^{2n+1}+2^{n+2}$ est divisible par $7$
\item{\em}$2^{2n}+15n-1$ est divisible par $9$
\end{enumerate}
\end{exo}


\begin{exo}
D\'emontrer, en raisonnant par r\'ecurrence, que $10^{6n+2}+10^{3n+1}+1$ est divisible
par $111$ quel que soit $n\in \N$. (Indication : $1000=9\times 111 +1$ ).
\end{exo}

\begin{exo}
Montrer :
\begin{enumerate}
    \item $\displaystyle{\sum_{k=1}^{n}k=\frac{n(n+1)}{2} \quad \forall n \in \N^{*} \,.}$
    \item $\displaystyle{\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6} \quad \forall n \in \N^{*} \,.}$
    \item $\displaystyle{\sum_{k=1}^{n}k^{3}=\dfrac{n^{2}{(n+1)}^{2}}{4}}$
\end{enumerate}
\end{exo}


\begin{exo}
\begin{enumerate}
 \item $\displaystyle{\sum_{(p,q)\in \N^{2}\mbox{ et } p+q\leq n}^{ } (p+q)}$
 \item $\displaystyle{\sum_{1\leq i<j\leq n} ij}$
 \item $\displaystyle{\sum_{1\leq i\leq n\mbox{ et } 1\leq j\leq n}^{ } \min(i,j)}$
\end{enumerate}
\end{exo}

\newpage

\begin{exo}
\textbf{En quoi le raisonnement suivant est-il faux ?} \\
Soit $\mathcal{P}(n)$ : $n$ crayons de couleurs sont tous de la m\^eme couleur.
\begin{itemize}
    \item $\mathcal{P}(1)$ est vraie car un crayon de couleur est de la m\^eme couleur
que lui-m\^eme.
    \item Supposons $\mathcal{P}(n)$. Soit $n+1$ crayons. On en retire $1$. Les $n$
crayons restants sont de la m\^eme couleur par hypoth\`ese de r\'ecurrence.

Reposons ce crayon et retirons-en un autre ; les $n$ nouveaux crayons sont \`a nouveau
de la m\^eme couleur. Le premier crayon retir\'e \'etait donc bien de la m\^eme couleur que les $n$ autres. La proposition est donc vraie au rang $n+1$.
    \item On a donc d\'emontr\'e que tous les crayons en nombre infini d\'enombrable
sont de la m\^eme couleur.
\end{itemize}
\end{exo}

\begin{exo}
Soit la suite $(x_n)_{n\in \N}$ d\'efinie par
$x_0=4$ et $\displaystyle{x_{n+1}=\frac{2x_n^2-3}{x_n+2}}$.
\begin{enumerate}
    \item Montrer que : $\forall n\in\N\quad x_n>3$.
    \item Montrer que : $\forall n\in\N \quad x_{n+1}-3>\frac{3}{2}(x_n-3)$.
    \item Montrer que : $\forall n\in\N \quad x_n \ge \left(\frac{3}{2}\right)^n+3$.
    \item La suite $(x_n)_{n\in\N}$ est-elle convergente ?
\end{enumerate}
\end{exo}

\begin{exo}
\begin{enumerate}
\item
Dans le plan, on consid\`ere trois droites $\Delta_{1},\Delta_{2},\Delta_{3}$ formant un
``vrai'' triangle : elles ne sont pas concourantes, et il n'y en a pas deux parall\`eles.
Donner le nombre $R_{3}$ de r\'egions (zones blanches) d\'ecoup\'ees par ces trois droites.
\item
On consid\`ere quatre droites $\Delta_{1},\ldots,\Delta_{4}$, telles qu'il n'en existe pas
trois concourantes, ni deux parall\`eles. Donner le nombre $R_{4}$ de r\'egions d\'ecoup\'ees par
ces quatre droites.
\item
On consid\`ere $n$ droites $\Delta_{1},\ldots,\Delta_{n}$, telles qu'il n'en existe pas
trois concourantes, ni deux parall\`eles. Soit $R_{n}$ le nombre de r\'egions d\'elimit\'ees par
$\Delta_{1}\ldots\Delta_{n}$, et $R_{n-1}$ le nombre de r\'egions d\'elimit\'ees par
$\Delta_{1}\ldots\Delta_{n-1}$. Montrer que $R_{n}=R_{n-1}+n$.
\item
Calculer par r\'ecurrence le nombre de r\'egions d\'elimit\'ees par $n$ droites en position
g\'en\'erale, c'est-\`a-dire telles qu'il n'en existe pas trois concourantes ni deux parall\`eles.
\end{enumerate}
\end{exo}



\begin{exo}
\begin{enumerate}
\item Montrer les in\'egalit\'es suivantes, pour tout $n\in \N^{*}$:
 $$2^{n-1}\leq n! < n^{n}$$
 $$\left(\frac{2n+1}{3}\right)\sqrt{n} \leq \sum_{k=1}^n \sqrt{k} \leq \left(\frac{2n}{3}+\frac{1}{2}\right)\sqrt{n}$$
\item Montrer aussi que pour tout $n\geq 2$
$$n!\leq \left( \frac{n+1}{2}\right) ^{n}.$$
\end{enumerate}
\end{exo}




\begin{exo}
Pour tout entier naturel $n$, on pose 
$$ S_{n} = 1\cdot 2 + 2 \cdot 3+\cdots + (n-1)\cdot n$$
D\'emontrer que l'on a 
$$S_{n} = \frac{1}{3} n(n-1)(n+1)$$
\end{exo}


\begin{exo}
Pour $n\in \mathbb{N}$ on consid\`ere la propri\'et\'e suivante:
$$P_{n}: \quad 2^n>n^2$$
\begin{enumerate}
\item Pour quelles valeurs de $n$ l'implication $P_{n} \Longrightarrow P_{n+1}$
est-elle vraie?
\item Pour quelles valeurs de $n$ la propri\'et\'e $P_{n}$ est-elle vraie?
\end{enumerate}
\end{exo}


\begin{exo}
Que pensez-vous de la d\'emonstration suivante?
\begin{enumerate}
\item Pour tout $n\geq2$, on consid\`ere la propri\'et\'e:
$$P(n) :\quad \mbox{$n$ points distincts du plan sont toujours align\'es}$$
\item Initialisation: $P(2)$ est vraie car deux points distincts 
sont toujours align\'es.
\item H\'er\'edit\'e: On suppose que $P(n)$ est vraie et on 
va d\'emontrer $P(n+1)$.
 \noindent Soit donc $A_{1}, A_{2},\ldots,A_{n}, A_{n+1}$ des points distincts. 
D'apr\`es l'hypoth\`ese de r\'ecurrence, $A_{1}, A_{2},\ldots, A_{n}$ sont 
align\'es sur une droite $d$, et $A_{2},\ldots, A_{n}, A_{n+1}$ sont 
align\'es sur une droite $d'$. Les deux droites $d$ et $d'$ ayant $n-1$
points communs $ A_{2},\ldots, A_{n}$ sont confondues. Donc
$A_{1}, A_{2},\ldots, A_{n}, A_{n+1}$ sont align\'es,
ce qui montre l'h\'er\'edit\'e de la propri\'et\'e.
\item Conclusion: la propri\'et\'e $P(n)$ est vraie pour tout $n \geq 2$.
\end{enumerate}
\end{exo}


\begin{exo}
\begin{enumerate}
\item D\'emontrer que pour tout entier naturel $n$, $9$ divise $10^n -1$.
\item Soit $k$ un entier strictement positif. Etudier la propri\'et\'e suivante:
pour tout entier naturel $n$, $k$ divise $(k+1)^n + 2$.
\end{enumerate}
\end{exo}


\begin{exo}
D\'emontrer que pour $n\geq 1$, le produit de $n$ entiers impairs est un 
entier impair.
\end{exo}




\begin{exo}[Ecriture en base $b$]
 Soit $b\geq 2$ un entier fix\'e. D\'emontrer que pour tout 
$N\in \mathbb{N}^{\ast}$, il existe un entier $n\in \mathbb{N}$ 
et des entiers $a_0,a_1,\ldots, a_n$ appartenant \`a $\{\,0,1,\ldots,b-1\,\}$ tels que;
$$N=a_0+a_1b+\cdots+a_nb^n\quad\mbox{et}\quad a_n\neq 0$$
 \noindent D\'emontrer que pour chaque $N$, le syst\`eme $(n,a_0,a_1,\ldots, a_n)$ est d\'etermin\'e par la propri\'et\'e ci-dessus.
 \noindent On dit que $a_0,a_1,\ldots,a_n$ sont les chiffres de l'\'ecriture du nombre $N$ suivant la base $b$.
\end{exo}


\begin{exo}
D\'emontrer par r\'ecurrence que pour tout $k\in\mathbb{N}$, $k!$ 
divise le produit de $k$ entiers cons\'ecutifs:
$$\forall n\in \mathbb{N},\; k! \mid n(n+1)\cdots(n-k+1)$$
\end{exo}


\begin{exo}
\begin{enumerate}
\item  Calculer les restes de la division euclidienne de $1,4,4^2,4^3$ par
  $3$. 
\item  Formuler, pour tout $n\in\mathbb{N}$, une hypoth\`ese $\mathcal{P}(n)$ concernant le
  reste de la division euclidienne de $4^n$ par $3$. D\'emontrer que $\mathcal{P}(n)$
  est v\'erifi\'ee pour tout $n\in\mathbb{N}$.
\item  Pour tout $n\in\mathbb{N}$, le nombre $16^n+4^n +3$ est-il divisible par $3$.
\end{enumerate}
\end{exo}



\begin{exo}
 Montrer que pour tout entier $n\geq 1$:
$$\frac 1{1.2} + \frac 1{2.3} + \ldots + \frac 1{n.(n+1)} = \frac n{n+1}.$$
\end{exo}




\begin{exo}
D\'emontrer par r\'ecurrence sur $n$ que pour tout $n\geq 2$
l'implication $$ [x>-1,x\not =0] \Rightarrow [ (1+x)^n >1+nx]$$
est vraie.
\end{exo}




\begin{exo}[Suite de Fibonacci]
 On d\'efinit une suite $(F_n)$ de la fa\c con suivante :
$$F_{n+1} = F_n+F_{n-1} ; \quad F_0=1 , F_1=1 \ .$$
\begin{enumerate}
\item  Calculer $F_n$ pour $1<n<10$.
\item  Montrer que l'\'equation $x^2=x+1$ admet une unique solution positive 
$a$ que l'on calculera.
\item  Montrer que, pour tout $n\geq 2$, on a
$$a^{n-2}< F_n < a^{n-1} \ .$$
\end{enumerate}
\end{exo}


\begin{exo}
Montrer que :
$$\cos \frac{\pi}{2^n} = \sqrt{2+\sqrt{2+\ldots\sqrt{2}}}.$$
\end{exo}


\begin{exo}
Pour $n \in \mathbb{N},$   soient $a_0,\ldots,a_n$ des nombres r\'eels de m\^eme signe tel que $a_i > -1,$ montrer que:
$$(1+a_0)...(1+a_n) > 1+a_0+\ldots+a_n.$$ 
\end{exo}



\begin{exo}
Quels sont les entiers $n$ $ $tels que $4^{n}\leq n!$ ?
\end{exo}

\begin{exo}
Montrer que :
$$\forall n\geq 2,u_{n}=\sum\limits_{k=1}^{n}\frac{1}{k}\notin \N.$$
\emph{Indication} : montrer que
$$\forall n\geq 2,\exists (p_{n},q_{n})\in (\N^{*})^{2},u_{n}=\frac{2p_{n}+1}{2q_{n}}.$$
\end{exo}

\begin{exo}
Soit $f:\N^{*}\rightarrow \N^{*}$ une application v\'{e}rifiant :
$$\forall n\in \N^{*},f(n+1)>f(f(n)).$$
Montrer que $f=Id_{\N^{*}}.$
\emph{Indications} :\\
Que dire de $k\in \N$ tel que $f(k)=\inf \{f(n)|n\in \N\}$?\\
En d\'{e}duire que $\forall n>0,f(n)>f(0).$\\
Montrer ensuite que $\forall n\in \N, $ on a: $\forall m>n,f(m)>f(n)$ et $
\forall m\leq n,f(m)\geq m $ \\
(on pourra introduire $k$ tel que $f(k)$ soit le plus petit entier de la forme $f(m)  $ avec $m>n$).\\
En d\'eduire que $f$ est strictement croissante et qu'il n'existe qu'une seule solution au probl\`eme. Laquelle ?
\end{exo}




\begin{exo}
Pour $p \in \left\{ 1, 2, 3\right\}$ on note $S_{p} = \sum\limits_{k = 0}^n k^p$.
\begin{enumerate}
\item A l'aide du changement d'indice $i = n-k$ dans $S_{1}$, calculer $S_{1}$.
\item Faire de m\^eme avec $S_{2}$. Que se passe-t-il ?
\item Faire de m\^eme avec $S_{3}$ pour l'exprimer en fonction de $n$ et $S_{2}$.
\item Calculer $S_{3}$.
\end{enumerate}
\end{exo}

\begin{exo}
Pour calculer des sommes portant sur deux indices, on a int\'er\^et
\`a repr\'esenter la z\^one du plan couverte par ces indices et
\`a sommer en lignes, colonnes ou diagonales... Calculer :
\begin{enumerate}
\item $\sum\limits_{1\leq i \leq j \leq n}ij$.
\item $\sum\limits_{1\leq i < j \leq n}i (j-1)$.
\item $\sum\limits_{1\leq i < j \leq n} (i-1)j$.
\item $\sum\limits_{1\leq i \leq j \leq n} (n-i) (n-j)$.
\item $\sum\limits_{1\leq p, q \leq n} (p + q)^2$ (on posera $k = p + q$).
\end{enumerate}
\end{exo}





\end{document}
