إثبات مسلمة برتراند

لأي عدد صحيح${\displaystyle n>0}$لدينا

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}.}$

البرهان: بتطبيق نظرية ذات الحدين ،

${\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}=2+\sum _{k=1}^{2n-1}{\binom {2n}{k}}\leq 2n{\binom {2n}{n}},}$

منذ${\displaystyle {\tbinom {2n}{n}}}$هو الحد الأكبر في المجموع على الجانب الأيسر، والمجموع يحتوي على${\displaystyle 2n}$الشروط (بما في ذلك الشروط الأولية)${\displaystyle 2}$(خارج نطاق الجمع).

لسعر فائدة ثابت${\displaystyle p}$، يُعرِّف${\displaystyle R=R(n,p)}$أن يكون الترتيب p -adic لـ${\displaystyle {\tbinom {2n}{n}}}$أي أكبر عدد طبيعي${\displaystyle r}$بحيث${\displaystyle p^{r}}$يقسم${\displaystyle {\tbinom {2n}{n}}}$.

لأي عدد أولي${\displaystyle p}$،${\displaystyle p^{R}\leq 2n}$.

البرهان: أس${\displaystyle p}$في${\displaystyle n!}$يتم الحصول عليها بواسطة صيغة ليجندر

${\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \!,}$

لذا

${\displaystyle R=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\sum _{j=1}^{\infty }\left(\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\!\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \right)}$

لكن يجب أن يكون كل حد من حدود المجموع الأخير إما صفرًا (إذا${\displaystyle n/p^{j}{\bmod {1}}<1/2}$) أو واحد (إذا${\displaystyle n/p^{j}{\bmod {1}}\geq 1/2}$وجميع المصطلحات التي تتضمن${\displaystyle j>\log _{p}(2n)}$تساوي صفرًا. لذلك،

${\displaystyle R\leq \log _{p}(2n),}$

و

${\displaystyle p^{R}\leq p^{\log _{p}(2n)}=2n.}$

لو${\displaystyle p}$هو عدد أولي فردي و${\displaystyle {\frac {2n}{3}}<p\leq n}$، ثم${\displaystyle R(n,p)=0.}$

البرهان: يوجد عاملان فقط من${\displaystyle p}$في بسط التعبير${\displaystyle {\tbinom {2n}{n}}=(2n)!/(n!)^{2}}$، قادمة من المصطلحين${\displaystyle p}$و${\displaystyle 2p}$في${\displaystyle (2n)!}$وكذلك عاملان من${\displaystyle p}$في المقام من نسخة واحدة من المصطلح${\displaystyle p}$في كل من العاملين من${\displaystyle n!}$تتلاشى هذه العوامل جميعها، فلا يتبقى أي عوامل من${\displaystyle p}$في${\displaystyle {\tbinom {2n}{n}}}$(القيد على${\displaystyle p}$يضمن شرط مسبقات اللمة أن${\displaystyle 3p}$كبير جدًا بحيث لا يمكن أن يكون حدًا من حدود البسط، والافتراض هو${\displaystyle p}$من الضروري أن يكون الأمر فرديًا لضمان ذلك${\displaystyle 2p}$لا يساهم إلا بعامل واحد من${\displaystyle p}$(إلى البسط.)

يتم توفير حد أعلى للدالة الأولية ،

${\displaystyle n\#=\prod _{p\,\leq \,n}p,}$

حيث يتم أخذ الناتج على جميع الأعداد الأولية${\displaystyle p}$أقل من أو يساوي${\displaystyle n}$.

للجميع${\displaystyle n\geq 1}$،${\displaystyle n\#<4^{n}}$.

البرهان: نستخدم الاستقراء الكامل .

ل${\displaystyle n=1,2}$لدينا${\displaystyle 1\#=1<4}$و${\displaystyle 2\#=2<4^{2}=16}$.

لنفترض أن المتباينة صحيحة لجميع${\displaystyle 1\leq n\leq 2k-1}$. منذ${\displaystyle n=2k>2}$مركب، لدينا

${\displaystyle (2k)\#=(2k-1)\#<4^{2k-1}<4^{2k}.}$

والآن لنفترض أن المتباينة صحيحة لجميع${\displaystyle 1\leq n\leq 2k}$. منذ${\displaystyle {\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}}$هو عدد صحيح وجميع الأعداد الأولية${\displaystyle k+2\leq p\leq 2k+1}$تظهر فقط في البسط، لدينا

${\displaystyle {\frac {(2k+1)\#}{(k+1)\#}}\leq {\binom {2k+1}{k}}={\frac {1}{2}}\!\left[{\binom {2k+1}{k}}+{\binom {2k+1}{k+1}}\right]<{\frac {1}{2}}(1+1)^{2k+1}=4^{k}.}$

لذلك،

${\displaystyle (2k+1)\#=(k+1)\#\cdot {\frac {(2k+1)\#}{(k+1)\#}}\leq 4^{k+1}{\binom {2k+1}{k}}<4^{k+1}\cdot 4^{k}=4^{2k+1}.}$

من الممكن تقليل الحد إلى${\displaystyle n=50}$.

ل${\displaystyle n\geq 17,}$نحصل${\displaystyle \pi (n)<{\frac {n}{2}}-1}$لذلك يمكننا القول أن المنتج${\displaystyle p^{R}}$هو على الأكثر${\displaystyle (2n)^{0.5{\sqrt {2n}}-1}}$، مما يعطي

${\displaystyle {\begin{aligned}&{\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}\leq (2n)^{0.5{\sqrt {2n}}-1}4^{2n/3}\\&4^{\sqrt {2n}}\leq (2n)^{3}\\&8n\leq 9\log _{2}^{2}(2n)\end{aligned}}}$

وهذا ينطبق على${\displaystyle n=49}$وخاطئ لـ${\displaystyle n=50}$.