Forum de mathématiques - Bibm@th.net

Saikidoka

Membre

Inscription : 23-08-2024

Messages : 3

Interprétation d'une suite vis à vis de la somme des k(k parmi n)

Bonjour à tous,

Par avance, désolé si cette discussion se trouve dans la mauvaise catégorie, cela dit il s'agit bien pour moi d'une curiosité et bizarrerie.

En préparant une potentielle future évaluation pour mes élèves, je me suis pris de curiosité pour la suite définie par récurrence comme suit :
[tex]\left\{\begin{aligned}u_0&=0\\u_{n+1}&=2u_n+2^n\end{aligned}\right.[/tex]

La curiosité vient du fait que l'on peut montrer que pour tout [tex]n\in\mathbb N[/tex], on a [tex]u_n=n2^{n-1}[/tex]

Or, on peut trouver que [tex]\sum_{k=0}^nk\times\binom{k}{n}=n2^{n-1}[/tex]

Une formule qui ne m'est pas totalement inconnue car lors d'un stage en L3, j'ai fait le lien entre cette formule et un graphe particulier. Je me demandais donc s'il s'agissait d'une coïncidence de la retrouver ici ou s'il existait une interprétation qui m'échappe.

J'avoue que je ne suis pas spécialement fan de l'idée d'une coïncidence, mais il est vrai que si on généralise la suite pour tout [tex]\lambda\in\mathbb C^*[/tex] par
[tex]\left\{\begin{aligned}u_0&=0\\u_{n+1}&=\lambda u_n+\lambda^n\end{aligned}\right.[/tex]
on trouve encore que pour tout [tex]n\in\mathbb N[/tex], on a [tex]u_n=n\lambda^{n-1}[/tex]

Merci à vous d'avoir pris le temps de me lire et pour vos idées

Dernière modification par Saikidoka (23-08-2024 17:45:13)

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 508

Re : Interprétation d'une suite vis à vis de la somme des k(k parmi n)

Bonsoir,

Ce n'est pas du hasard.

Votre relation correspond au nombre de façons de choisir un groupe de personnes avec choix d'un représentant du groupe.
On peut montrer l'égalité en faisant le dénombrement de deux façons.
Le rapport avec la récurrence coule de source en regardant ce qui se passe en rajoutant une personne pour passer de n à n+1.
Distinguer deux cas:
Soit l'intrus est lui-même un représentant, soit il n'en est pas,
mais alors sa présence ou non dans un groupe représenté double exactement  les cas.
C'est facile.

A

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Saikidoka

Membre

Inscription : 23-08-2024

Messages : 3

Re : Interprétation d'une suite vis à vis de la somme des k(k parmi n)

Merci de la réponse,

J'avoue que ce n'était pas si immédiat pour moi et j'adore cette interprétation de la formule. Juste pour reformuler si j'ai bien compris, pour passer de n à n+1, on ajoute une nouvelle personne :
- Soit elle est représentante de son groupe : on regarde tous les groupes possibles en choisissant parmi les n personnes déjà présentes ce qui fait [tex]\sum_{k=0}^n\binom{k}{n}=2^n[/tex]
- Soit elle n'est pas représentante de son groupe :
    - Soit on l'ajoute à l'un des groupes d'avant : [tex]u_n[/tex]
    - Soit on ne l'ajoute pas à l'un des groupes d'avant : [tex]u_n[/tex]
On retrouve alors bien [tex]u_{n+1}=2u_n+2^n[/tex].

C'est bien ça ?

Merci encore pour cette interprétation, du coup question subsidiaire, qu'en est-il de la généralisation avec [tex]\lambda[/tex] ?

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 508

Re : Interprétation d'une suite vis à vis de la somme des k(k parmi n)

Bonjour,

En plus des $2^n$ lorsque la n+1 ième personne P est représentant ( comme vous l'avez dit, on complète avec une partie quelconque parmi n) , il faut ajouter toutes les parties où elle n'est pas un représentant :
Ce sont celles où P n'est pas dans le groupe, on en a $u_n$,
+ ces mêmes choix avec P raccolé au groupe , il en a aussi $u_n$... D'où la relation de récurrence.

Pour généraliser je n'y ai pas réfléchi, il est peut-être mieux de passer par l'algèbre et des dérivations.

A.

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 508

Re : Interprétation d'une suite vis à vis de la somme des k(k parmi n)

Bonjour,

Sinon on peut quand même faire un pont pour la généralisation, en persévérant avec le dénombrement.

On procède comme avant, mais le prix à payer quand on considère un groupe de k personnes est $(\lambda - 1)^{k-1}$, et on s'intéresse au coût global.
Le cas $\lambda = 2$ redonne bien-sûr ce qui a été vu (mais transparent alors vu que 2-1 = 1, ce qu'on a dénombré est aussi le coût global en payant 1 Euro à chaque fois, si on préfère ).

Et si vous voulez retrouver la récurrence, vous vous convaincrez facilement (en suivant le même raisonnement que dans le cas $\lambda = 2$ ) , que
$u_{n+1} = u_n + (\lambda - 1)u_n + \Sigma_{0 \le k \le n} C(n,k) (\lambda - 1)^{k - 1+1}$ (on voit apparaitre encore dans la dernière somme partielle le coût partiel quand on considère les parties où l'intrus est président, égale à $\lambda^n$ d'après la formule du binôme).

Bref, la boucle est bouclée ...

Bonne fin de journée

Alain

Dernière modification par bridgslam (26-08-2024 12:19:12)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."