Suite et ensemble de parties — Les-mathematiques.net The most powerful custom community solution in the world

Suite et ensemble de parties

Modifié (16 Feb) dans Combinatoire et Graphes
Bonsoir
Un exercice de sup que je trouve super intéressant.

Exercice (*).
Pour toute partie $A$ de $\N^{*}$, on note $p(A)$ le produit des éléments de $A$. 
Et pour tout $n \in \N^{*}$, on pose : $u_n = \displaystyle\sum_{A \in \mathcal P([|1,n|])} \dfrac{1}{p(A)}$.
Donner une expression simple de $u_n$. 

J'ai calculé les premiers termes.
  • Pour $n=1$, on a $\mathcal P( \{1\} )= \{ \emptyset, \{1 \} \}$. Donc $u_1= 2$.
  • Pour $n=2$, on a $\mathcal P( \{1,2\} )= \{ \emptyset, \{1 \} , \{2 \} , \{1,2 \} \}$. Donc $u_2 = 1+1+ \dfrac{1}{2}+\dfrac{1}{2}=3$.
  • Pour $n=3$, on a $\mathcal P( \{1,2,3\} )= \{ \emptyset, \{1 \} , \{2 \} , \{3\},  \{1,2 \} , \{1,3\}, \{2,3\}, \{1,2,3 \} \}$. Donc $u_3=4$.
Pour le cas général, j'a l'impression qu'il faut utiliser l'idée classique suivante :  
$u_{n+1}=\displaystyle\sum_{A \in \mathcal P([1,n+1|) \\ n+1 \in A} \dfrac{1}{p(A)}+\displaystyle\sum_{A \in \mathcal P([1,n+1|) \\ n+1 \notin A} \dfrac{1}{p(A)}$ .
Mais après je bloque. 

Réponses

  • Peut-être écrire une relation de récurrence entre $u_{n+1}$ et $u_n$ ?
  • Oui c'est ce que j'essaie de faire.
    Je crois que c'est le raisonnement ultra classique sur les parties de $[|1,n+1|]$ qui contiennent $n+1$ et celles qui ne contiennent pas $n+1$.

    L'application : 
    $\phi : \mathcal P([|1,n+1|] \ \text{qui ne contiennent pas} \ \ n+1 \longrightarrow \mathcal P([|1,n|])$ définie par $\phi(A)=A$ est bijective.

    Donc $\displaystyle\sum_{A \in \mathcal P([|1,n+1|]) \\ n+1 \notin A} \dfrac{1}{p(A)}=\displaystyle\sum_{A \in \mathcal P([|1,n|])} \dfrac{1}{p(A)}=u_n$.

    Pour l'autre somme j'ai plus de difficulté à trouver une bijection.
  • Modifié (15 Feb)
    NB : pour $n=0$, $u_0=1$ sans problème métaphysique.
    Dans l'idée classique, on continue en considérant qu'une partie qui contient $n+1$, c'est la réunion de $\{n+1\}$ et d'une partie de $\{1,\dots,n\}$. Ça tombe bien parce que si $A$ et $B$ sont disjointes, $p(A\cup B )$ s'exprime facilement en fonction de $p(A)$ et $p(B)$ !
  • Modifié (16 Feb)
    Merci ! 
    Si $A$ et $B$ sont disjoints, alors $P(A\cup B )=p(A) p(B)$.
    Je ne suis pas loin de trouver la bijection, ton indication m'a bien aidé  :)
  • Modifié (16 Feb)
    L'application : 
    $\psi : \mathcal P([|1,n+1|] \ \text{qui contiennent} \ \ n+1 \longrightarrow \mathcal P([|1,n|]) \cup \{n+1 \}$ définie par $\psi(X)= X \backslash \{n+1\} \cup \{n+1 \} $ est bijective.

    Donc $\displaystyle\sum_{A \in \mathcal P([|1,n+1|]) \\ n+1 \in A} \dfrac{1}{p(A)}=\displaystyle\sum_{A \in \mathcal P([|1,n|]) } \dfrac{1}{(n+1)p(A)}=\dfrac{u_n}{n+1}$ car $p(A  \cup \{n+1 \} )=p(A) \times p( \{n+1 \})$.
    Ainsi : $u_{n+1}=u_n + \dfrac{u_n}{n+1}$
    $u_{n+1}=\dfrac{n+2}{n+1} u_n$.
    La suite $\left(\dfrac{u_n}{n+1}\right)_{n \in \N^{*}}$ est constante donc $\boxed{\forall n \in \N^{*} ,\ u_n = n+1}$.
  • Modifié (16 Feb)
    L’ensemble d’arrivée de ta « bijection » est pour le moins étrange.
  • Car on ne peut pas faire d'union entre un ensemble d'ensemble et un ensemble ? 

    Il faudrait prendre $\{ X \in \mathcal P([|1,n|]) \} \cup \{ n+1 \}$? 
  • Regarde les cardinaux de tes ensembles de départ et d'arrivée et tu verras bien que $\psi$ ne peut être une bijection.
  • Le cardinal de l'ensemble des parties de $[|1,n+1|]$ qui ne contiennent pas $n+1$ est $2^n$.
    Donc le cardinal des parties de $[|1,n+1|]$ qui contiennent $n+1$ est de cardinal $2^{n+1}-2^n$.

    Le cardinal de $\mathcal P([|1,n|]) \cup \{n+1 \}$ est $2^n +1$. Il y a un problème.
  • Modifié (16 Feb)
    Les éléments de $\mathcal P([|1,n|])$, c'est des ensembles d'entiers  alors que l'unique élément de $\{n+1 \}$, c'est un entier donc ça n'a pas trop de sens de prendre la réunion des deux (sauf si on considère les entiers comme étant eux même des ensembles. . .).
    Bref, si on considère les parties de $[|1,n+1|]$ qui contiennent l'entier $n\!+\!1$, ce n'est absolument pas ta réunion et c'est bien évidement un ensemble de cardinal $2^n$ vu que pour chaque entier $k\!\in\![|1,n|]$ on peut soit le prendre, soit ne pas le prendre et que pour l'entier $k\!=\!n\!+\!1$, il n'y a pas le choix, on doit le prendre.
  • Oui $2^{n+1}-2^n=2^n \times (2-1)=2^n$.

    Mais comment trouver la bijection ? C'est toujours sur ce point que je bloque. 
  • Déjà essaye de proposer deux ensembles de même cardinaux au départ et à l'arrivée.
  • Ensemble de départ : les parties de $[|1,n+1|]$ qui contiennent $n+1$. Cardinal : $2^n$.
    Ensemble d'arrivée : je ne trouve pas. 
  • Modifié (16 Feb)
    Je prends une partie de $[\![1,n\!+\!1]\!]$ qui contient l'élément $n\!+\!1$.  Je lui enlève cet élément.  Il me reste quoi ?

    (non, non, ce n'est pas "pince moi" . . .)
  • Modifié (16 Feb)
    Soit $f : \text{ensemble des parties de} \ [|1,n+1|] \ \text{qui contiennent} \ n+1 \longrightarrow \mathcal P([|1,n|])$ définie par $f(A)=A \setminus \{n+1\}$.
    Elle est bijective.
    Donc $\displaystyle\sum_{A \in \mathcal P([|1,n+1|] \\ n+1 \in A} \dfrac{1}{p(A)} = ?$
    Je n'ai pas l'impression que cette bijection me permet d'obtenir la somme que je veux, je bloque ici.
  • Tu ne peux pas bloquer ici : tu n'as même pas utilisé ta bijection $f$...
  • Modifié (16 Feb)
    @JLapin
    En effet. J'ai trouvé l'astuce : $A=f(A) \cup \{n+1\}$.
    $\displaystyle\sum_{A \in \mathcal P([|1,n+1|]) \\ n+1 \in A} \dfrac{1}{p(A)} =\sum_{A \in \mathcal P([|1,n+1|]) \\ n+1 \in A} \dfrac{1}{p(f(A) \cup \{n+1 \})} =\sum_{A \in \mathcal P([|1,n|])} \dfrac{1}{p(A \cup \{n+1 \})} = \boxed{\sum_{A \in \mathcal P([|1,n|])} \dfrac{1}{(n+1)p(A)} }$

    Exercice d'application.
    Soit $A$ une partie finie d'un anneau commutatif. 
    Montrer par récurrence sur le cardinal de $A$ que :  $\displaystyle\prod_{a \in A} (1+a)=\displaystyle\sum_{B \in \mathcal P(A)} \displaystyle\prod_{b \in B} b$.
  • Modifié (16 Feb)
    Notons $n=|A|$.
    Si $n=1$, le résultat est évident. 
    Sinon, soit $A$ un ensemble de cardinal $n+1$. Soit $x$ un élément de $A$.
    Notons $A' = A \backslash \{x \}$.
    On a $\displaystyle\sum_{B \in \mathcal P(A)} \displaystyle\prod_{b \in B} b = \displaystyle\sum_{B \in \mathcal P(A) \\ x \notin B} \displaystyle\prod_{b \in B} b+ \displaystyle\sum_{B \in \mathcal P(A) \\ x \in B} \displaystyle\prod_{b \in B} b$
    On a : 
    • $\displaystyle\sum_{B \in \mathcal P(A) \\ x \notin B} \displaystyle\prod_{b \in B} b = \displaystyle\sum_{B \in \mathcal P(A') } \displaystyle\prod_{b \in B} b = \displaystyle\prod_{a \in A'} (1+a)$.
    • $\displaystyle\sum_{B \in \mathcal P(A) \\ x \in B} \displaystyle\prod_{b \in B} b = \displaystyle\sum_{B \in \mathcal P(A) \\ x \in B } \displaystyle\prod_{b \in f(B) \cup \{x \} } b = \displaystyle\sum_{B \in \mathcal P(A')} \displaystyle\prod_{b \in B\cup \{x \} } x =x  \displaystyle\prod_{a \in A'} (1+a)$.
    Donc $\displaystyle\sum_{B \in \mathcal P(A)} \displaystyle\prod_{b \in B} b = x  \displaystyle\prod_{a \in A'} (1+a) +  \displaystyle\prod_{a \in A'} (1+a)$

     $\displaystyle\sum_{B \in \mathcal P(A)} \displaystyle\prod_{b \in B} b = (1+x) \displaystyle\prod_{a \in A'} (1+a)$

    Enfin :  $\boxed{\displaystyle\sum_{B \in \mathcal P(A)} \displaystyle\prod_{b \in B} b = \displaystyle\prod_{a \in A} (1+a)}$.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!