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.
Primalità e combinatoria...
.....
$ \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ì!
$ \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ì!
...
Re: Primalità e combinatoria...
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.Sisifo ha scritto:Dimostrare che per tutti gli n tali che $ \displaystyle {{2 n} \choose n } \le 2^n $, 6n+5 è primo.
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... 
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.
-------
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.
Ultima modifica di HiTLeuLeR il 27 feb 2006, 17:43, modificato 1 volta in totale.
-
HumanTorch
- Messaggi: 281
- Iscritto il: 01 gen 1970, 01:00
- Località: Tricase
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.