Il fattoriale cresce veloce ma non troppo... (Own)

[kn]

Dimostrare che $ \displaystyle~2^n\nmid n!,~~\forall n>0 $

[jordan]

Bonus: Mostrare che per ogni $ n>0 $ vale $ 2^n \nmid 2^{s_2(n)-1}n! $

Nb: $ s_2(n) $ rappresenta la somma delle cifre di n in base 2
Nb2: Dato che ogni numero ha in base 2 almeno un 1 la mia tesi è un po più forte di quella di kn
Nb3: @kn, definirlo own è un po esagerato direi..

[Haile]

Vediamo

La massima potenza di 2 che divide $ $n!$ $ è data da $ $\sum_{k=1}^{\infty} \bigg\lfloor \frac{n}{2^k} \bigg\rfloor$ $. Chiaramente non è necessario estendere la sommatoria all'infinito: ci si può fermare quando $ $2^k > n$ $, ovvero $ $k > \log_2 n$ $.

La tesi richiede quindi che per ogni n valga $ $ n > \sum_{k=1}^{\lfloor \log_2 n \rfloor} \bigg\lfloor \frac{n}{2^k} \bigg\rfloor$ $.

Ora, il RHS è massimizzato quando $ $n$ $ è una potenza di 2, e precisamente in quel caso vale $ $\sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{2^k}$ $, e la nostra tesi diventa $ $n > n \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{2^k}$ $ ovvero

$ $1 > \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{1}{2^k}$ $, e considerandola una serie abbiamo $ $1 > 1 - 2^{-\log_2 n}$ $ che è vero per ogni n finito.

[kn]

Nb3: @kn, definirlo own è un po esagerato direi..

Hai ragione, è un po' scontato come problema (però con own si fanno avanti più utenti...)

Nb2: Dato che ogni numero ha in base 2 almeno un 1 la mia tesi è un po più forte di quella di kn

Allora perché non $ \displaystyle~2^n \parallel 2^{s_2(n)}n! $?