Pagina 1 di 1
155. Somma fattoriale
Inviato: 20 ago 2013, 17:06
da mat94
Dimostrare che per ogni numero naturale $n$ esiste un solo numero naturale $k$ e un'unica sequenza di interi $ a_1,..,a_k $ tale che $ n=a_1\cdot 1!+..+a_k\cdot k! $ , dove $ a_k\neq 0 $ e $ 0\leq a_i\leq i $ .
Re: 155. Somma fattoriale
Inviato: 21 ago 2013, 13:59
da Gottinger95
E' già stato fatto, però metto un hintarello (di come l'avevo fatto io):
Re: 155. Somma fattoriale
Inviato: 21 ago 2013, 15:39
da mat94
Ma è già stato messo sul forum? non lo sapevo

Dato che è una staffetta se l'hai risolto metti la soluzione, non fa niente che l'hai già visto

Re: 155. Somma fattoriale
Inviato: 21 ago 2013, 16:04
da Triarii
Re: 155. Somma fattoriale
Inviato: 21 ago 2013, 16:32
da Gottinger95
Osservazione. Vale \(n \cdot n! = (n+1)! - n!\), da cui si ricava il valore di questa somma telescopica:
\(\displaystyle \sum_{i=1}^n{i \cdot i!} = (n+1)!-1\)
Perciò, per le limitazioni imposte, abbiamo, per qualsiasi \(a_1, \ldots, a_n\):
\(\displaystyle \sum_{i=1}^n{a_i \cdot i!} \leq \sum_{i=1}^n{i \cdot i!} = (n+1)!-1 < (n+1)! \)
Poniamo che esistano due diverse rappresentazioni \( ( a_1, \ldots, a_n), \ \ (b_1, \ldots, b_m) \) di un numero con WLOG \(n \geq m\). Allora abbiamo:
\(\displaystyle \sum_{i=0}^n{ a_i i!} = \sum_{i=0}^m{b_i i!}\)
\(\displaystyle \sum_{i=0}^m{(a_i - b_i)i!} + \sum_{i=m+1}^n{a_i i!} = 0\)
Se vogliamo avere qualche speranza di ottenere 0 dall' LHS, i termini \(a_{m+1}, \ldots, a_n\) devono essere 0: infatti i termini della seconda somma sono positivi, e ognuno è maggiore stretto in modulo dell'intera prima somma. Perciò abbiamo ottenuto il primo punto, ossia che se esistono due rappresentazioni, allora hanno la stessa "lunghezza". Sia adesso \(j\) il più grande indice tale che \(a_j \neq b_j\) e ritorniamo alla nostra equazione:
\(\displaystyle \sum_{i=0}^j{(a_i - b_i)i!} = 0\)
\(\displaystyle |(a_j-b_j) j! |= |\sum_{i=0}^{j-1}{(b_i-a_i)i!}| \leq \sum_{i=0}^{j-1}{i \cdot i!} < j! \leq |(a_j-b_j)j! | \)
Assurdo. Perciò esiste una sola rappresentazione. Mmm, ma adesso mi tocca postare un nuovo problema? xD
Re: 155. Somma fattoriale
Inviato: 22 ago 2013, 13:59
da mat94
Non bisogna dimostrare anche l'esistenza degli $a_i$ ?
Re: 155. Somma fattoriale
Inviato: 22 ago 2013, 14:27
da Gottinger95
Si, ho dimenticato.Si può fare in due modi:
1. Per bezout, visto che il primo termine è 1, posso raggiungere tutti i numeri. Inoltre si può facilmente dimostrare che se una "rappresentazione" non rispetta le limitazioni, allora ne esiste un'altra che fornisce lo stesso numero ma che rispetta le limitazioni (sciogliendo oppure raggruppando gli \(a_i\) che non vanno bene)
2. In modo più elegante, cerchiamo di capire quanti numeri si possono rappresentare usando solo i primi \(k\) termini della "base fattoriale": il coefficiente di \(i!\) può essere scelto in \(i+1\) modi (compreso lo 0), perciò possiamo rappresentare
\(\prod_{i=1}^k{i+1} = (k+1)!\)
numeri. Ma questo numero (considerando che anche lo 0 è incluso nel conteggio) è il massimo a cui posso arrivare con \(k\) termini:
\(1+\sum_{i=1}^k{i \cdot i!} = (k+1)!\)
Perciò, visto che abbiamo dimostrato che esiste un'unica rappresentazione per ogni numero, la rappresentazione fattoriale deve prendere tutti i numeri.
Re: 155. Somma fattoriale
Inviato: 22 ago 2013, 15:03
da mat94
La prima non l'ho capita, comunque la seconda funziona

vai pure