\documentclass[french,12pt]{article}

% Les packages....
\usepackage{a4}
\usepackage[francais]{babel}
\usepackage [applemac] {inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{euscript,latexsym,pifont}
\usepackage{enumerate,theorem}
\usepackage{vmargin, indentfirst, fancyheadings} 
\setpapersize{A4}

%Quelques commandes perso pour les principaux symboles mathématiques
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\K}{\mathbb{\Bbbk}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\nl}{\mid \! \!}
\newcommand{\nr}{\! \! \mid}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Sig}{\mathfrak{S}}
\newcommand{\g}{\mathfrak{g}}
\newcommand{\Od}{\mathcal{O}}
\newcommand{\lnq} {<}
\newcommand{\gnq} {>}
\newcommand{\gl}{\mathfrak{gl}}
\newcommand{\GL}{\textrm{GL}}

% Environement pour les exercices
\theoremstyle{break}
\newtheorem{exo}{Exercice}

\begin{document}

% La mise en page
%\setlength{\headrulewidth}{0pt}
\cfoot{\thepage}
\chead{Mathématiques S1}
\lhead{Algébre-Géométrie}
\rhead{2009/2010}
\pagestyle{fancy}

% Le titre (avec un peu de bidouille)
\title{TD6: $\N$}
\author{}
\date{}

\maketitle
\thispagestyle{fancy}

\begin{exo}
Redémontrer par récurrence sur $n$ les formules de sommes arithméthiques et géométriques 
$$ \sum_{k=0}^{n-1} n_{0}.q^k=n_{0}\times\frac {1-q^{n}}{1-q} \qquad \sum_{k=0}^{n-1} n_{0}+r.k=n\times n_{0}+r\times\frac{n(n-1)}2$$ 
\end{exo}

\begin{exo}
Montrer que pour tout $n\in \N^*$ on a $$\sum_{k=0}^n (3k+1)=\frac 12 (3n^2+5n+2)$$
\end{exo}


\begin{exo}
Soit $n\in\N$. Montrer que $2^{3^n}-2$ est divisible par $3$.\\
Attention! $x^{y^z}=x^{(y^z)}\neq (x^y)^z=x^{y\times z}$.
\end{exo}

\begin{exo}[*]
Montrer que $\mathcal P (\N)$ n'est pas dénombrable.
(Indication: On pourra supposer qu'il existe $f$ une bijection de $\N$ dans $\mathcal P(\N)$ et s'interesser à $E=\{y\mid y\notin f(y)\}$).

\end{exo}

\begin{exo}
Montrer que pour tout $n\in\N$, on a $$\sum_{k=0}^{n-1}( 3k^2+3k+1)=n^3.$$
\end{exo}



\begin{exo}[*]$\phantom 1$\\

Soit $f:\left\{\begin{array}{rcl} {\N^2}&\rightarrow {\N} \\{(p,q)}&\mapsto &{\frac12(p+q)(p+q+1) + p}\end{array}\right.$
\begin{itemize}
\item  Montrer pour $q > 0$ : $f(p+1,q-1) = f(p,q)+1$ et $f(0,p+1) = f(p,0)+1$.
\item  Montrer que : $f(0,p+q) \leqslant f(p,q) \lnq f(0,p+q+1)$.
\item  Montrer que $g$ : $n\mapsto f(0,n)$ est strictement croissante.
\item  Montrer que $f$ est injective (on supposera $f(p,q) = f(p',q')$ et on montrera
     dans un premier temps que $p+q = p'+q'$).
\item Montrer que $f$ est surjective.
\item Chercher une interprétation graphique de ce résultat.
\item En déduire qu'il existe une surjection de $\N$ sur $\Q$.
\end{itemize}
\end{exo}


\begin{exo}[*]
On veut montrer que il n'existe pas $f:\N\rightarrow \N$ tel que $f\circ f(n)=n+2009$ pour tout $n\in \N$.\\
Soit $E=\{0,\dots 2008\}$, $F=\N\setminus E$, $G=f(\N)\cap E$ et $H=E\setminus G$.\\
Si $f$ existe, montrer que\\
1) $f$ est injective\\
2) $f(F)\subset F$\\
3) $f^{-1}(F)=F\cup G$\\
4) $f^{-1}(G)=H$\\
...Et trouver une contradiction.
\end{exo}

\end{document}