\documentclass[a4paper,12pt]{amsart}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\documentclass[aap]{imsart}
%\RequirePackage{natbib}
\usepackage{inputenc}
\usepackage[T1]{fontenc}
\usepackage{inputenc}
%\usepackage[french]{babel}
\usepackage[english,francais]{babel}
\usepackage{ae,aeguill,icomma}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{marvosym}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{float}
\usepackage{color}
\usepackage{epsfig}
\usepackage{graphicx}

\usepackage{MnSymbol}

\usepackage{enumerate}

\usepackage{stmaryrd}

\usepackage{cases}

\usepackage{tikz}
\usetikzlibrary{trees}
\usepackage{verbatim}
\usetikzlibrary{shapes,arrows}
\usepackage{graphicx}

\usepackage{dsfont}

% settings
%\pubyear{2005}
%\volume{0}
%\issue{0}
%\firstpage{1}
%\lastpage{8}
%\arxiv{math.PR/0000000}


\setcounter{MaxMatrixCols}{10}

\setlength{\oddsidemargin}{-0.4cm}   
\setlength{\evensidemargin}{-0.6cm}  
\setlength{\topmargin}{-2cm}  
\setlength{\textwidth}{17.cm} 
\setlength{\textheight}{26.cm}

 

\newcommand\N{\mathbb{N}}
\newcommand\Z{\mathbb{Z}}
\newcommand\E{\mathbb{E}}
\newcommand\F{\mathbb{F}}
\newcommand\R{\mathbb{R}}
\newcommand\K{\mathbb{K}}
\newcommand\C{\mathbb{C}}
\newcommand\Pro{\mathbb{P}}
\newcommand\T{\mathbb{T}}
\newcommand\G{\mathbb{G}}
\newcommand{\pgcd}{\mathrm{PGCD}}
\newcommand{\veps}{\varepsilon}

\newcommand\calF{\mathcal{F}}
\newcommand\calG{\mathcal{G}}
\newcommand\calB{\mathcal{B}}
\newcommand\calO{\mathcal{O}}
\newcommand\calN{\mathcal{N}}
\newcommand\calC{\mathcal{C}}
\newcommand\calV{\mathcal{V}}
\newcommand\calA{\mathcal{A}}
\newcommand\calW{\mathcal{W}}
\newcommand\calR{\mathcal{R}}
\newcommand\calT{\mathcal{T}}
\newcommand\calH{\mathcal{H}}
\newcommand\calK{\mathcal{K}}
\newcommand\calP{\mathcal{P}}
\newcommand\calM{\mathcal{M}}
\newcommand\wh{\widehat}
\newcommand\wt{\widetilde}


\def\build#1_#2^#3{\mathrel{\mathop{\kern 0pt#1}\limits_{#2}^{#3}}}
\def\liml{\build{\longrightarrow}_{}^{{\mbox{$\mathcal L$}}}}
\def\limP{\build{\longrightarrow}_{}^{{\mbox{$\mathbb P$}}}}
\def\liminfty{\build{\longrightarrow}_{n \to \infty}^{}}
\def\siminfty{\build{\sim}_{n \to \infty}^{}}
\def\eqinfty{\build{=}_{n \to \infty}^{}}
\def\eqo{\build{=}_{x \to 0}^{}}

\numberwithin{equation}{section}
\theoremstyle{plain}
\newtheorem{TD}{Th�or�me-D�finition}
\newtheorem{Prop}[TD]{Proposition}
\newtheorem{PD}[TD]{Proposition-D�finition}
\newtheorem{Theo}[TD]{Th�or�me}
\newtheorem{Cor}[TD]{Corollaire}
\newtheorem{Lem}[TD]{Lemme}
\theoremstyle{definition}
\newtheorem{ND}[TD]{Notation-D�finition}
\newtheorem{Nota}[TD]{Notation}
\newtheorem{Def}[TD]{D�finition}
\newtheorem{Defs}[TD]{D�finitions}
\newtheorem{Ex}[TD]{Exemple}
\newtheorem{Exo}[TD]{Exercice}
\theoremstyle{remark}
\newtheorem{Rem}[TD]{Remarque}
\newtheorem{Rems}[TD]{Remarques}

\newcommand\card{\mathrm{card}}
\newcommand\lra\longrightarrow
\newcommand\llra\longleftrightarrow
\newcommand\Llra\Longleftrightarrow
\renewcommand{\pgcd}{\text{pgcd}}
\newcommand{\ds}{\displaystyle}

\hyphenation{BINAR}


\begin{document}

ECE 1 \hfill Correction en ligne le Vendredi 3 novembre. \\
2016-2017\\


\title[DM $\no$1]
{Devoir maison bonus $\no$1}
%\author{Vassili Blandin}
%\dedicatory{A rendre pour le 23 septembre}

\maketitle


\renewcommand{\labelitemi}{$\bullet$}
\begin{Exo}\hspace{0pt}\\
Un digicode est compos� de $n$ boutons, ces boutons sont num�rot�s de 1 � $n$. Pour entrer, il faut pousser tous les boutons dans un certain ordre. La r�gle est la suivante:
\begin{itemize}
\item tous les boutons doivent �tre pouss�s une unique fois,
\item il est possible de pousser plusieurs boutons en m�me temps.
\end{itemize}
Pour tout $n\in\N^\star$, on notera $E_n$ l'ensemble des entiers de $1$ � $n$.\\
On appellera un $n$-code, toute suite ordonn�e $(P_1,P_2,\ldots,P_j)$, avec $j\in\N^\star$, v�rifiant:
\begin{itemize}
\item pour tout $i\in\llbracket 1,j\rrbracket$, $P_j\in\calP(E_n)$,
\item les parties $P_1$, $P_2,\ldots,P_n$ sont deux � deux disjointes,
\item aucune partie n'est vide,
\item l'union des parties $P_1$, $P_2,\ldots,P_n$ est �gale � $E_n$.
\end{itemize}
On notera $c_n$ le nombre de $n$-codes.\\ 
Par exemple, on a:
\begin{itemize}
\item $c_1=1$ car le seul 1-code possible est $(\{1\})$,
\item $c_2=3$ car les 2-codes possibles sont: $(\{1\},\{2\})$, $(\{2\},\{1\})$ et $(\{1,2\})$.
\end{itemize}Nous allons chercher une relation de r�currence liant les $c_n$.
\begin{enumerate}
\item \begin{enumerate}
\item D�terminer $c_3$.
\item Soit $n\in\N^\star$, quel est le nombre de $n$-codes o� les boutons sont pouss�s successivement (c'est-�-dire o� toutes les parties $P_i$ sont des singletons)?
\item Soit $n\in\N^\star$, $n$ pair. Quel est le nombre de $n$-codes o� les boutons sont tous pouss�s par paires?
\item Soit $n\in\N^\star$, quel est le nombre de $n$-codes compos�s de 2 parties?
\end{enumerate}
\item \begin{enumerate}  
\item Soit $(n,k)\in\N^2$ avec $1\leq k<n$. Soit $P_1$ une partie fix�e de $E_n$ poss�dant $k$ �l�ments. Combien y a-t-il de $n$-codes commen�ant par cette partie $P_1$? On exprimera la r�ponse � l'aide de $c_i$ pour un $i$ bien choisi.
\item En d�duire une expression de $c_n$ en fonction de $(c_0,c_1, c_2,\ldots, c_{n-1})$. On prendra comme convention $c_0=1$.
\item V�rifier que l'expression obtenue fonctionne pour $c_2$ et $c_3$.\\
Donner le nombre de 4-codes et de 5-codes.
\end{enumerate}
\end{enumerate}
\end{Exo}\hspace{0pt}

\begin{Exo}
Soit $n\in\N^\star$.
\begin{enumerate}
\item Montrer que: $\ds\sum_{k=1}^n k(2k^2-1)=\frac{n(n+1)(n^2+n-1)}2$.
\item Soit $(x_k)_{k\in\llbracket1,n\rrbracket}$ une famille de r�els. Montrer que: $\ds\prod_{k=1}^ne^{x_k}=\exp\left({\sum_{k=1}^n x_k}\right)$.
\end{enumerate}
\end{Exo}\hspace{0pt}

\begin{Exo}
Pour tout $n\in\N$, $n\geq3$, calculer les sommes suivantes:
$$\text{(1)}\sum_{k=2}^{n-1} (4^{2-k}+5^k6^{n-k+1}),\hspace{60pt}
\text{(2)}\sum_{k=3}^{n+1} 2^{3k+2}\binom n{k-1}.$$
\end{Exo}

\begin{Exo}\hspace{0pt}
\begin{enumerate}
\item Soient $a$ et $b$ deux rationnels v�rifiant $a<b$, on note $\ds c=\frac{a+b}2$. Montrer que $c$ est un nombre rationnel v�rifiant $a<c<b$.
\item En d�duire, gr�ce � un raisonnement par l'absurde, qu'il n'existe pas de plus petit rationnel strictement sup�rieur � 1.
\end{enumerate}
\end{Exo}\hspace{0pt}

\begin{Exo}
Soit $n\in\N^\star$. Montrer que: $\ds\prod_{k=1}^n\frac{2k}{2k+1}=\frac{2^{2n}(n!)^2}{(2n+1)!}$.
\end{Exo}\hspace{0pt}

\begin{Exo}
Soit $E$ un ensemble et $A$, $B$ et $C$ trois parties de $E$.
\begin{enumerate}
\item Montrer que: $(A\backslash B)\backslash C = A\backslash(B\bigcup C)$.
\item Montrer que: $(A\backslash B)\bigcap C= (A\bigcap C)\backslash(B\bigcap C)$.
\end{enumerate}
\underline{Consigne:} ne pas traiter plus d'une question par une succession d'�galit�s.
\end{Exo}\hspace{0pt}




\end{document}