Exercice pour le fun

[Médiat]

Bonjour,

Soit la suite définie par et pour , la question est de trouver une formule directe donnant .

Je précise que je poste cette question uniquement pour le plaisir de ceux qui chercheront (c'est un peu trop technique pour le sous-forum "Science ludique"), que je connais la réponse qui est d'ailleurs très, très facile à trouver sur le net (donc donner ici la réponse sans explication ne sert à rien).

Merci de poster sous spoiler, pour ne pas gâcher le plaisir des autres.
-----

[Seirios]

Bonsoir,

 Cliquez pour afficher

On écrit les premiers termes, et on devine que , que l'on simplifie en (ce qui doit pouvoir se montrer par récurrence). Je ne sais pas si l'expression peut être simplifiée ; on peut reconnaître le nombre d'arrangements, alors peut-être qu'un raisonnement de combinatoire permet de trouver une expression sympathique pour la somme.

[Médiat]

Bonsoir,

 Cliquez pour afficher

Vous pouvez même l'écrire

Mais on peut trouver une expression plus simple.

[Seirios]

 Cliquez pour afficher

Effectivement, le 1 peut être rentré dans la somme. Par changement de variables, ; je ne pense pas que l'on puisse simplifier davantage, mais on peut tout de même trouver que . Une autre manière de l'écrire serait (je ne crois pas que l'on dispose d'une expression simple pour la somme des factorielles).

[A voir en vidéo sur Futura]

[Médiat]

Vous avez tout en main pour trouver la réponse (pour n>0).

Je ne suis pas certain de votre deuxième formule.

[inviteea028771]

Par contre la méthode des séries génératrices (que j'aime beaucoup) semble coincer
Je suis terriblement déceptionné


Je vais donc essayer de trouver une autre méthode "originale", mais je suis assez en panne d'inspiration.

En attendant, la solution :

 Cliquez pour afficher

La solution, est assez facile à intuiter :

En appliquant la formule n fois, on a :



Ensuite, en développant :



Et ça se montre facilement rigoureusement par récurrence.


On peut interpréter ça comme la somme sur k du nombre d'arrangements de k parmis n :



Ou encore, le nombre total de façon de retirer des boules numérotés d'une urne à n boules (en prenant en compte l'ordre)

Il y a peut être une autre interprétation qui donne une écriture sans somme

[Médiat]

Bonjour,

Ce que vous écrivez est juste, mais le calcul peut vous permettre de simplifier énormément votre dernière formule.

[Seirios]

Vous avez tout en main pour trouver la réponse (pour n>0).

Je ne suis pas certain de votre deuxième formule.

Effectivement, la deuxième formule est fausse, j'ai fait une erreur dans un changement de variables.

[invite705d0470]

Bonjour
J'ai juste griffonné deux trois idées, mais je les mets quand même.

 Cliquez pour afficher

D'abord, j'ai voulu observer qualitativement l'évolution continue d'une solution en réécrivant sous la forme , ce qui vend des solutions de la forme (si mes lignes sont justes)
Pas très prometteur (même si on sens cachée derrière une fonction voisine de ).

Bon, en traitant directement la formule de récurrence comme une équation discrète, tout se passe beaucoup mieux, puisqu'on reconnait une équation fonctionnelle (gamma ou presque, donc) perturbée par un terme constant: j'ai donc cherché des solutions sous la forme où lambda vérifie (variation de la constante) .
En sommant ("primitive discrète", en quelques sortes), j'aboutis à
avec, finalement,

Est-ce correct ?

[Médiat]

Bonjour,

Votre dernière formule est correcte (mais on peut la simplifier un peu, voir le spoiler)

 Cliquez pour afficher

avec, finalement, d'où

Mais surtout on peut simplifier énormément cette formule (qui est un passage obligé dans la démonstration).

[inviteea028771]

J'ai cherché par curiosité la solution sur internet, et je dois avouer que je n'y aurai jamais pensé. Et une fois arrivé là ou tout le monde est arrivé, c'est facile à démontrer (si on y pense) :

 Cliquez pour afficher

La solution c'est

Pour la démonstration, il suffit d'écrire :




Et par comparaison avec la série des 1/2^n, on voit que ce dernier terme est strictement inférieur à 1 (pour n > 0 )

D'où le résultat:



Mais je n'aurai pas vu le résultat, je n'y aurai jamais pensé

[Médiat]

En voyant le résultat, vous avez la raison qui m'a poussé à poster cette question .

Vous remarquerez que Seirios, dans son message #4, "a tout en main pour trouver la réponse".

[Seirios]

C'est une remarque plutôt simple pourtant... Encore faut-il y faire attention.

 Cliquez pour afficher

Finalement, c'est une question assez naturelle : comparer avec l'expression asymptotique . Cela dit, je ne savais pas que l'on disposait d'une expression explicite pour .

C'est donc un résultat (surprenant) qui doit être trouvable si l'on trouve une bonne raison pour étudier la suite . Y a-t-il un cadre (relativement) naturel qui justifierait l'étude de cette suite ?

[Médiat]

Je réponds à Serios , sous spoiler, car cela pourrait aiguiller les réflexions.

 Cliquez pour afficher

est le nombre de mots que l'on peut écrire avec n lettres distinctes (y compris le mot vide). En fait la relation de récurrence apparaît après le résultat sous forme de somme d'inverse de factorielles