Majoration Binome de Newton par Polynome

[invite17fb38b6]

Bonjour,

Voici le problème que je me pose :

Existe-t-il une fonction f(n) NON constante telle que :

C(n,f(n)) < n^k pour un k fixé et pour n assez grand.

Avec C(n,m) le binôme de Newton, C(n,m) = n!/(n-m)!m!.

Il faut savoir que si f(x) est constante, C(n,f(n)) est MAJOREE par un polynome. Si f(x) = x/2, C(n, f(n)) est MINOREE par une exponentielle. Je cherche à déterminer à quel moment C(n, f(n)) passe du stade "majorée par un polynôme" à "minorée par une exponentielle" avec 0 < f'(x) < 1/2 et la dérivée f'(x) le plus proche possible
de 1/2. Ce moment existe, mais comment le déterminer ?

L'idée que j'ai eu est conventionnelle :

J'utilise la fonction de Stirling pour approcher et rendre dérivable le binôme de Newton (Je le majore)... J'élimine de cette approximation tous les facteurs majorable par un polynome (sous la racine) car ils compléxifient le calcul et sont inutiles puisque déjà majorés par un
polynome.

Le problème devient :

Existe-t-il une fonction f(n) telle que :

C(x,f(x)) < B(x,f(x)) < x^k

avec B(x,f(x)) = e^[x(1 + ln(x))] * (x - f(x))^(f(x) - x) * f(x)^-f(x)

Et j'etudie la dérivée de ln(B(x,f(x))) et k.ln(x) pour les comparer...

On pose g(x) = ln(B(x,f(x)))

Donc, g(x) = x(1 + ln(x)) - (x - f(x)).ln(x - f(x)) - f(x).ln(f(x))

Je trouve g'(x) = 3 + ln(x) + ln(x-f(x)) + f'(x).(ln(f(x)) - ln(x-f(x))

Et là c'est le drame...
Je n'arrive pas à résoudre l'inégalité différentielle suivante car trop incompétant sur les eq. diff. :

Trouver f(x) telle que g'(x) < k/x .

Si j'élimine le terme avec f'(x) j'obtient :
~g'(x) = ln(x) + ln(x - f(x)) < k/x
Ce qui me donne : f(x) > x-[e^(1/x)]/x
mais ne me permet pas de conclure sur le pb de départ ....

Quelqu'un peut-il m'aider ? Cela me permettrait de valider mathématiquement l'intérêt à apporter à un algorithme en théorie des graphes sur lequel je travaille en ce moment...

En tous cas, à tous ceux qui prennent la peine de lire,
un grand merci ! C'est déjà un bel effort de lire ce post !

Nicola Levoilier
-----

[matthias]

Existe-t-il une fonction f(n) NON constante telle que :

C(n,f(n)) < n^k pour un k fixé et pour n assez grand.

Dit comme ça, c'est évident avec f(n) = n.
Mais j'imagine, en ayant lu le post, que tu cherches une fonction croissante avec f(n) <= n/2, c'est bien ça ?

[invite17fb38b6]

Oui absolument !
Décidément j'arrive pas très bien à poser le pb...
Je cherche une fonction croissante qui soit plus petite que n/2...

As tu des idées ?