Identità di Legendre-de Polignac.

[sasha™]

Da questa identità si ricava la disuguaglianza:

$$ v_p(n!) ≤ \frac{n}{p-1}$$

Domanda: quando sussiste l'uguaglianza?

EDIT: corretto il sorgente LaTeX. ma_go

[<enigma>]

E' ovvio: $ \left \lfloor \frac{n}{p^k} \right \rfloor $ è nulla per ogni $ p^k>n $, dunque nella tua maggiorazione non sussisterà mai l'uguaglianza, visto che avrai come minimo una differenza di $ \displaystyle \sum_{k=\left \lfloor \log _p n \right \rfloor +1} ^{\infty} \frac{n}{p^k}>0 $.

Per chi non conoscesse la formula e come ricavare la maggiorazione: $ \displaystyle v_p(n!)=\sum_{k=1}^{\infty} \left \lfloor \frac{n}{p^k} \right \rfloor \leq \sum_{k=1}^{\infty} \frac{n}{p^k} = \frac{n}{p-1} $

[sasha™]

Quindi si può benissimo usare la disuguaglianza stretta?

[ndp15]

Domanda: quando sussiste l'uguaglianza?

L'uguaglianza sussiste nel caso banale $ n=0 $
Inoltre si tenga presente che vale $ \displaystyle v_p(n!) = \frac{n - s_p(n)}{p - 1} $ ove dove $s_p(\cdot)$ è la funzione che associa a ogni intero la somma delle cifre della sua rappresentazione posizionale in base $p$

[matty96]

Ragazzi, mentre facevo un problema mi sono imbattuto in questa cosa $$ \upsilon_2\left(\binom{2s}{s}\right) $$ e per risolverlo ho fatto alcuni passaggi usando le proprietà di $\upsilon_p(\cdot)$
$$ \upsilon_2\left(\binom{2s}{s}\right)=\upsilon_2\left(\frac{2s!}{s!s!}\right)=\upsilon_2(2s!)-\upsilon_2(s!s!)=\upsilon_2(2s!)-2\upsilon_2(s!)$$ ora usando la proprietà del post ottengo che $\upsilon_2(2s!)-2\upsilon_2(s!) \leq 2n - 2n= 0$. Dove sbaglio? Forse devo usare $s_p(\cdot)$? Nel caso come faccio?

[<enigma>]

Ragazzi, mentre facevo un problema mi sono imbattuto in questa cosa $$ \upsilon_2\left(\binom{2s}{s}\right) $$ e per risolverlo ho fatto alcuni passaggi usando le proprietà di $\upsilon_p(\cdot)$
$$ \upsilon_2\left(\binom{2s}{s}\right)=\upsilon_2\left(\frac{2s!}{s!s!}\right)=\upsilon_2(2s!)-\upsilon_2(s!s!)=\upsilon_2(2s!)-2\upsilon_2(s!)$$ ora usando la proprietà del post ottengo che $\upsilon_2(2s!)-2\upsilon_2(s!) \leq 2n - 2n= 0$. Dove sbaglio? Forse devo usare $s_p(\cdot)$? Nel caso come faccio?

1. Hai sbagliato a mettere le parentesi, $ 2s! \neq (2s)! $.
2. Hai sbagliato a maggiorare il coefficiente binomiale centrale, perché per maggiorare tutta l'espressione è corretto maggiorare $ v_2((2s)!) $, ma devi minorare $ 2v_2(s!) $. Più precisamente $ v_2((2s)!)-2v_2(s!)<2s-2v_2(s!)<2s-2(s/2)=s $ -se usi una minorazione diversa per la valutazione diadica di $ s! $ giungi ad una stima diversa, qui ho usato il debole fatto che ci sono circa $ n/2 $ numeri pari $ \leq n $ (se $ n $ è dispari sottrai 1/2 ma la stima è sempre quella) e quindi almeno altrettanti fattori 2-.
Il ragionamento che ci sta dietro è: devo trovare un valore massimo per un'espressione del tipo $ a-b $, allora devo trovare un massimo di $ a $ e un minimo di $ b $, trovando il massimo di entrambi non posso dire niente (ragionamento simile si applica al quoziente di due quantità).

[matty96]

Si al punto 1 non ho messo le parentesi ma credo che ho pensato come se ci fossero(infatti lo avevo svolto in umodo diverso,senza le proprietà e dava s come risoltato).Scusa ma non ho capito perchè al posto $2\upsilon_2(s!)$ metti $2(s/2)$ .Potresti spiegarmelo meglio questo fatto?(il ragionamento l'ho capito ma questa cosa no)

[<enigma>]

Dunque, noi dobbiamo stimare quanti fattori 2 ci sono in $ s! $: i numeri pari minori di $ s $ sono $ 2, 4, ..., s $ se $ s $ è pari, se è dispari cambia poco. Ogni numero pari contribuisce per almeno un fattore 2 al loro prodotto, quindi $ 1 \cdot 2 \cdot 3 \cdot ... \cdot s $ avrà almeno un fattore 2 dato da 2, uno dato da 4, uno da 6, eccetera. I numeri pari minori di $ s $ sono $ s/2 $ (sempre supponendo $ s $ pari, non complichiamoci la vita). Riassumendo dunque: $ s/2 $ numeri pari, ciascun numero pari ha almeno un fattore 2, dunque hai almeno $ s/2 $ fattori 2. Poi in realtà i fattori 2 sono di più perché alcuni numeri pari contengono più di un fattore 2 (questi sono 4, 8, 12, 16, ...), ma come stima non è poi così brutta. Se ti aiuta vedilo come un troncamento della formula citata all'inizio.

[matty96]

Si ,ora è tutto chiaro....io avevo fatto più o meno un ragionamento del genere.Infatti senza sfruttare la proprietà dei binomiali avevo scritto $$\binom{2s}{s}=\frac{2s(2s-1)(2s-2)\cdot\cdot\cdot(s+1)}{s(s-1)\cdot\cdot\cdot 1}$$ sfruttando questo fatto ho notato che tutti i numeri pari del numeratore si divedevano con il denominatore dando come risultato 2 (tipo $\frac{2s-2}{s-1}$) e cosi',dato che il numero di numeri pari di 2s è s, il binomiale diventa $2^s(2n-1)(2n-3)\cdot\cdot\cdot(s+1)$ (ovviamente parlando di s pari) e da ciò ho ricavato s come risultato.Spero che il mio ragionamento non abbia errori.....

[<enigma>]

Si ,ora è tutto chiaro....io avevo fatto più o meno un ragionamento del genere.Infatti senza sfruttare la proprietà dei binomiali avevo scritto $$\binom{2s}{s}=\frac{2s(2s-1)(2s-2)\cdot\cdot\cdot(s+1)}{s(s-1)\cdot\cdot\cdot 1}$$ sfruttando questo fatto ho notato che tutti i numeri pari del numeratore si divedevano con il denominatore dando come risultato 2 (tipo $\frac{2s-2}{s-1}$) e cosi',dato che il numero di numeri pari di 2s è s, il binomiale diventa $2^s(2n-1)(2n-3)\cdot\cdot\cdot(s+1)$ (ovviamente parlando di s pari) e da ciò ho ricavato s come risultato.Spero che il mio ragionamento non abbia errori.....

Purtroppo il tuo ragionamento non è esatto, dato che nell'argomento della divisione termine a termine che dà come risultato 2 hai perso qualche termine per strada (oltre a dire $ s $ fattori 2 invece di $ s/2 $: il numero di numeri pari di $ 2s $ è $ s $ ma tu hai troncato il numeratore a $ s+1 $ semplificandolo direttamente con un $ s! $!). Ti faccio un esempio con $ s=5 $: $ \binom{10} {5} =\frac {10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=\frac {10} {5} \cdot \frac {8}{4} \cdot \frac {6}{3} \cdot 9 \cdot 7 \cdot \frac 1 2=2^3 \cdot 9 \cdot 7 \cdot \frac 1 2=2^2(...) $. Tieni anche conto che il risultato non può comunque essere esattamente $ s $ poiché le disuguaglianze che ho scritto prima sono entrambe strette (riflettici su un attimo), dunque il numero di fattori 2 è sicuramente minore di $ s $. Aggiungo che in realtà il numero di fattori 2 è di solito assai minore di $ s $: per esempio se $ s=20 $ hai solamente due fattori 2 e non 20 -o 19-! Non penso si possa esprimere facilmente/elementarmente la valutazione diadica di quel binomiale perché partendo dalla formula di de Polignac vedi che le funzioni parte intera sono abbastanza rognose da trattare.

[matty96]

Ah...grazie tante,ecco perchè non riuscivo a concludere il problema.Io ero sicuro di quella s,mentre non ho guardato bene.Ti ringrazio,non riuscivo a trovare l'errore

P.S. comunque io consideravo s pari ,quindi s+1 è dispari e non lo semplifico

[Veluca]

Visto che siamo in tema, chi riesce a calcolare il valore esatto di $\upsilon_2({2^k \choose 2^{k-1}})$?

[<enigma>]

Abbastanza facile, ma lo metto nascosto per non togliere a matty96 il piacere di farlo.

Testo nascosto:

Al numeratore la contribuzione di 2-fattori è $ \displaystyle \sum_{n=1}^{\infty} \left \lfloor \frac{2^k}{2^n} \right \rfloor=\sum_{n=1}^{\infty} \left \lfloor 2^{k-n} \right \rfloor=\sum_{n=1}^{k} 2^{k-n}=2^k-1 $, al denominatore è $ \displaystyle 2\sum_{n=1}^{\infty} \left \lfloor \frac{2^{k-1}}{2^n} \right \rfloor=2\sum_{n=1}^{\infty} \left \lfloor 2^{k-n-1} \right \rfloor=2\sum_{n=1}^{k-1} 2^{k-n-1}=2(2^{k-1}-1)=2^k-2 $, e la valutazione del quoziente è $ 2^k-1-(2^k-2)=1 $. Dunque $ \displaystyle v_2 \left ( \binom{2^k}{2^{k-1}} \right )=1 $.

[matty96]

Anche me esce 1, solo che per dimostrarlo ho bisogno di dimostrare anche questo: $$\upsilon_2((2^h)!)=2^h-1$$ Non riesco a trovare una prova di questo fatto,un aiutino?

[<enigma>]

Prova per induzione.