\documentclass[10pt]{article}
\usepackage[latin1]{inputenc}
\pagestyle{empty}
\textheight 265mm
\textwidth 160mm
\hoffset -14mm
\voffset -26mm
\parindent=0pt

\font\twelvesym=msbm10 at 12pt
\font\tensym=msbm10
\font\sevensym=msbm7
\font\fivesym=msbm5

\newfam\symfam
\textfont\symfam=\tensym
\scriptfont\symfam=\sevensym
\scriptscriptfont\symfam=\fivesym
\def\sym{\fam\symfam\tensym}
\def\fns{\footnotesize}
\def\mref#1{(\ref{#1})}
\def\mod{\ {\rm mod}\ }
\def\mods{\ {\rm mods}\ }
\def\bu{\bullet}
\def\ul#1{\underline#1}

%%% Fleches %%%%%%%%%%%

\def\dra{{$\rightarrow$}}
\def\dla{{$\leftarrow$}}
\def\dua{{$\uparrow$}}
\def\dda{{$\downarrow$}}
\def\dnw{{$\nwarrow$}}
\def\dse{{$\searrow$}}
\def\ra{\rightarrow}

%%%%%%%%%%%%%%%%%%%%%%
% Sauts
%%%%%%%%%%%%%%%%%%%%%%

\def\ss{\smallskip}
\def\ms{\medskip}
\def\bs{\bigskip}
\def\small{\footnotesize}
\def\b{$\Bullet\ $}
\def\gcr{\hfill\cr}
\def\hs{\hbox to 3mm{}}
\def\hhs{\hbox to 5cm{}}
\def\btu{\bigtriangleup}
\def\Box{\triangle}
\def\mhs{\hbox to 1cm{}}



\def\up#1{\raise 1ex\hbox{\footnotesize#1}}
\def\pointir{\unskip . --- \ignorespaces}
\def\cs{$\clubsuit\ $}
\def\sps{$\spadesuit\ $}
\def\hs{$\heartsuit\ $}
\def\ds{$\diamondsuit\ $}

\def\bb{\sym}
\def\A{{\cal A}}
\def\al{\alpha}
\def\be{\beta}
\def\la{\lambda}
\def\sa{\sqrt{A}}
\def\ra{\rightarrow}
\def\sq#1{\sqrt{#1}}
\def\ra{\rightarrow}

\def\B{{\cal B}}
\def\E{{\sym E}}
\def\F{{\mathcal{F}}}
\def\N{{\sym N}}
\def\C{{\sym C}}
\def\R{{\sym R}}
\def\Z{{\sym Z}}
\def\Q{{\sym Q}}
\def\P{{\mathcal{P}}}
\def\s{{\sigma}}
\def\al{\alpha}
\def\De{\Delta}
\def\Ep{{\mathcal{E}}_p}
\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}

\def\bsk{\bigskip}
\def\msk{\medskip}
\def\ssk{\smallskip}

\begin{document}
\begin{center}
{\bf Examen du cours de ``Combinatoire algébrique, énumérative et fonctionnelle''.\\ 
Madacascar 2007-2008}.\\
\end{center}

\bsk
{\footnotesize Seules les notes manuscrites, le support de cours 
et la calculette sont autoris\'es. Le candidat s'efforcera de r\'ediger lisiblement et avec soin sa copie. En particulier, les r\'eponses doivent \^etre justifi\'ees et les résultats clairement dégagés.\\
Le sujet est (en principe) trop long pour le temps imparti, il est donc 
conseill\'e de traiter en priorit\'e les questions que l'on sait faire 
en en indiquant clairement la r\'ef\'erence}.

\bsk
{\bf I}) {\sc Question de Cours}:

1) Les s\'eries sont des fonctions, donner le cadre g\'en\'eral de leur d\'efinition.\\
2) Rappeler les deux formules de produit (Hadamard et Cauchy) et leurs propri\'et\'es.\\
3) a) Donner les formes des trois types d'expression des fonctions rationnelles de $\C[[z]]$ (rat, coeff, rec).\\
b) D\'ecrire comment on passe de l'une \`a l'autre.\\
c) Qu'est-ce qu'une famille (de séries) sommable ?\\
{\sc Application}\pointir\\
Montrer que $\Big((z+z^2)^n\Big)_{n\in \N}$ est sommable. En déduire une expression de $F_n$ (nième nombre de Fibonacci) sous forme d'une somme de binomiaux.

\ss
{\bf II)} {\sc Exercices}\\
A) 1) Développer les séries suivantes :

\begin{center}
\begin{tabular}{ccc} 
a) $\frac{1}{1 - z^3}$ &  b) $\frac{1 - z}{1 + z}$ & c) $\frac{1 - \sqrt{1 + z^2}}{z}$ 
\end{tabular}
\end{center}

\ss
2) Sommer : 

\begin{center}
\begin{tabular}{ccc} 
a) $\sum_{n\geq 0} nz^3n$ & b) $\sum_{n\geq 0} n(n - 1)z^n$ c) $\sum_{n\geq 0} n^2 z^n$ 
\end{tabular}
\end{center}

\bs
B) On rappelle que le produit de Hadamard de deux séries $A=\sum_{n\geq 0}a_n z^n$ et $B=\sum_{n\geq 0}b_n z^n$ est défini par $A\odot B=\sum_{n\geq 0}a_nb_n z^n$.\\
1) Soit $\phi(z)=\sum_{n\in \N}a_n z^n$. Pour quels nombres complexes $\al\in \C$ les égalit\'es suivantes sont-elles vraies ?
\begin{center}
\begin{tabular}{cc}
a) $\frac{1}{1-z^5}\odot\phi(z)=\frac{1}{5}(\phi(z)+\phi(\al z)+\phi(\al^2 z)+\phi(\al^3 z)+\phi(\al^4 z))$ & 
b) $\frac{1}{1-\al z}\odot=\phi(\al z)$
\end{tabular}
\end{center}

2) {\sc Application}\pointir Calculer
\begin{center}
\begin{tabular}{ll}
a) $\frac{1}{1-z^3}\odot\Big(\sum_{n\in \N}F_n z^n\Big)$ & 
b) $\frac{1}{1+z}\odot\Big(\sum_{n\in \N}F_n z^n\Big)$ 
\end{tabular}
\end{center}
3) Donner une r\`egle dans le style de (A)1)a) pour $\frac{z}{1-z^4}\odot\phi(z)$ et en d\'eduire\\ $\frac{z}{1-z^4}\odot\Big(\sum_{n\in \N}F_n z^n\Big)$.


B) 1) Les nombres de Fibonacci sont donn\'es par la r\'ecurrence 
\begin{equation}
F_0=0;\ F_1=1;\ F_{n+2}=F_n+F_{n+1}
\end{equation}
a) Red\'emontrer que la s\'erie g\'en\'eratrice des nombres de Fibonacci est $S(z)=\frac{z}{1-z-z^2}$.\\
b) D\'ecomposer la fraction pr\'ec\'edente en \'el\'ements simples et en d\'eduire (justifier) que 
\begin{equation}
F_n=\frac{1}{\sqrt{5}}(\phi^n-\bar\phi^n)
\end{equation}
c) D\'eduire du (b) une expression, sous forme de fraction rationnelle, de la s\'erie $\sum_{n=0}^\infty F_n^2 z^n$.\\
{\fns Indication: On \'evitera au maximum les calculs \`a l'aide des relations $\phi\bar\phi=-1$ et $\phi+\bar\phi=1$.}\\
d) En calculant $F_{n+3}^2-F_{n+2}^2$ trouver une relation de r\'ecurrence entre les $a_n=F_n^2$. Recalculer la fraction 
rationnelle $\sum_{n}F_n^2z^n$.\\
2) On consid\`ere une suite satisfaisant une relation de r\'ecurrence d'ordre deux 
$$x_{n+2}=a_0 x_n+a_1 x_{n+1}.$$
a) En s'inspirant de la question (4d) et en d\'eveloppant $x_{n+3}^2-a_0x_{n+2}^2$, trouver une relation de r\'ecurrence 
satisfaite par la suite $x_n^2$.\\
b) Donner la fraction rationnelle $\sum_{n=0}^\infty (x_n)^2z^n$ sous la forme $\frac{P(z)}{1-zQ(z)};\ P,Q\in C[z]$.\\
c) Montrer que $\Big((zQ(z))^n\Big)_{n\in \N}$ est sommable et en déduire une nouvelle expression de $x_n^2$.

\ss
3) Soit $\al=1+\sqrt{2};\ \bar\al=1-\sqrt{2}$.\\
a) Donner une relation du type 
\begin{equation}\label{reclin}
\al^2=u\al +v\ ,\ u,v\in\Z  
\end{equation} 

b) Les coefficients $u,v\in \Z$ sont-ils uniques ?\\ 
c) Montrer, en utilisant \mref{reclin}, que la suite $g_n=\frac{1}{\sqrt{2}}(\al^n-\bar\al^n)$ vérifie 
$$g_{n+2}=g_n+2 g_{n+1}.$$ 
et en déduire que $g_n\in\N$.\\
d) \`A l'aide de (2), calculer 
$$ S_1=\sum_{n=0}^\infty g_nz^n\ \textrm{ et }\ S_2=\sum_{n=0}^\infty g_n^2z^n$$

\ss
{\bf III. Probl\`eme}

On construit une suite de $\Z^2$ par le proc\'ed\'e suivant
\def\bu{$\bullet$}
\begin{center}
\begin{tabular}{ccccccccccc}
\bu     &\dla   &\bu    &\dla   & \bu   & \dla  & \bu   & \dla  &
\bu   \\ 
\dda    &       &       &       &       &       &       &
& \dua  \\ \bu     &       &\bu    &\dla   & \bu   & \dla  & \bu
&       & \bu\\ \dda    &       & \dda  &       &       &       &
\dua  &       & \dua \\
        &       &\bu    &       &$\circ$& \dra  & \bu   &       & \bu \\
        &       &\dda   &       &       &       &       &       & \dua\\
        &       &\bu    & \dra  & \bu   & \dra  & \bu   & \dra  & \bu\\
\end{tabular}
\end{center}

c'est une suite de couples ($c_n$), le point de d\'epart ($\circ$)
\'etant l'origine ($c_0=(0,0)$).\\ a) Soit $d_1(n)$, l'indice du
n\up{i\`eme} passage de $c_n$ sur la premi\`ere demi-diagonale
$x=y;\ x> 0$. On a
\begin{center}
\begin{tabular}{c||c|c|c|c|c|}
$n$     &1  &2  &3  &4  &5\\ \hline $d_1(n)$&2  &12 &30 &56 &90\\
\end{tabular}
\end{center}
montrer que $a_1(n)=d_1(n+1)-d_1(n)$ v\'erifie $a_1(n+1)-a_1(n)=8$
(on pourra donner une preuve ``picturale'', sinon il est
conseill\'e d'admettre le r\'esultat et de continuer).\\ b)
D\'eduire de la question pr\'ec\'edente que $a_1(n)=8n+2$.\\ c)
Donner les s\'eries g\'en\'eratrices $\sum_{n\geq 0}a_1(n)z^n$
puis $\sum_{n\geq 0}d_1(n)z^n$.\\ d) D\'eduire de ce qui
pr\'ec\`ede que $d_1(n)=(2n)^2-2n$.\\ 3) Montrer que les indices
du n\up{i\`eme} passage de $c_n$ sur 3 autres demi-diagonales sont
respectivement (en tournant dans le sens trigonom\'etrique) $$
d_2(n)=(2n)^2;\ d_3(n)=(2n)^2+2n;\ d_4(n)=(2n)^2+4n=(2n+1)^2-1 $$
donner les s\'eries g\'en\'eratrices (en $z$) de $d_i;\ i=1..4$.\\
4) Selon la position de $k$ par rapport \`a
$d_1(n)<d_2(n)<d_3(n)<d_4(n)$ donner la valeur de $c_k=(x_k,y_k)$
et montrer que $k\ra c_k$ est une bijection entre $\N$ et $\Z^2$.

\bsk
3) Reprendre le probl\`eme pr\'ec\'edent avec le bijection $\N\ra \N^2$ d\'efinie 
par le diagramme suivant :

%\begin{center}
%\begin{tabular}{ccccccc}
%     	&$\cdots$&\bu    	&\dla   	& \bu   	&\dla  	&\bu   	\\ 
%    	&       	&       	&       	&       	&       	& \dua  \\ 
%\bu     	& \dra  	& \bu   	& \dra  	& \bu   	&   	& \bu	\\ 
%\dua   	&       	&          &       	& \dda  & 	&\dua \\
%\bu        &  \dla	&\bu    	&       	& \bu    &          & \bu  	\\
%        	&       	&\dua   &       	& \dda 	&       	& \dua \\
%$\circ$ &\dra  	&\bu    	&       	& \bu  	& \dra  	& \bu   	\\
%\end{tabular}
%\end{center}

\begin{center}
\begin{tabular}{ccccccc}
\bu    	&       	&       &       	&       	&       &   \\ 
\dua   	& \dse   	&       &       	&       	&       &   \\ 
\bu    	&      	&\bu    &       	&       	&      	&      	\\ 
    	&  \dnw 	&       & \dse  	&       	&       &       \\ 
\bu   &       	& \bu   &       	& \bu   	&   		&    	\\ 
\dua  &  \dse 	&       & \dnw  	&       	& \dse  &  \\
\bu   &      		&\bu    &       	& \bu    	&       & \bu  	\\
      &  \dnw 	&       & \dse	  &      		& \dnw  &      \\
$\circ$&\dra  	&\bu    &       	& \bu  		& \dra  & \bu   	\\
\end{tabular}
\end{center}

\end{document}