\parindent=0mm
\input upsnum.tex
\def\comb#1#2{{#1\choose #2}}
\def\N{{\bf N}}
\def\Z{{\bf Z}}
\def\R{{\bf R}}
\def\Card{{\rm Card}}
{\bf Corrig\'e de l'\'epreuve X--E.S.P.C.I. PC* Math 1 2000}

\vskip 15mm
\centerline{\bf Premi\`ere partie}
\vskip 3mm
\item{\bf 1.} On a $\varphi_0(j)=1$ pour tout $j$. On peut supposer $k\ge 1$.
\item{$\longrightarrow$}Pour $j\in\{0,1,\ldots,k{-}1\}$, $j$ est 
racine de $\varphi_k$ donc $\varphi_k(j)=0$.

\item{$\longrightarrow$}Pour $j\ge k$, $\displaystyle \varphi_k(j)=
{1\over k!}j(j-1)\cdots(j-k+1)={1\over k!}{j!\over (j-k)!}=\comb jk$ 
;  ainsi $\varphi_k(j)=\comb jk$ pour tout $j\in\N$.

\item{$\longrightarrow$}Pour $j< k$ on pose $j=-p$ avec $p>0$, alors

$\displaystyle \varphi_k(j)={1\over k!}(-p)(-p{-}1)\cdots(-p{-}k{+}1)
={(-1)^k\over k!}p(p{+}1)\cdots(p{+}k{-}1)={(-1)^k\over 
k!}{p{+}k{-}1)!\over (p{-}1)!}
=(-1)^k\comb {p{+}k{-}1}k$\footnote{${}^{(1)}$}{Les $\varphi_k$ sont 
appel\'es polyn\^omes de Newton ; on
voit que $\varphi_k(j)$ est entier pour tout $j\in\Z$.}.


\vskip 3mm
\item{\bf 2.}On a $\displaystyle P_n =
\sum_{k=0}^n(-1)^k\varphi_k(X)\varphi_{n-k}(n-X)$ car 
$\varphi_{n-k}=0$ pour $k>n$ ; $\varphi_0=1$,
$\varphi_1=X$ et $\varphi_2={1\over 2}X(X-1)$.

{\bf a)} $\displaystyle P_0 
=\sum_{k=0}^0(-1)^k\varphi_k(X)\varphi_{n-k}(n-X)=\varphi_0(X)\varphi_{0}(N-X)=1$.

$\displaystyle P_1=\sum_{k=0}^1(-1)^k\varphi_k(X)\varphi_{n-k}(n-X)
=\varphi_0(X)\varphi_{1}(N-X)-\varphi_1(X)\varphi_{0}(N-X)=N-2X$

$\displaystyle 
P_2=\varphi_0(X)\varphi_{2}(N-X)-\varphi_1(X)\varphi_{1}(N-X)+\varphi_2(X)\varphi_{0}(N-X)
=2X^2-NX+{1\over 2}N(N{-}1)$

\vskip 1mm
{\bf b)} $\varphi_k$ est de degr\'e $k$ et de coefficient dominant 
${1\over k!}$.

Alors $\varphi_p(N{-}X)={1\over p!}(N{-}X)^p+a_{p-1}(N{-}X)^{p-1}+\cdots$
est de degr\'e $p$ et de coefficient dominant ${(-1)^p\over p!}$. 
Ainsi $(-1)^k\varphi_k(X)\varphi_{n-k}(n-X)$ est de degr\'e 
$k+(n{-}k)=n$
et de coefficient dominant $(-1)^k{1\over k!}{(-1)^{n-k}\over 
(n-k)!}={(-1)^n \over n!}\comb nk$.

Donc $P_n$ est de degr\'e au plus $n$ et le coefficient de $X^n$ est
$\sum_{k=0}^n{(-1)^n \over n!}\comb nk={(-1)^n \over 
n!}\sum_{k=0}^n\comb nk={(-1)^n \over n!}2^n$ :

$P_n$ est de degr\'e $n$ et de coefficient dominant ${(-1)^n \over n!}2^n$

\vskip 1mm
{\bf c)}$\displaystyle P_n(j) = 
\sum_{k=0}^N(-1)^k\varphi_k(j)\varphi_{n-k}(N-j)= 
\sum_{k=0}^N(-1)^k\comb jk\comb{N-j}{n-k}$
d'apr\`es {\bf 1.}.

\vskip 3mm
\item{\bf 3.} $\displaystyle f_j(u)
=\sum_{n=0}^NP_n(j)u^n=\sum_{n=0}^N \sum_{k=0}^N(-1)^k\comb 
jk\comb{N-j}{n-k}u^n
=\sum_{k=0}^N(-1)^k\comb jk\left(\sum_{n=0}^N \comb{N-j}{n-k}u^n\right)$

Or $\comb jk=0$ pour $k>j$, $\comb{N-j}{n-k}=0$ pour $n<k$  et 
$\comb{N-j}{p}=0$ pour $p\ge N-j$ donc

$\eqalign{f_j(u)
&=\sum_{k=0}^j(-1)^k\comb jk\left(\sum_{n=k}^N \comb{N-j}{n-k}u^n\right)
=\sum_{k=0}^j(-1)^k\comb jk\left(\sum_{p=0}^{N-k} 
\comb{N-j}pu^{p+k}\right)\hbox{ avec }N{-}j\le N{-}k\cr
&=\sum_{k=0}^j(-1)^k\comb jku^k\left(\sum_{p=0}^{N-j} \comb{N-j}pu^{p}\right)
=\sum_{k=0}^j(-1)^k\comb jku^k(1+u)^{N-j}=(1-u)^j(1 +u)^{N-j}{.}
}$

\vskip 3mm
\item{\bf 4.}{\bf a)} $\eqalign{ F(u, v)
&=\sum_{j=0}^n\comb Nj f_j(u)f_j(v)
=\sum_{j=0}^n\comb Nj\bigl((1{-}u)(1{-}v)\bigr) 
^j\bigl((1{+}u)(1{+}v)\bigr) ^{N-j}\cr
&=\bigl((1{-}u)(1{-}v)+(1{+}u)(1{+}v)\bigr)^N
=(2+2uv)^N=2^N(1+uv)^N}$

\vskip 1mm
\vfill
\penalty-500
{\bf b)} On suppose $0\le b< a\le N$ : on a
$\displaystyle {\partial^{a}F \over \partial u^a}(u,v)=2^Nv^a{N! 
\over (N-a)!}(1+uv)^{N-a}$.

On pose  $P_{a,u}(v)={\partial^{a}F \over \partial u^a}(u,v)$ 
consid\'er\'e comme polyn\^ome en $v$.

$0$ est racine d'ordre $a$ de $P_{a,u}$ donc, pour $b\le a$, 
$0=\bigl(P_{a,u}\bigr)^{(b)}(0)$.

Ainsi $\displaystyle {\partial^{a+b}F
\over \partial u^a\partial v^b}(u,0)=0$ pour tout $u$ ; en 
particulier $\displaystyle {\partial^{a+b}F \over \partial
u^a\partial v^b}(0,0)=0$.

Dans le cas $a< b$ on a la m\^eme d\'emonstration. Pour le cas $a=b$ 
on va appliquer la r\`egle de Leibniz :

$\eqalign{{\partial^{2a}F\over \partial u^a\partial v^a}(0,0)
&={\partial^{a}\over \partial v^a}\bigl(2^Nv^a{N! \over (N-a)!}(1+uv)^{N-a}\bigr)(0,0)\cr
&=2^N{N! \over (N-a)!}\sum_{k=0}^a\comb ak{\partial^{k}v^a\over 
\partial v^k}(0,0)
{\partial^{a-k}(1+uv)^{N-a}\over \partial v^{a-k}}(0,0)
\hbox{ or }{\partial^{k}v^a\over \partial v^k}(0,0)=0\hbox{ pour }k<a\cr
&=2^N{N! \over (N-a)!}\comb aa{\partial^{a}v^a\over \partial v^a}(0,0)
(1+uv)^{N-a}(0,0)=2^N{N! a!\over (N-a)!}
}$

\vskip 3mm
\item{\bf 5.} {\bf a)}On a $\bigl<P\bigm |Q\bigr>=\bigl<Q\bigm 
|P\bigr>$, $\bigl<P\bigm |aQ+bR\bigr>=
a\bigl<P\bigm |Q\bigr>+b\bigl<P\bigm |R\bigr>$ et
$\bigl<P\bigm |P\bigr>=\sum_{j=0}^N \comb Nj \bigl(P(j)\bigr)^2\ge 0$ 
car $\comb Nj>0$. Si on a $\bigl<P\bigm |P\bigr>=0$
alors $\bigl(P(j)\bigr)^2= 0$ pour tout $j\in\{0,1,\ldots,N\}$ donc 
$P$ admet $N$ racines distinctes ; comme $P$
appartient  \`a $\R_N[X]$ on en d\'eduit que $P=0$.

Ainsi $\bigl<.\bigm |.\bigr>$ est un produit scalaire.

\vskip 1mm
{\bf b)} La d\'efinition $f_j(u)=\sum_{n=0}^N P_n(j)u^n$ implique
$\displaystyle {d^nf_j \over u^n}(0)=n!P_n(j)$. Ainsi
$${\partial^{a+b}F \over \partial u^a\partial v^b}(u,v)
={\partial^{b} \over \partial v^b}\sum_{j=0}^N\comb 
Nj{\partial^{a}f_j(u)f_j(v) \over \partial u^a}(u,v)
={\partial^{b} \over \partial v^b}\sum_{j=0}^N\comb Nj{d^{a}f_j\over 
d u^a}(u)f_j(v)
=\sum_{j=0}^N\comb Nj{d^{a}f_j\over d u^a}(u){d^{b}f_j\over d v^b}(v)$$
donc $\displaystyle {\partial^{a+b}F \over \partial u^a\partial v^b}(0,0)=
\sum_{j=0}^N\comb Nj{d^{a}f_j\over d u^a}(0){d^{b}f_j\over d v^b}(0)
=\sum_{j=0}^N\comb Nja!P_a(j)b!P_b(j)=a!b!\bigl<P_a\bigm |P_b\bigr>$.

D'apr\`es la question {\bf 4. b)} on en d\'eduit 
que\footnote{${}^{(2)}$}{Et aussi $\bigl<P_a\bigm |P_a\bigr>=2^N\comb 
Na$.}
$\bigl<P_a\bigm |P_b\bigr>=0$ pour $a\ne b$ : la famille est orthogonale.

\vskip 3mm
\item{\bf 6.} On a $\displaystyle {d f_j \over du}(u)=\sum_{n=1}^N 
nP_n(j)u^{n-1}$ donc
$\displaystyle (1-u^2){d f_j \over du}(u)=\sum_{n=1}^N 
nP_n(j)u^{n-1}-\sum_{n=1}^N nP_n(j)u^{n+1}$ :

le coefficient de $u^n$ dans $ (1-u^2){d f_j \over du}(u)$ est donc 
$(n+1)P_{n+1}(j)-(n-1)P_{n-1}(j)$
pour $1\le n\le N-1$.

De plus, pour $1\le j\le N-1$, ${d f_j \over 
du}(u)=(-j)(1-u)^{j-1}(1+u)^{N-j}+(N-j)(1-u)^{j}(1+u)^{N-j-1}$ donc

$(1-u^2){d f_j \over 
du}(u)=\bigl(-j(1+u)+(N-j)(1-u)\bigr)f_j(u)=\bigl((N-2j)-Nu\bigr)f_j(u)$ 
:

le coefficient de $u^n$  dans $ (1-u^2){d f_j \over du}(u)$ est aussi 
$(N-2j)P_n(j)-NP_{n-1}(j)$.

Pour $j=0$, $(1{-}u^2){d f_0 \over du}(u)
%=(1{-}u^2)\bigl(N(1{+}u)^{N-1}\bigr)
=N(1-u)f_0(u)$ : le coefficient de $u^n$ est $NP_n(0)-NP_{n-1}(0)$.

Pour $j=N$, $(1{-}u^2){d f_N \over du}(u)
%=(1{-}u^2)\bigl(N(1{+}u)^{N-1}\bigr)
=-N(1+u)f_N(u)$ : le coefficient de $u^n$ est $-NP_n(N)-NP_{n-1}(N)$.

On a donc, pour tout $j\in\{0,1,\ldots,N\}$, 
$(N-2j)P_n(j)-NP_{n-1}(j)=(n+1)P_{n+1}(j)-(n-1)P_{n-1}(j)$
donc le polyn\^ome $Q=(n+1)P_{n+1}-(N-2X)P_n+(N-n+1)P_{n-1}$ s'annule 
en tout $j\in\{0,1,\ldots,N\}$.

On a $P_{k}\in \R_k[X]$ donc $Q\in\R_{n+1}[X]$ ; de plus le 
coefficient de $X^{n+1}$ est, d'apr\`es la question {\bf 2. b)},
$(n+1)(-1)^{n+1}{2^{n+1}\over (n+1)!}+2.(-1)^n{2^n \over n!}=0$ donc 
$Q$ appartient \`a $\R_n[X]$.

Or $Q$ admet au moins $n{+}1$ racines distinctes et $Q\in\R_n[X]$ : 
on en d\'eduit $Q=0$.

Ainsi, pour tout $m$ tel que $1 \le  m \le  N-1$,
$(m + 1)P_{m+1}(X) - (N-2X)P_m(X) + (N-m + 1)P_{m-1}(X)= 0$.

\vfill
\penalty -500
\vskip 5mm
\centerline{\bf Deuxi\`eme partie}
\vskip 3mm
\item{\bf 7.}{\bf a)} $d(I, J) = 0$ est \'equivalent \`a $I\triangle 
J=\emptyset$.

On a $I\triangle J=\bigl(I\cup J\bigr)\setminus\bigl(I\cap J\bigr)$ 
avec $\bigl(I\cap J\bigr)\subset \bigl(I\cup J\bigr)$
donc $d(I, J) = 0$ est \'equivalent \`a $\bigl(I\cap 
J\bigr)=\bigl(I\cup J\bigr)$.

Or $\bigl(I\cap J\bigr)\subset I\subset \bigl(I\cup J\bigr)$ et 
$\bigl(I\cap J\bigr)\subset J\subset \bigl(I\cup J\bigr)$
donc la condition $\bigl(I\cap J\bigr)=\bigl(I\cup J\bigr)$ implique $I=J$.

Inversement si $I=J$ alors $I\triangle J=\emptyset$ donc 
$\bigl[d(I,J)=0\bigr]\iff \bigl[I=J\bigr]$.

\vskip 1mm
Si $d(I, J) = 1$ alors $I\triangle J$ est un singleton, que l'on note 
$\{a\}$. On suppose, par exemple, que $a$
appartient \`a $I$.

Alors $a$ ne peut pas appartenir \`a $J$. De plus $\bigl(I\cup 
J\bigr)=\bigl(I\cap J\bigr)\cup \{a\}$.

On a donc $\bigl(I\cap J\bigr)\subset J\subset \bigl(I\cup 
J\bigr)=\bigl(I\cap J\bigr)\cup \{a\}$ avec $a\notin J$
donc $J=\bigl(I\cap J\bigr)$ et

$\bigl(I\cap J\bigr)\subset I\subset \bigl(I\cup J\bigr)=\bigl(I\cap 
J\bigr)\cup \{a\}$ avec $a\in I$
donc $J=\bigl(I\cap J\bigr)\cup \{a\}=J\cup\{a\}$.

Inversement si $I=J\cup\{a\}$ avec $a$ n'appartenant pas \`a $J$ alors
$I\triangle J=\{a\}$ donc $d(I,J)=1$.

$\bigl[d(I,J)=1\bigr]\iff \bigl[I=J\sqcup \{a\}\hbox {ou }J=I\sqcup 
\{a\}\bigr]$ o\`u le symbole
$\sqcup$ signifie une union disjointe.
\vskip 1mm
{\bf b)} D\'etaillons $I\triangle J$ : si $I=\bigl(I\cap 
J\bigr)\sqcup I'$ et $J=\bigl(I\cap J\bigr)\sqcup J'$
alors $I\cup J=\bigl(I\cap J\bigr)\sqcup I'\sqcup J'$ donc 
$I\triangle J=I'\sqcup J'$.

Alors $\bigl(I\triangle J\bigr)\cap I=\bigl(I'\sqcup 
J'\bigr)\cap\bigl((I\cap J)\sqcup I'\bigr)=I'$ car
$\bigl(I\cap J\bigr)\cap J'=\emptyset$.

On en d\'eduit que $\bigl(I\triangle J\bigr)\triangle I=J'\sqcup 
\bigl(I\cap J\bigr)=J$ donc
$d\bigl((I\triangle J),I\bigr)=\Card J$.

\vskip 3mm
\item{\bf 8.} On va classer les parties $A$ telles que $d(A,I)=1$.

\item{$\longrightarrow$} Si $A=I\sqcup \{a\}$ avec $a$ appartenant \`a $J$.
On pose $I=\bigl(I\cap J\bigr)\sqcup I'$, $J=\bigl(I\cap 
J\bigr)\sqcup J'$ et $J'=J''\sqcup\{a\}$.

On a $A\cap J=\bigl(I\cup \{a\}\bigr)\cap J =\bigl(I\cap 
J\bigr)\cup\bigl(\{a\}\cap J\bigr)
=\bigl(I\cap J\bigr)\sqcup\{a\}$ car $a\notin \bigl(I\cap 
J\bigr)\subset I$ donc

$A=I\sqcup\{a\}=\bigl(I\cap J\bigr)\sqcup I'\sqcup\{a\}=\bigl(A\cap 
J\bigr)\sqcup I'$
et $J=\bigl(I\cap J\bigr)\sqcup J''\sqcup\{a\}=\bigl(A\cap J\bigr)\sqcup J''$.

On en d\'eduit que $A\triangle J=I'\sqcup J''$ et $I\triangle 
J=I'\sqcup J'=I'\sqcup J''\sqcup\{a\}$
donc $\Card\bigl(I\triangle J\bigr)=\Card\bigl(A\triangle J\bigr)+1$.

\item{$\longrightarrow$} Si $A=I\sqcup \{a\}$ avec $a$ n'appartenant 
pas \`a $J$.
On pose $I=\bigl(I\cap J\bigr)\sqcup I'$ et $J=\bigl(I\cap J\bigr)\sqcup J'$.

On a $A\cap J=\bigl(I\cup \{a\}\bigr)\cap J =\bigl(I\cap 
J\bigr)\cup\bigl(\{a\}\cap J\bigr)
=\bigl(I\cap J\bigr)$ car $\{a\}\cap J=\emptyset$ donc

$A=I\sqcup\{a\}=\bigl(I\cap J\bigr)\sqcup I'\sqcup\{a\}=\bigl(A\cap 
J\bigr)\sqcup I'\sqcup\{a\}$
et $J=\bigl(I\cap J\bigr)\sqcup J'=\bigl(A\cap J\bigr)\sqcup J'$.

On en d\'eduit que $A\triangle J=I'\sqcup\{a\}\sqcup J'=I\triangle 
J\sqcup\{a\}$
donc $\Card\bigl(A\triangle J\bigr)=\Card\bigl(I\triangle J\bigr)+1$.

\item{$\longrightarrow$} Si $I=A\sqcup \{a\}$ avec $a$ appartenant 
\`a $J$ on est dans le premier cas en \'echangeant les
r\^oles de $A$ et de $I$ donc $\Card\bigl(A\triangle 
J\bigr)=\Card\bigl(I\triangle J\bigr)+1$.

\item{$\longrightarrow$} Si $I=A\sqcup \{a\}$ avec $a$ n'appartenant 
pas \`a $J$ on est dans le deuxi\`eme cas en
\'echangeant les r\^oles de $A$ et de $I$ donc $\Card\bigl(I\triangle 
J\bigr)=\Card\bigl(A\triangle J\bigr)+1$.

\vskip 1mm
Ainsi si $d(A,I)=1$ alors $d(A,J)=d(I,J)\pm 1$ donc $\gamma_j^k=0$ si 
$j\notin \{k-1,k+1\}$.

On a $d(A,J)=d(I,J)-1$ si et seulement si

\item{---}$A=I\sqcup\{a\}$ avec $a$ appartenant \`a $J$ ; comme $a$ 
n'appartient pas \`a $I$ on choisit $a$  dans
$J\setminus I$

\item{---}$I=A\sqcup\{a\}$ avec $a$ n'appartenant pas \`a $J$ ; comme 
$a$ appartient \`a $I$ on choisit $a$  dans
$I\setminus J$

Les ensembles $A$ tels que $d(A,J)=d(I,J)-1$ sont donc d\'efinis par 
un \'el\'ement de $J\setminus I\sqcup
I\setminus J=I\triangle J$ ;

il y a $\Card\bigl(I\triangle J\bigr)$ choix distincts possibles donc 
$\gamma_{k-1}^k=d(I,J)=k$.

On a $d(A,J)=d(I,J)+1$ si et seulement si

\item{---}$A=I\sqcup\{a\}$ avec $a$ n'appartenant pas \`a $J$ ; comme 
$a$ n'appartient pas \`a $I$ on choisit $a$  dans
$E\setminus (I\cup J)$

\item{---}$I=A\sqcup\{a\}$ avec $a$ appartenant \`a $J$ ; comme $a$ 
appartient \`a $I$ on choisit $a$  dans
$I\cap J$

Les ensembles $A$ tels que $d(A,J)=d(I,J)-1$ sont donc d\'efinis par 
un \'el\'ement de $E\setminus I\triangle J$ ;

il y a $N-\Card\bigl(I\triangle J\bigr)$\footnote{${}^{(3)}$}{Il est 
normal de trouver une somme \'egale \`a $N$.
Pour fabriquer $A$ tel que $d(I,A)=1$ on choisit un \'el\'ement de 
$E$ : s'il appartient \`a $I$ on l'enl\`eve,
s'il n'appartient pas \`a $I$ on l'ajoute.} choix
distincts possibles donc $\gamma_{k+1}^k=N-d(I,J)=N-k$.

\vfill
\penalty -1000
\vskip 5mm
\centerline{\bf Troisi\`eme partie}
\vskip 3mm
\item{\bf 9.}{\bf a)} $d(I,J)$ est le cardinal d'une partie de $E$ 
donc $d(I,J)\le \Card E=N$.
Pour $n> N$ $A_n$ est la matrice nulle.

$d(I,J)=0$ si et seulement si $I=J$ donc $A_0={\cal J}$.

\vskip 1mm
{\bf b)} On a $A_1A_m=C$ avec
$\displaystyle (C)_{pq}=\sum_{r=1}^{2^N}(A_1)_{pr}(A_m)_{rq}$. Comme 
les coefficients des $A_n$ sont \'egaux  \`a 1 ou 0
$(C)_{pq}$ est le nombre d'entiers $r$ tels que 
$(A_1)_{pr}=(A_m)_{rq}=1$ c'est--\`a--dire le nombre de parties $I_r$ 
de
$E$ telles que $d(I_p,I_r)=1$ et $d(I_r,I_q)=m$ ; avec les notations 
du {\bf 8.} on a $(C)_{pq}=\gamma_m^k$ avec
$k=d(I_p,I_q)$.

Pour $k=d(I_p,I_q)\ne m\pm 1$ on a $(C)_{pq}=0$, pour 
$d(I_p,I_q)=m-1$ on a $(C)_{pq}=\gamma_m^{m-1}=N-m+1$ et pour
$d(I_p,I_q)=m+1$ on a $(C)_{pq}=\gamma_m^{m+1}=m+1$. Ainsi 
$A_1A_m=C=(N-m+1)A_{m-1}+(m+1)A_{m+1}$.
\vskip 3mm
\item{\bf 10.} $P_0=1$ donc $P_0(A)={\cal J}=A_0$. $P_1=N-2X$ donc 
$P_1(A)=N{\cal J}-2A=N{\cal J}-2{1\over 2}(N{\cal J}-A_1)
=A_1$.

Si on suppose $P_n(A)=A_n$ et $P_{n-1}(A)=A_{n-1}$ pour $1\le n\le 
N-1$ alors, en utilisant {\bf 6.},

$\eqalign{(n+1)P_{n+1}(A)
&=\bigl(N{\cal J}-2A\bigr)P_n(A)-(N-n+1)P_{n-1}(A)
=A_1A_n-(N-n+1)A_{n-1}\cr
&=(N-n+1)A_{n-1}+(n+1)A_{n+1}-(N-n+1)A_{n-1}=(n+1)A_{n+1}\hbox{ 
d'apr\`es }{\bf 9.b)}\cr
}$

Ainsi $P_{n+1}(A)=A_{n+1}$ donc, par r\'ecurrence, $P_n(A)=A_n$ pour 
tout entier $n\in\{0,1,\ldots,N\}$.

\vskip 3mm
\item{\bf 11.} On classe les parties $J$ de $E$ de cardinal $j$ par 
le cardinal de leur intersection
avec $I$ :

si $\Card(J)=j$ et $\Card\bigl(I\cap J\bigr)=k$ alors $J=\bigl(I\cap 
J\bigr)\sqcup J'$ avec

$I\cap J$ sous--ensemble \`a $k$ \'el\'ements de $I$ donc peut \^etre 
choisi parmi $\comb ik$ possibilit\'es et

$J'$ sous--ensemble \`a $j-k$ \'el\'ements de $E\setminus I$ donc 
peut \^etre choisi parmi $\comb {N-i}{j-k}$ possibilit\'es.

il y a donc $\comb ik\comb {N-i}{j-k}$ tels sous--ensembles : 
$\displaystyle \kern -8mm \sum_{\textstyle{J\in{\cal P}(E)
\atop \Card J=j,\ \Card(I\cap J)=k}}\kern -11mm(-1)^{\Card(I\cap 
J)}=\comb ik\comb {N-i}{j-k}(-1)^k$.

d'o\`u $\displaystyle \kern -2mm\sum_{\textstyle{J\in{\cal P}(E) 
\atop \Card J=j}}\kern -2mm(-1)^{\Card(I\cap J)}
=\sum_{k=0}^i\kern -8mm\sum_{\textstyle{J\in{\cal P}(E) \atop \Card 
J=j,\ \Card(I\cap J)=k}}\kern -11mm
(-1)^{\Card(I\cap J)}
=\sum_{k=0}^i\comb ik\comb {N-i}{j-k}(-1)^k=P_j(i)$

d'apr\`es {\bf 2. c)} car $\comb ik=0$ pour $k>i$.

\vskip 3mm
\item{\bf 12.}{\bf a)} On \'ecrit toujours $I=\bigl(I\cap 
J\bigr)\sqcup I'$ et $J=\bigl(I\cap J\bigr)\sqcup j'$.
Alors $\bigl(I\triangle J\bigr)\cap K=\bigl(I'\sqcup J'\bigr)\cap 
K=\bigl(I'\cap K\bigr)\sqcup \bigl(J'\cap K\bigr)$.

Ainsi $(-1)^{\Card((I\triangle J)\cap K)}=(-1)^{\Card(I'\cap 
K)}(-1)^{\Card(J'\cap K)}$.

De plus $I\cap K=\bigl((I\cap J)\sqcup I'\bigr)\cap K=\bigl(I\cap 
J\cap K\bigr)\sqcup \bigl(I'\cap K\bigr)$ ;
de m\^eme $J\cap K=\bigl(I\cap J\cap K\bigr)\sqcup \bigl(I'\cap K\bigr)$.

$\eqalign{\hbox{Ainsi  }(-1)^{\Card(I\cap K)}(-1)^{\Card(J\cap K)}
&=(-1)^{\Card(I\cap J\cap K)}(-1)^{\Card(I'\cap K)}
(-1)^{\Card(I\cap J\cap K)}(-1)^{\Card(J'\cap K)}\cr
&=(-1)^{\Card(I'\cap K)}(-1)^{\Card(J'\cap K)}
=(-1)^{\Card((I\triangle J)\cap K)}{.}\cr
}$

{\bf b)} On note $A=I\triangle J$ et $a=\Card A$. $a=0$ si et 
seulement si $I=J$. On utilise {\bf 11.} et {\bf 3.}.

\vskip 1mm$\eqalign{\sum_{K\in{\cal P}(E)}(-1)^{\Card(I\cap 
K)}(-1)^{\Card(J\cap K)}
&=\sum_{K\in{\cal P}(E)}(-1)^{\Card(A\cap K)}
=\sum_{k=0}^n\sum_{\textstyle{K\in{\cal P}(E) \atop \Card 
K=k}}(-1)^{\Card(A\cap K)}\cr
&=\sum_{k=0}^nP_k(a)=f_a(1)=(1-1)^a(1+1)^{N-a}=\left\{\matrix{2^N&\hbox{ 
si }a=0\cr
0&\hbox{ sinon.}\hfill\cr}\right.
}$

\vskip 3mm
\item{\bf 13.} {\bf a)} Les coefficients de $B_k$ sont $(B_k)_{pq}={1\over 
2^N}\sum_{n=0}^N P_k(n)(A_n)_{pq}$
or $(A_n)_{pq}=0$ pour tout $n$ sauf $(A_n)_{pq}=1$ pour 
$n=d(I_p,I_q)$ : on a donc
$(B_k)_{pq}={1\over 2^N}P_k\bigl(d(I_p,I_q)\bigr)$. De plus 
$I_p\triangle I_q$ est de cardinal
$d(I_p,I_q)$ donc, d'apr\`es {\bf 11.}, $\displaystyle (B_k)_{pq}
={1\over 2^N}\kern -2mm\sum_{\textstyle{K\in{\cal P}(E) \atop \Card 
K=k}}\kern -2mm(-1)^{\Card((I_p\triangle I_q)\cap K)}
={1\over 2^N}\kern -2mm\sum_{\textstyle{K\in{\cal P}(E) \atop \Card 
K=k}}\kern -2mm(-1)^{\Card(I_p\cap K)}
(-1)^{\Card(I_q\cap K)}$.
Si on note $B_k.B_l=C$ alors 
$(C)_{pq}=\sum_{r=1}^{2^N}(B_k)_{pr}(B_l)_{rq}$ puis

$\eqalign{(C)_{pq}
&=\sum_{r=1}^{2^N}\left({1\over 2^N}\kern 
-2mm\sum_{\textstyle{K\in{\cal P}(E) \atop \Card K=k}}\kern -2mm
(-1)^{\Card(I_p\cap K)} (-1)^{\Card(I_r\cap K)}\right)\left({1\over 
2^N}\kern -2mm
\sum_{\textstyle{L\in{\cal P}(E) \atop \Card L=l}}\kern -2mm
(-1)^{\Card(I_r\cap L)} (-1)^{\Card(I_q\cap L)}\right)\cr
&={1\over (2^N)^2}\sum_{I\in{\cal P}(E)}\sum_{\textstyle{K\in{\cal 
P}(E) \atop \Card K=k}}
\sum_{\textstyle{L\in{\cal P}(E) \atop \Card L=l}}\kern -2mm
(-1)^{\Card(I_p\cap K)} (-1)^{\Card(I\cap K)}(-1)^{\Card(I\cap L)} 
(-1)^{\Card(I_q\cap L)}\cr
&={1\over (2^N)^2}\kern -1mm\sum_{\textstyle{K\in{\cal P}(E) \atop \Card K=k}}
\sum_{\textstyle{L\in{\cal P}(E) \atop \Card L=l}}\kern 
-1mm(-1)^{\Card(I_p\cap K)} (-1)^{\Card(I_q\cap L)}
\underbrace{\sum_{I\in{\cal P}(E)} (-1)^{\Card(I\cap 
K)}(-1)^{\Card(I\cap L)}}_{=0\hbox{ si }K\ne L\hbox{ d'apr\`es
{\bf 12. b)}}}\cr
}$

Or on ne peut avoir $K=L$ que si $k=l$ donc $B_k.B_l=0$ si $k\ne l$ 
et, pour $k=l$,

$\displaystyle (C)_{pq}=
{1\over (2^N)^2}\kern -2mm\sum_{\textstyle{K\in{\cal P}(E) \atop \Card K=k}}
\kern -1mm(-1)^{\Card(I_p\cap K)} (-1)^{\Card(I_q\cap K)}2^N=(B_k)_{pq}$
donc $(B_k)^2=B_k$.

\vskip 1mm
{\bf b)} $B_k$ est donc une matrice de projecteur donc ${\rm 
rg}(B_k)={\rm tr}(B_k)$.

Or les termes diagonaux de $A_n$ sont nuls pour $n\ne 0$ car 
$d(I,I)=0$ donc ${\rm tr}(A_n)=0$ et ${\rm tr}(A_0)={\rm
tr}({\cal J})=2^N$ d'o\`u
$\displaystyle {\rm tr}(B_k)={1\over 2^N}\sum_{n=0}^NP_k(n){\rm 
tr}(A_n)={1\over 2^N}P_k(0)2^N=P_k(0)
=\sum_{i=0}^N (-1)^i\comb 0i\comb{N-0}{k-i}=\comb Nk$ d'apr\`es {\bf 2.c)}.

\vskip 3mm
\item{\bf 14.}{\bf a)} Les $B_k$ sont des projecteurs ; on note $E_k$ 
l'image de $B_k$ (dans $\R^{2^N}$).

Si $0_E=X_0+X_1+\cdots+X_N$ avec $X_k$ appartenant \`a $E_k$ alors 
$X_k=B_k.X_k$ donc

$0_E=B_l(0_E)=\sum_{k=0}^N B_l(x_k)=\sum_{k=0}^N 
B_l.B_k.X_k=B_l.X_l=X_l$ car $B_l.B_k=0$ pour $k\ne l$.

Les images des $B_k$ sont en somme directe ; de plus la somme des 
dimensions est

$\sum_{k=0}^N{\rm rg}(B_k)=\sum_{k=0}^N\comb Nk=2^N$ =: on a 
$\R^{2^N}=E_0\oplus E_1\oplus\cdots\oplus E_N$.

\vskip 1mm
On va donc exprimer les $A_n$ comme combinaisons lin\'eaires des 
$B_k$ ce qui donnera la diagonalisation.

\vskip 1mm
$\displaystyle \sum_{k=0}^N\alpha_k B_k
=\sum_{k=0}^N\alpha_k\left({1\over 2^N}\sum_{n=0}^NP_k(n)A_n\right)
=\sum_{n=0}^N\left(\sum_{k=0}^N{\alpha_k\over 2^N}P_k(n)\right)A_n
=\sum_{n=0}^NP(n)A_n$ o\`u $\displaystyle P=\sum_{k=0}^N 
{\alpha_k\over 2^N}P_k$.

Si $P=L_i$ le polyn\^ome de Lagrange tel que
$L_i(j)=\delta_{i,j}$ pour $j\in E$ on a $\displaystyle 
\sum_{k=0}^N\alpha_k B_k
=\sum_{k=0}^NL_i(n)A_n=A_i$.

\vskip 1mm
Il reste \`a d\'ecomposer les polyn\^omes $L_i$.

\vskip 1mm
La famille $\bigl(P_0,P_1,\ldots,P_N\bigr)$ est une base orthogonale 
de $\R_N[X]$
donc la d\'ecomposition d'un vecteur dans cette base est
$\displaystyle P=\sum_{k=0}^N{\bigl<P\bigm |P_k\bigr>\over 
\bigl<P_k\bigm |P_k\bigr>}P_k$. On a vu que
$\bigl<P_k\bigm |P_k\bigr>=2^N\comb Nk$.

$\displaystyle \bigl<L_i\bigm |P_k\bigr>=\sum_{n=0}^N\comb Nn 
L_i(n)P_k(n)=\comb NiP_k(i)$ donc
$\displaystyle L_i=\sum_{k=0}^N{\comb NiP_k(i) \over 2^N\comb Nk}P_k$.

Ainsi, en choisissant $\alpha_k={\comb NiP_k(i) \over \comb Nk}$ on a
$\sum_{k=0}^N\alpha_kB_k=A_i$ ;

les valeurs propres de $A_i$ sont les r\'eels ${\comb NiP_k(i) \over 
\comb Nk}$ pour $k$ appartenant \`a $E$

et  les sous--espaces propres associ\'es sont les images des $B_k$.

\vskip 1mm
{\bf b)}Pour $i=1$ les valeurs propres de $A_1$ sont les r\'eels 
${\comb N1P_k(1) \over \comb Nk}$.

Or $\displaystyle P_k(1)=\sum_{n=0}^N(-1)^n\comb 1n \comb 
{N{-}1}{k{-}n}=\sum_{n=0}^1(-1)^n\comb 1n \comb {N{-}1}{k{-}n}
=\comb {N{-}1}{k}-\comb {N{-}1}{k{-}1}={(N-1)!(N-2k) \over k!(N-k)!}$.

Les valeurs propres sont donc les entiers $N-2k$ pour $k$ appartenant 
\`a $E$ qui sont distinctes
donc les sous--espaces propres sont les ${\rm Im}(B_k)$ qui sont de 
dimensions ${\rm rg}(B_k)=\comb Nk$

\end

