OliForum Matematico

Ero indeciso se postare questo problema qui o in TdN, ma credo che questo sia il posto giusto...

Dimostrare che per tutti gli n tali che $ \displaystyle {{2 n} \choose n } \le 2^n $, 6n+5 è primo.

.....

$ \displaystyle {n \choose k} = \frac {n!}{k!(n-k)!} $

$ \displaystyle {2 \choose 1} = {\frac {2!}{1!(2-1)!}= {\frac{2}{1}} = {2} = {2^1}} $

$ \displaystyle {4 \choose 2} = {\frac {4!}{2!(4-2)!}= {\frac{4\cdot3\cdot2!}{2!\cdot2!}} = {6} > {2^2}} $

$ \displaystyle {6 \choose 3} = {\frac {6!}{3!(6-3)!}= {\frac{6\cdot5\cdot4\cdot3!}{3!\cdot3!}} = {20} > {2^3}} $

...........

il numero $ n $ è supposto naturale? Mi devo essere perso qualcosa, devo aver sbagliato io, devo essermi distratto... non può essere così!

Sì n è naturale (cioè intero maggiore o uguale a 0), qual è il problema?
(Lo so non è un problema molto complicato...)

Sisifo ha scritto:Dimostrare che per tutti gli n tali che $ \displaystyle {{2 n} \choose n } \le 2^n $, 6n+5 è primo.

Per ogni $ n \in \mathbb{N} $, vale $ \displaystyle 2^n = \sum_{k=0}^n \binom{n}{k} \le \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} $, dove l'uguaglianza è soddisfatta sse $ \displaystyle \binom{n}{k} = 1 $, per ogni $ k = 0, 1, \ldots, n $, i.e. sse $ n = 0, 1 $. E in effetti, $ 5 $ e $ 2 \cdot 6 + 5 $ sono primi.

No, boh, è che stando così le cose, la diseguaglianza vale solo per $ n=1 $, ed è di seguito ovvio che $ 6\cdot1+5=11 $ è primo... è che mi pareva troppo facile...

Precisamente la mia dimostrazione...

PS Vale anche per n=0, come ha fatto notare Hitl

Comunque credo che starebbe meglio nel subforum di TdN: non si dica mai che ho risolto un problema della sezione combinatorica...

Sì, vero, vale anche per $ n=0 $...

Il modo in cui *tentavo* di dimostrarlo sarebbe stato... verificare che l'esponenziale base due cresceva meno della combinazione, al crescere di $ n $... e che quindi per $ n>1 $ i due valori non si incontrano più... ma va beh...

Ne approfitterei per chiedere ai più eruditi da dove salti fuori quella proprietà che ha usato HiTLeuLer... Grazie...

Non sono fra i più eruditi, ma ti rispondo ugualmente - senza offesa alcuna per i più eruditi!

-------

Dal teorema binomiale $ \displaystyle \sum_{k=0}^{2n} \binom{2n}{k} x^k (1+x)^{2n} = (1+x)^n (1+x)^n = $ $ \!\displaystyle\left(\sum_{k=0}^n \binom{n}{k} x^k\right)\!\left(\sum_{h=0}^n \binom{n}{h} x^h\right) $. Adesso eguaglia i coefficienti dei termini di grado $n$ ai due membri, per ottenere l'identità desiderata.

Io le ho postate nel glossario...

Arigatou gozaimashita!

Chi posta l'istruttiva dimostrazione per induzione??? Magari sarebbe meglio lo facesse qualcuno che ci mette più di 0,2 secs a trovarla...

Beh, è piuttosto semplice vedere che il primo membro, una volta semplificato n! a numeratore e denominatore, e poi dividendo ambo i membri per 2^n e distribuendo i vari 2 ai fattori del denominatore e moltiplicando e dividendo per 2n, otteniamo al numeratore il prodotto di naturali ognuno dei quali è maggiore del corrispondente al denominatore, quindi la frazione è maggiore di 1. Da ciò esaminiamo i casi banali.