Coefficients binomiaux
dans Arithmétique
Bonsoir
Je cherche à prouver que $\displaystyle \forall n \in \mathbb N^*,\ \binom{2n}{n} = \sum_{k=0}^{n-1}\Big(1+\frac{n}{n-k}\Big)$
J'avais pensé à le prouver par récurrence :
Au rang $n = 1$ : $\dbinom{2}{1} = 2~$ et $~\displaystyle \sum_{k=0}^{0}\Big(1+\frac{n}{n-k}\Big) = 2.$
Puis pour un certain $n$ on a : $~\displaystyle \binom{2n}{n} = \sum_{k=0}^{n-1}\Big(1+\frac{n}{n-k}\Big).$
Reste à montrer que $~\displaystyle \binom{2(n+1)}{n+1} = \sum_{k=0}^{n}\Big(1+\frac{n+1}{n+1-k}\Big)$
Mais je ne vois pas quelle opération réaliser pour passer de $\dbinom{2n}{n}$ à $\dbinom{2(n+1)}{n+1}$
La formule de Pascal ne me semble pas adaptée donc je ne sais pas quoi faire pour continuer
Sinon peut-être que la récurrence n'est pas adaptée ?
Un petit indice ? (:P)
Merci pour votre aide
Je cherche à prouver que $\displaystyle \forall n \in \mathbb N^*,\ \binom{2n}{n} = \sum_{k=0}^{n-1}\Big(1+\frac{n}{n-k}\Big)$
J'avais pensé à le prouver par récurrence :
Au rang $n = 1$ : $\dbinom{2}{1} = 2~$ et $~\displaystyle \sum_{k=0}^{0}\Big(1+\frac{n}{n-k}\Big) = 2.$
Puis pour un certain $n$ on a : $~\displaystyle \binom{2n}{n} = \sum_{k=0}^{n-1}\Big(1+\frac{n}{n-k}\Big).$
Reste à montrer que $~\displaystyle \binom{2(n+1)}{n+1} = \sum_{k=0}^{n}\Big(1+\frac{n+1}{n+1-k}\Big)$
Mais je ne vois pas quelle opération réaliser pour passer de $\dbinom{2n}{n}$ à $\dbinom{2(n+1)}{n+1}$
La formule de Pascal ne me semble pas adaptée donc je ne sais pas quoi faire pour continuer
Sinon peut-être que la récurrence n'est pas adaptée ?
Un petit indice ? (:P)
Merci pour votre aide
Réponses
-
Pour passer de $ \binom{2n}{n}$ à $\binom{2(n+1)}{n+1}$ tu peux effectuer le quotient.
-
Le quotient de ?
-
Mais as-tu calculé les premières valeurs de $\displaystyle S_n= \sum_{k=0}^{n-1}(1+\frac{n}{n-k})$ ? J'ai comme un doute...
-
Eh bien j'ai testé avec certaines valeurs de n et cela me semble coller
-
D'abord on écrit « eh bien ». Corrige, STP.
Ensuite, pour quelles valeurs « ça colle » ? -
Bonjour,
Il me semble que la leçon :
\[\binom{2n}{n} = \prod_{k=0}^{n-1}(1+\frac{n}{n-k})\]
est meilleure… -
Le passage de $\binom{2n}{n}$ à $\binom{2(n+1)}{n+1}$ peut t'être utile ailleurs. Quand tu as deux nombres et qu'on te suggère de calculer le quotient, c'est le quotient de quoi d'après toi ?
-
Oui bien sur c'est un produit ... je suis tête en l'air ...
Ok donc je calcule le quotient : $\frac{\binom{2n}{n}}{\binom{2(n+1)}{n+1}}$
Mais en quoi cela m'aide à effectuer mon passage ? -
Pour n=2, ça donne 6=5.
-
Pour n=3 la somme n'est même pas un entier sauf erreur.
$\begin{align} \sum_{k=0}^{3-1}\Big(1+\frac{3}{3-k}\Big)&=\Big(1+\frac{3}{3-0}\Big)+\Big(1+\frac{3}{3-1}\Big)+\Big(1+\frac{3}{3-2}\Big)\\
&=\Big(1+\frac{3}{3}\Big)+\Big(1+\frac{3}{2}\Big)+\Big(1+\frac{3}{1}\Big)\\
&=8,5
\end{align}$
PS:
La formule de GB semble numériquement nettement plus pertinente. -
Plutôt $\frac{\binom{2(n+1)}{n+1}}{\binom{2n}{n}}=q_n$, ainsi tu auras ${\binom{2(n+1)}{n+1}}=q_n {\binom{2n}{n}}$. Mais oublie ça pour l'instant, et réfléchis à la suggestion de gb.
-
Je ne vois pas pourquoi aller chercher une récurrence, alors qu'il suffit de réduire au même dénominateur, d'écrire les produits in extenso, et de contempler benoîtement le résultat :
\[\prod_{k=0}^{n-1} \left( 1+\frac{n}{n-k} \right) = \prod_{k=0}^{n-1}\frac{2n-k}{n-k} =\frac{2n(2n-1)(2n-2)\dotsm(n+1)}{n(n-1)(n-2)\dotsm1} = \dots\] -
Gb a écrit:Je ne vois pas pourquoi aller chercher une récurrence
Parce qu'en toute rigueur il en faut une. Tu veux établir une formule où figure un produit qui a un nombre de facteurs qui dépend de $n$. -
Bof, FdP !
on utilise la formule $\prod \frac{a_i}{b_i}=\frac{\prod a_i}{\prod b_i}$
Qui, elle, peut se prouver par une récurrence immédiate. -
Le diable se cache dans les trois petits points...
-
gb a raison. La récurrence n'est pas une fin en soi. L'égalité qu'il écrit donne immédiatement la solution. Benoîtement, c'est le mot.
-
L'égalité donne bien : $\frac{2n! - n!}{n!} $ ?
-
Maintenant, la fausse formule avec la somme m'a conduit à (me) poser une question.
J'ai posé : $\displaystyle S_n= \sum_{k=0}^{n-1}(1+\frac{n}{n-k})=n(1+H_n)$ avec $\displaystyle H_n= \sum_{j=1}^{n} \frac 1j$.
Récemment quelqu'un a rappelé dans un autre fil que pour $n \ge 2$, le rationnel $H_n$ n'est pas un entier. Quid de $n H_n$ ? -
Écris ce que vaut, "par définition", $\binom{2n}{n}$ et compare avec le résultat donné par Gb.
-
$3\times H_3=5,5$ sauf erreur.
PS:
Je viens de me rendre compte que la question posée est: $nH_n$ n'est jamais un entier pour $n>2$? -
Justement $\binom{2n}{n} = \frac{2n!}{n!^2}$ ce qui ne me semble pas être égal au produit
-
Il n'y a aucun diable. On trouve exactement l'expression du coefficient binomial, et les formules avec les points de suspension ne sont pas plus diaboliques que les formules avec $\Sigma$ ou $\Pi$.
-
Pebid:
Ne sais-tu pas que $\dfrac{u}{v}=\dfrac{a\times u}{a\times v}$ ?
$a,v$ non nuls.
PS:
A toi de trouver ce que vaut $a$ dans le cas qui te préoccupe.
PS2:
L'égalité correcte est celle-ci:
$\binom{2n}{n} = \frac{(2n)!}{n!^2}$ (il ne faut pas oublier les parenthèses) -
Le diable ne se cache pas dans les petits points : l'écriture in extenso n'est là que pour permettre aux aveugles malvoyants de se rendre compte de la portée exacte des produits, afin de rédiger correctement le callul :
\[\prod_{k=0}^{n-1}\frac{2n-k}{n-k} = \frac{\prod_{k=0}^{n-1}(2n-k)\prod_{k=n}^{2n-1}(2n-k)}{\prod_{k=0}^{n-1}(n-k)\prod_{k=n}^{2n-1}(2n-k)} = \frac{\prod_{k=0}^{2n-1}(2n-k)}{\prod_{k=0}^{n-1}(n-k)\prod_{l=0}^{n-1}(n-l)} = \dots\]
J'utilise le changement d'indice \(l=n-k\), la formule du produit de \(n\) fractions et la formule permettant de regrouper deux produits de \(n\) termes par associativité ; la démonstration de ces formules nécessite certes une récurrence, mais je ne sache pas que l'on s'interdise d'utiliser ces formules afin de ne pas cacher les récurrences sous-jacentes. -
Gb:
Pour le coup, je trouve ta méthode détaillée compliquée.
A partir de la formule que tu donnes plus haut:
$\prod_{k=0}^{n-1} \left( 1+\frac{n}{n-k} \right) = \prod_{k=0}^{n-1}\frac{2n-k}{n-k} =\frac{2n(2n-1)(2n-2)\dotsm(n+1)}{n(n-1)(n-2)\dotsm1} = \dots$
La multiplication de la fraction de droite (numérateur et dénominateur) par le nombre adéquat termine le calcul en deux coups de cuillère à pot. -
Les symboles $\Sigma$ et $\Pi$ sont là pour nous, et non nous pour les symboles. Je veux dire que leur usage est légitime s'ils simplifient les choses mais ils ne sont pas une fin en soi. Les formules avec points de susension sont tout aussi légitimes.
Moi dans mon cours la formule principale pour les combinaisons était : $\binom{n}{p} =\frac{n(n-1)\dotsm(n-p+1)}{p!} $, qui donne immédiatement la solution du problème posé ici, comme gb l'a montré. -
Mon programme python pour $nH_n$ entier tourne depuis bien longtemps et ca ne semble pas etre entier... Quelqu'un possède la réponse?
-
Un fil du forum consacré au fait que $H_n$ n'est pas entier pour $n>1$
http://www.les-mathematiques.net/phorum/read.php?4,418260,418313 -
On peut essayer de partir de la démonstration du fait que $H_n$ n'est pas entier, et voir...
-
On peut essayer ça :
Soit $p$ un nombre premier de l'intervalle $\left] \frac{n}{2},n \right]$ dont l'existence est garantie par le postulat de Bertrand. Le raisonnement usuel sur $H_n$ montre que celui-ci peut s'écrire sous la forme
$$H_n = \frac{1}{p} + \frac{a}{b} \quad \textrm{avec} \ p \nmid b.$$
Notons aussi que $p \nmid n$ puisque $p > \frac{n}{2}$. Si $n H_n$ était entier, alors $bn H_n$ le serait aussi, entraînant une contradiction puisque $bn H_n = \frac{bn}{p} + na$. -
Voici le schéma d'une démonstration de ce que pour $n\in \mathbb{N}$, $p\in \mathbb{N}$, $p\geq 2$, le rationnel $S_{n,p}=\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{n+p}$ n'est jamais un entier.
On effectue la somme : $S_{n,p}=\frac{c_{1}+c_{2}+...+c_{p}}{(n+1)(n+2)...(n+p)}$, avec : $c_{i}= (n+1)(n+2)...(n+i-1)(n+i+1)...(n+p)$.
Pour tout $m\in \mathbb{N}^*$, on note $v_2(m)$ l'exposant de $2$ dans la décomposition de $m$ en facteurs premiers, c'est la valuation 2-adique de $m$.
Soit $\omega =v_{2}((n+1)(n+2)...(n+p))$ et $\omega_{i}=v_{2}(n+i)$. Alors : $v_{2}(c_{i})=\omega-\omega_{i}$.
Par suite : $c_i=2^{\omega-\omega_{i}}(2y_i+1)$, $y_i \in \mathbb N$.
Soit $\omega_{k}$ le plus grand des $\omega_{i}$ pour $i=1,2,...,p$. On a forcément : $\omega_{k}\geq 1$.
Il vient : $S_{n,p}=\frac{2y+1}{2^{\omega_{k}}(2z+1)}$, $y\in \mathbb{N}$, $z\in \mathbb{N}$. Conclusion : impair/pair = non entier.
J'ai sauté des intermédiaires, on verra ça demain si besoin est.
On devrait pouvoir utiliser ça avec $n=0$ pour prouver que $pH_p$ n'est pas entier pour $p \ge 3$.
Bonne nuit.
Fr. Ch.
21/12/2017 -
Poursuivons. Si l'on fait $n:=0$ dans le calcul précédent, alors $S_{n,p}=H_p$. Si $2^q \le p <2^{q+1}$, avec $q\in \mathbb N$, alors : $v_2(p)=q=\left\lfloor {\log_2 p}\right\rfloor $.
Avec les notations de mon message précédent, on a : $\omega_p=\left\lfloor {\log_2 p}\right\rfloor=\omega_k $, et par suite : $H_{p}=\frac{1}{2^{\left\lfloor \log _{2}p\right\rfloor }}\cdot \frac{2y+1}{2z+1}$.
Et là, déception. Je croyais pouvoir en conclure que $pH_p$ n'était pas entier, mais non.
Heureusement que nous avons la belle démonstration de noix de totos, qui réclame un outil plus élaboré, le théorème de Bertrand-Tchebychev.
Bonne journée.
Fr. Ch. -
@ Chaurien : l'expression obtenue pour \(H_p\) permet de conclure lorsque \(p\) n'est pas une puissance de 2.
-
Un exercice supplémentaire pour pebid, simplifier :
$(4-\dfrac{2}{1})\times(4-\dfrac{2}{2})\times(4-\dfrac{2}{3}) \times \dots \times (4-\dfrac{2}{2018})$
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 14
+8 Invités