\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{fourier} \usepackage[scaled=0.875]{helvet} \usepackage{amsmath,amssymb,makeidx} \usepackage[mathscr]{eucal} \usepackage{eufrak} \usepackage{fancybox} \usepackage{graphicx} \usepackage{tabularx} \usepackage[normalem]{ulem} \usepackage{pifont} \usepackage{textcomp} \newcommand{\euro}{\eurologo{}} %Tapuscrit : Denis Vergès \usepackage{pst-plot,pst-text} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\D}{\mathbb{D}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \usepackage[left=3.5cm, right=3.5cm, top=3cm, bottom=3cm]{geometry} \addtolength{\topmargin}{-1.59999pt} \newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}} \renewcommand{\theenumi}{\textbf{\arabic{enumi}}} \renewcommand{\labelenumi}{\textbf{\theenumi.}} \renewcommand{\theenumii}{\textbf{\alph{enumii}}} \renewcommand{\labelenumii}{\textbf{\theenumii.}} \def\Oij{$\left(\text{O},~\vect{\imath},~\vect{\jmath}\right)$} \def\Oijk{$\left(\text{O},~\vect{\imath},~ \vect{\jmath},~ \vect{k}\right)$} \def\Ouv{$\left(\text{O},~\vect{u},~\vect{v}\right)$} \usepackage{fancyhdr} \usepackage[np]{numprint} \setlength\parindent{0mm} \usepackage[french]{babel} \begin{document} \lhead{\small CAPES externe}% \lfoot{\small{}} \rfoot{\small{mars 2010}} \lfoot{\small{}} %\renewcommand \footrulewidth{.2pt}% \pagestyle{fancy} \thispagestyle{empty} \marginpar{\rotatebox{90}{\textbf{A. P. M. E. P.}}} \begin{center} {\Large \textbf{CAPES épreuve 2 session 2010}} \bigskip \textbf{Notations} \end{center} \medskip \begin{itemize} \item[$\diamond$] Dans tout le problème, $\mathbb{K}$ désigne $\R$ ou $\C$. L'ensemble des suites d'éléments de $\mathbb{K}$ est noté $\mathbb{K}^{\N}$. Une suite $\left(a_{n}\right)_{n\in \N}$ d'éléments de $\mathbb{K}$ sera noté plus simplement $\left(a_{n}\right)$. On note $(0)$ la suite constante dont tous les termes sont nuls et on rappelle que deux suites $\left(a_{n}\right)$ et $\left(b_{n}\right)$ sont égales si et seulement si, pour tout entier $k \in \N$ on a $a_{k} = b_{k}$. \item[$\diamond$] Soient $\left(a_{n}\right)$ et $\left(b_{n}\right)$ deux éléments de $\mathbb{K}^{\N}$, on définit leur somme $\left(a_{n}\right) +\left(b_{n}\right)$, leur produit $\left(a_{n}\right) \times \left(b_{n}\right)$ et le produit d'une suite par un élément $\lambda \in \mathbb{K}$ respectivement par : \setlength\parindent{5mm} \begin{itemize} \item[] $\left(a_{n}\right) +\left(b_{n}\right) = \left(a_{n} + b_{n}\right)$ \item[] $\left(a_{n}\right) \times \left(b_{n}\right) = \left(c_{n}\right)$ où, pour tout entier $n \in \N : c_{n} = \sum_{k=0}^{n} a_{k}b_{n-k}$ \item[] $\lambda \cdot \left(a_{n}\right) = \left(\lambda a_{n}\right)$ \end{itemize} \setlength\parindent{0mm} \item[$\diamond$] On admet que $\left(\mathbb{K}^{\N}, +\right)$ est un groupe commutatif d'élément nul $(0)$. \item[$\diamond$] Pour tout $p \in \N$, on notera $X^p$ la suite $\left(x_{n}\right) \in \mathbb{K}^{\N}$ définie par : \[\left\{\begin {array}{ l c l} x_{p}& =& 1\\ x_{n} &=& 0~ \text{si}~ n \neq p \end{array}\right.\] On écrira aussi $X^0$ et $X^1$ respectivement $1$ et $X$. \item[$\diamond$] Pour tout $(k,~ n) \in \N^2$ tel que $0 \leqslant k \leqslant n$, le coefficient binomial $\binom{n}{k}$ est égal à $\dfrac{n!} {k!(n - k)!}$. \end{itemize} \vspace{0,5cm} \begin{center} \textbf{Partie I : série génératrice d'une suite} \boldmath $\left(a_{n}\right)$ \unboldmath \end{center} \medskip \begin{enumerate} \item Propriétés algébriques \begin{enumerate} \item Montrer que $\left(\mathbb{K}^{\N}, +, \times\right)$ est un anneau commutatif dont on précisera l'élément neutre. \item Montrer que $\left(\mathbb{K}^{\N}, +, \times\right)$ est intègre. (Indication : \emph{si $\left(a_{n}\right)$ est un élément non nul de $\mathbb{K}^{\N}$, on pourra considérer le plus petit entier $k$ tel que $a_{k} \neq 0$.}) \item Montrer qu'un élément $\left(a_{n}\right)$ de $\mathbb{K}^{\N}$ est inversible dans $\mathbb{K}^{\N}$ si et seulement si $a_{0} \neq 0$. \item Montrer que $\left(\mathbb{K}^{\N}, +, \cdot\right)$ est un $\mathbb{K}$-espace vectoriel. \end{enumerate} \medskip Les résultats précédents montrent que toute suite $\left(a_{n}\right) \in \mathbb{K}^{\N}$ peut s'écrire formellement sous la forme $\displaystyle\sum_{n\geqslant 0} a_{n}X^n$. Lorsqu'on note $A(X) = \displaystyle\sum_{n\geqslant 0} a_{n}X^n$ ou $A = \sum_{n\geqslant 0} a_{n}X^n$, alors $A(X)$ ou $A$ sera appelée série génératrice de la suite $\left(a_{n}\right)$. On remarque que par définition du produit des suites on a $X^p \times X^q = X^{p+q}$ pour tout $(p,~ q) \in \N^2$. D'autre part, si $A$ est une série génératrice, pour tout entier $k \geqslant 2,~A^k$ désigne le produit $\underbrace{A \times A \times ... \times A}_{k~\text{facteurs}}$. \medskip \emph{On remarquera aussi que s'il existe un entier $p$ tel que $a_{p} \neq 0$ et tel que pour tout entier $n > p$ on a $a_{n} = 0$ alors la série génératrice de la suite $\left(a_{n}\right)$ n'est autre qu'un polynôme de degré $p$ qu'on notera $\displaystyle\sum_{n=0}^p a_{n}X^n$.\\ D'après la question 1. c. ci-dessus, la série génératrice $\displaystyle\sum_{n \geqslant 0} a_{n}X^n$ est inversible si et seulement si $a_{0} \neq 0$. Dans toute la suite, si la série génératrice $A(X)$ est inversible, on écrira son inverse sous la forme $\dfrac{1}{A(X)}$. Plus généralement si la série génératrice $A(X)$ est inversible et si $B(X)$ est une série génératrice quelconque, le produit $B(X) \times \dfrac{1}{A(X)}$ sera noté $\dfrac{B(X)}{A(X)}$. Si de plus $B(X)$ et $A(X)$ sont des séries génératrices sous la forme de polynômes alors $\dfrac{B(X)}{A(X)}$ peut être assimilée à une fraction rationnelle sur $\mathbb{K}$ et on admet que les techniques de décomposition en éléments simples sur $\mathbb{K}$ restent valables pour $\dfrac{B(X)}{A(X)}$} \item \textbf{Éléments inversibles} \medskip \begin{enumerate} \item Montrer que la série génératrice inversible $\displaystyle\sum_{n \geqslant 0} X^n$ a pour inverse $1 - X$, c'est-à-dire que : \[\dfrac{1}{1 - X} = \sum_{n \geqslant 0} X^n\] \item Soit $a \in \mathbb{K} - \{0\}$, montrer que : \[\dfrac{1}{1 - aX} = \sum_{n\geqslant 0} a^n X^n\] \item Soient $a \in \mathbb{K} - \{0\}, b \in \mathbb{K} - \{0\}$ avec $a \neq b$, montrer que : \[\dfrac{1}{(1 - aX)(1 - bX)} = \left(\dfrac{a}{a-b} \right)\dfrac{1}{1 - aX} + \left(\dfrac{b}{b - a} \right)\dfrac{1}{1 - bX}\] \end{enumerate} \item \textbf{L'opérateur de dérivation} \medskip L'opérateur de dérivation, $D : \mathbb{K}^{\N} \to \mathbb{K}^{\N}$ est défini par : \[D : A = \sum_{n\geqslant 0}a_{n}X^n \mapsto D(A) = \sum_{n\geqslant 1}^{+ \infty}n a_{n}X^{n-1} = \sum_{n \geqslant 0}(n + 1)a_{n+1}X^n\] \begin{enumerate} \item Montrer que $D$ est un endomorphisme du $\mathbb{K}$-espace vectoriel $\mathbb{K}^{\N}$. Soient A et B deux séries génératrices. Montrer que : \item $D(A \times B) = D(A) \times B + A \times D(B)$. (on pourra commencer par traiter le cas où $A = X^p$ et $B = X^q$ où $(p,~ q) \in \N^2$). \item Si $B$ est inversible \[D\left(\dfrac{A}{B} \right) = \dfrac{D(A) \times B - A \times D(B)}{B^2}\] \end{enumerate} \item \textbf{Quelques exemples} \begin{enumerate} \item Montrer que la suite $\left(a_{n}\right)_{n \in \N}$ dont la série génératrice est : \[A(X) = \dfrac{1}{(1 - X)^2}\] est définie pour tout entier $n$ par $a_{n} = n + 1$. \item Montrer que, pour tout $p \in \N$, la suite $\left(a_{p,~n}\right)_{n \in \N}$ dont la série génératrice est \[A_{p}(X) = \dfrac{1}{(1 - X)^p}\] est définie pour tout entier $n$ par : \[a_{p,~n} = \binom{n+p - 1}{n}\] \item Soit $A(X)$ la série génératrice d'une suite $\left(a_{n}\right)_{n \in \N}$. Montrer que $\dfrac{A(X)}{1 - X}$ est la série génératrice de la suite $\left(b_{n}\right)_{n \in \N}$ définie par : \[b_{n} = \sum_{k=0}^n a_{k}\] \item En déduire que, pour tout entier $p \in \N$ on a : \[\sum_{k=0}^n \binom{k + p - 1}{k} = \binom{n + p}{n}\] \end{enumerate} \end{enumerate} \vspace{0,5cm} \begin{center} \textbf{Partie II : séries génératrices et suites récurrentes} \end{center} \medskip \begin{enumerate} \item On considère la suite $\left(a_{n}\right)_{n \in \N}$ définie par : \[\left\{\begin{array}{l c l} a_{0}& = &0\\ \multicolumn{3}{l}{\forall n \in \N,~ a_{n+1} = 2a_{n} + n} \end{array}\right.\] On se propose de déterminer la formule explicite de $a_{n}$ en fonction de $n$. On note $A(X)$ la série génératrice de la suite $\left(a_{n}\right)_{n \in \N}$. \begin{enumerate} \item Montrer que : \[A(X) = 2X \times A(X) + X^2 \times \sum_{n\geqslant 0} (n + 1)X^n\] \item Déterminer la décomposition en éléments simples sur $\mathbb{K}$ de la fraction rationnelle \[\dfrac{X^2}{(1 - X)^2 (1 - 2X)}\] \item En déduire l'expression de $a_{n}$ en fonction de $n$. \end{enumerate} \item On considère la suite de Fibonacci $\left(F_{n}\right)_{n\in \N}$ définie par : \[\left\{\begin{array}{l c l} F_{0}& =& 0\\ F_{1}& =& 1\\ \multicolumn{3}{l}{\forall n \in \N,~ F_{n+2} = F_{n+1} + F_{n}} \end{array}\right.\] et on note $F(X)$ la série génératrice de la suite $\left(F_{n}\right)_{n\in \N}$. \begin{enumerate} \item Montrer que : \[F(X) = \dfrac{1}{\sqrt{5}}\left(\dfrac{1}{1 - \alpha_{1}X} - \dfrac{1}{1 - \alpha_{2}X} \right)\] où \[\alpha_{1} = \dfrac{1 + \sqrt{5}}{2} \quad \text{et}\quad \alpha_{2} = \dfrac{1 - \sqrt{5}}{2}\] \item En déduire l'expression de $F_{n}$ en fonction de $n$. \end{enumerate} \item Suites récurrentes linéaires d'ordre $k \:(k \geqslant 1)$. %\alpha_{1} = \dfrac{1 + \sqrt{5}}{2} \quad \text{et}\quad \alpha_{2} = \dfrac{1 - \sqrt{5}}{2} \medskip Soit $\left(a_{1},~ \ldots,~ a_{k}\right) \in \C^k$, avec $a_{k} \neq 0$. On considère l'ensemble $\mathcal{U}$ des suites complexes $\left(u_{n}\right)$ définies par la donnée de $\left(u_{0},~ \ldots,~ u_{k-1}\right) \in \C^k$ et par la relation de récurrence \[\forall n \geqslant k,~ u_{n} = a_{1}u_{n-1} + a_{2}u_{n-2} + \ldots + a_{k}u_{n-k}.\] (\emph{On utilisera, sans le démontrer, le fait que $(\mathcal{U},~+,~\cdot)$ est un $\C$-espace vectoriel}). Soit $\left(u_{n}\right) \in \mathcal{U}$. On note $S$ la série génératrice de $\left(u_{n}\right)$, et $(E)$ l'équation caractéristique de $\left(u_{n}\right)$ : \[z^k = a_{1}z^{k-1} + a_{2}z^{k-2} +\ldots + a_{k} \quad (E)\] \begin{enumerate} \item Montrer que $\varphi : \left(u_{n}\right) \in \mathcal{U} \mapsto \left(u_{0},~ u_{1},~ \ldots,~ u_{k-1}\right)$ est un isomorphisme de $\mathcal{U}$ dans $\C^k$. \item On pose $Q(X) = 1 - a_{1}X - \ldots - a_{k}X^k$ et $P(X) = Q(X) \times S(X)$. Montrer que $P(X)$ est un polynôme de degré au plus $k - 1$, à coefficients dans $\C$. \item On note $z_{1},~\ldots,~z_{p}$ les racines dans $\C$ de l'équation $(E)$ et $\alpha_{1},~\ldots,~\alpha_{p}$ les ordres de multiplicité respectifs de $z_{1},~\ldots,~z_{p}$. Montrer qu'il existe des nombres complexes $b_{i,~j},~1 \leqslant i \leqslant p,~1 \leqslant j \leqslant \alpha_{ i}$ tels que : \[\dfrac{P(X)}{Q(X)}= \sum_{i=1}^{p} \left(\sum_{j=1}^{\alpha_{i}}\dfrac{b_{i,~j}}{\left( X - 1/z_{i}\right)^j} \right)\] \item Montrer alors qu'il existe des polynômes $R_{1},~\ldots,~R_{p}$ tels que pour tout $n$ \[u_{n} = \sum_{i=1}^p R_{i}(n) z_{i}^n~ \text{o\`u}~\forall i,\: deg\left(R_{i} \right) < \alpha_{i}.\] \item On note $\mathcal{V}$ l'ensemble des suites $\left(v_{n}\right)$ dont le terme général s'écrit $v_{n} = \displaystyle\sum_{i=1}^p P_{i}(n)z_{i}^n$ où pour tout $i \in \{1,~ 2,~\ldots,~p\},~ P_{i}$ est un polynôme tel que $deg \left(P_{i}\right) < \alpha_{i}$. Démontrer que $(\mathcal{V},~+,~\cdot )$ est un $\C$-espace vectoriel dont la dimension vérifie l'inégalité dim $\mathcal{V} \leqslant k$ et déduire que $\mathcal{V} = \mathcal{U}$. \end{enumerate} \end{enumerate} \vspace{0,5cm} \begin{center} \textbf{Partie III : Nombre de partitions d'un ensemble} \end{center} \medskip Soient $k \geqslant 1$ un entier et $S$ un ensemble non vide, on dit que $\left\{S_{1},~ S_{2},~\ldots,~ S_{k}\right\}$ est une partition de $S$ en $k$ classes si : \[\left\{\begin{array}{l} \forall i \in \{1, \ldots, k\},~ S_{i} \neq \emptyset\\ \forall (i,~ j) \in \{1, \ldots, k\}^2,~S_{i} \cap S_{j} = \emptyset~ \text{si}~ i \neq j\\ \displaystyle \bigcup_{i=1}^k S_{i} = S \end{array}\right.\] Pour tout entier $n \geqslant 1$ et tout entier $k \in \{1, \ldots, k\}$ on note $\left\{\genfrac{}{}{0pt}{}{n}{k} \right\}$ le nombre de partitions d'un ensemble de cardinal $n$ en $k$ classes. On pose par convention : \setlength\parindent{5mm} \begin{itemize} \item[$\diamond$] pour tout entier $n \geqslant 1$ : $\left\{\genfrac{}{}{0pt}{}{n}{0} \right\} = 0$ \item[$\diamond$] pour tout entier $k > n$ : $\left\{\genfrac{}{}{0pt}{}{n}{k}\right\} = 0$ \item[$\diamond$] $\left\{\genfrac{}{}{0pt}{}{0}{0}\right\} = 1$ \end{itemize} \setlength\parindent{0mm} \begin{enumerate} \item Donner toutes les partitions de l'ensemble $S = \{1,~ 2,~ 3,~ 4\}$ en 2 classes. Cette question montre que $\left\{\genfrac{}{}{0pt}{}{4}{2}\right\} = 7$. On se propose dans ce qui suit de calculer $\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}$ en fonction de $n$ et $k$. \item Montrer que, pour tout entier $n \geqslant 1$ on a : \[\left\{\genfrac{}{}{0pt}{}{n}{k}\right\} = \left\{\genfrac{}{}{0pt}{}{n-1}{k-1}\right\} + k\left\{\genfrac{}{}{0pt}{}{n - 1}{k}\right\}\] (\emph{On fixera un élément $s \in S$ et on considèrera les partitions contenant le singleton $\{s\}$ et les partitions qui ne le contiennent pas}). \item On considère la série génératrice \[A_{k}(X) = \sum_{n \geqslant 0} \left\{\genfrac{}{}{0pt}{}{n}{k}\right\}X^n\] \begin{enumerate} \item Montrer que pour tout entier $k \geqslant 1$, on a : \[A_{k}(X) = X \times A_{k-1}(X) + kX \times A_{k}(X)\] \item En déduire que, pour tout entier $k \geqslant 1$, on a : \[A_{k}(X) = \dfrac{X^k}{\Pi_{m=1}^{k}(1 - mX)}\] \item Montrer que, pour tout entier $k \geqslant 1$, on a : \[\dfrac{1}{\Pi_{m=1}^{k}(1 - mX)} = \sum_{r=1}^{k} \dfrac{\alpha_{r}}{1 - rX}\] où, pour tout $r \in \{1,~\ldots,~k\},~\alpha_{r} = (-1)^{k-r}\dfrac{r^{k-1}}{(r - 1)!(k - r)!}$. \item En déduire que, pour tout entier $n \geqslant k$ : \[\left\{\genfrac{}{}{0pt}{}{n}{k}\right\} = \sum_{r=1}^k (-1)^{k - r}\dfrac{r^n}{r!(k - r)!}\] \end{enumerate} \item Application : nombre de surjections On considère un ensemble $E$ de cardinal $n$ et un ensemble $F$ de cardinal $p$ où $n$ et $p$ sont deux entiers strictement positifs. On se propose de calculer le nombre $S(n,~ p)$ de surjections de $E$ sur $F$. \begin{enumerate} \item Que vaut $S(n,~ p)$ lorsque $p > n$ ? \item Que vaut $S(n,~ n)$ ? \item On suppose maintenant que $p \in \{1,~\ldots,~n\}$. Montrer que : \[S(n,~ p) = p!\left\{\genfrac{}{}{0pt}{}{n}{p}\right\}\] \end{enumerate} \end{enumerate} \vspace{0,5cm} \begin{center} \textbf{Partie IV : Nombre de dérangements} \end{center} \medskip Soit $n \in \N^{*}$. On note $\mathfrak{S}_{n}$ l'ensemble des permutations de $\{1,~ \ldots,~ n\}$. Un dérangement de l'ensemble $\{1,~ \ldots,~ n\}$ est une permutation $\sigma \in \mathfrak S_n$ sans point fixe c'est-à-dire telle que pour tout entier $i \in \{1,~ \ldots,~ n\},~ \sigma(i) \neq~i$. On note $d_{n}$ le nombre de dérangements de l'ensemble $\{1,~ \ldots,~ n\}$. On pose $d_{0} = 1$ et pour tout entier naturel $n,~ p_{n} = \dfrac{d_{n}}{n!}$. \begin{enumerate} \item Calculer $d_{1},~ d_{2}$ et $d_{3}$. \item Pour $0 \leqslant k \leqslant n$, on note $B_{k}$ l'ensemble des permutations de $\mathfrak S_n$ ayant exactement $k$ points fixes. \begin{enumerate} \item Montrer que le cardinal de $B_{k}$ vérifie l'égalité : Card $\left(B_{k}\right ) = \displaystyle\binom{n}{k}d_{n - k}$ et en déduire que : \[\sum_{k=0}^n \binom{n}{k}d_{n - k} = n!\] \item Soit $P$ la série génératrice de la suite $\left(p_{n}\right)$. Montrer que \[E(X) \times P(X) = \sum_{n \geqslant 0} X^n,~\text{o\`u}~ E(X) = \sum_{n \geqslant 0} \dfrac{1}{n!}X^n.\] \item Déterminer la série génératrice inverse de $E(X)$. \item En déduire que \[d_{n} = n!\sum_{k=0}^n \dfrac{(-1)^k}{k!}\] \end{enumerate} \end{enumerate} \vspace{0,5cm} \begin{center} \textbf{Partie V : Nombres de Catalan} \end{center} \begin{enumerate} \item \textbf{Chemins de Dyck} \medskip Le plan est rapporté à un repère \Oij. Pour tout entier $n \geqslant 1$, on appelle chemin de Dyck de longueur $2n$, toute suite $\left(s_{0},~ s_{1},~\ldots,~ s_{2n}\right)$ de points du plan dont les coordonnées sont des entiers positifs tels que $s_{0} = (0,~ 0),~ s_{2n} = (2n,~ 0)$ et, tels que, pour tout entier $k \in \{0,~ 1,~\ldots,~2n-1\},~ s_{k+1}$ est l'image de $s_{k}$ par la translation de vecteur $\vect{\imath} + \vect{\jmath}$ ou de vecteur $\vect{\imath} - \vect{\jmath}$. Voici un chemin de Dyck de longueur 16. \medskip \psset{unit=0.7cm} \begin{center} \begin{pspicture}(0,-0.5)(16.5,5) \psaxes[linewidth=1.5pt]{->}(0,0)(16.5,5) \psgrid[gridlabels=0pt,subgriddiv=1,gridwidth=0.3pt](0,0)(16,5) \psline[linewidth=1.25pt](0,0)(1,1)(2,2)(3,1)(4,2)(5,1)(6,0)(7,1)(8,2)(9,3)(10,2)(11,3)(12,2)(13,1)(14,0)(15,1)(16,0) \psdots(0,0)(1,1)(2,2)(3,1)(4,2)(5,1)(6,0)(7,1)(8,2)(9,3)(10,2)(11,3)(12,2)(13,1)(14,0)(15,1)(16,0) \end{pspicture} \end{center} On note $c_{n}$ le nombre de chemins de Dyck de longueur $2n$. Les nombres $c_{n}$ sont appelés \textbf{nombres de Catalan}. Pour tout chemin de Dyck $C = \left(s_{0},~ s_{1},~\ldots,~ s_{2n}\right)$ de longueur $2n$ on note $k(C)$ le plus petit entier tel que $s_{k(C)}$ soit d'ordonnée nulle et d'abscisse non nulle. \begin{enumerate} \item Justifier que $k(C)$ est un entier pair. \item Montrer que le nombre de chemins de Dyck $C$ de longueur $2n$ tel que $k(C) = 2n$ est égal à $c_{n-1}$. \item Montrer que le nombre de chemins de Dyck $C$ de longueur $2n$ tel que $k(C) = 2p$ avec $p \in \{1,~\ldots,~n\}$ est égal à $c_{p-1}c_{n-p}$. (Par convention, on pose $c_{0} = 1$). \item En déduire que la suite $\left(c_{n}\right)$ vérifie la relation de récurrence : \[c_{n} = \sum_{j=1}^n c_{j-1}c_{n-j}.\] \end{enumerate} \item \textbf{Expression des nombres de Catalan} \medskip Soit $r$ un nombre rationnel positif. On définit les coefficients binomiaux généralisés par : \[\left\{\begin{array}{l c l} \binom{r}{0}&=&1\\ \binom{r}{n}&=&\dfrac{\Pi_{k=0}^{n-1} (r - k)}{n!}~\text{pour tout entier}~ n \geqslant 1 \end{array} \right.\] On admet qu'il existe une unique série génératrice $S(X) = \Sigma_{n \geqslant 0} s_{n}X^n$ telle que : \[\left\{\begin{array}{l c l} s_{0} &=&1\\ S(X)^2 &=& 1 - 4X \end{array}\right.\] et que cette série génératrice est donnée par : \[S(X) = \sum_{n \geqslant 0} \binom{\frac{1}{2}}{n}(-4)^nX^n\] \begin{enumerate} \item Montrer que : \[S(X) = 1 - \sum_{n \geqslant 0} \dfrac{2}{n + 1}\binom{2n}{n}X^{n+1}\] \item On pose \[H(X) = \dfrac{1}{2}\left(1 - S(X)\right)\] Vérifier que $H(X) = X + (H(X))^2$. \end{enumerate} \item Soit $C(X)$ la série génératrice de la suite $\left(c_{n}\right)$ des nombres de Catalan. \begin{enumerate} \item Montrer que : \[X \times C(X) = X + (X \times C(X))^2\] \item En déduire que, pour tout entier $n$, on a : \[c_{n} = \dfrac{1}{n + 1}\binom{2n}{n}\] puis que, pour tout entier $n \geqslant 1$ on a : \[c_{n} = \binom{2n}{n} - \binom{2n}{n - 1}.\] \end{enumerate} \end{enumerate} \end{document}