"Base" fattoriale

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

"Base" fattoriale

Messaggio da Triarii » 03 mag 2013, 20:49

Dimostrare che ogni intero positivo può essere scritto in modo unico nella forma
$ a_1\cdot 1!+a_2\cdot 2!+...+a_n\cdot n! $ con $ 0\le a_i\le i $ per ogni $ i $
"We' Inge!"
LTE4LYF

Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: "Base" fattoriale

Messaggio da Lasker » 04 mag 2013, 15:20

Ci provo io :D
Dimostro ora per induzione che:
$ \sum_{i=1}^n {i*i!}=(i+1)!-1 $

1)Passo base :
$ 1*1!=2!-1 $

2)Passo induttivo:
$ \sum_{i=1}^n{i*i!}+(n+1)(n+1)!=(n+2)!-1 $

$ (n+1)!-1+(n+1)(n+1)!=(n+1)!*(n+2)-1 $

$ (n+1)!(n+2)=(n+1)!(n+2) $ $ \longrightarrow 0=0 $ Verificata $ \forall n \in \mathbb{N} $
Dunque i numeri rappresentabili con i primi n termini sono sempre minori (di uno) di $ (n+1)! $
Ma i diversi numeri che posso scrivere come $ \sum_{i=1}^n {a_i*i!} $ sono esattamente (n+1)! perché ciascun $ a_i $ può essere scelto in $ i+1 $ modi.
Dunque, avendo $ (n+1)! $ "cassetti" (i numeri minori di $ (n+1)! $) e $ (n+1)! $ (al massimo) "piccioni"(i diversi numeri che posso rappresentare con la sommatoria), basta dimostrare che la rappresentazione è unica.
Infatti, se ad ogni numero è associata un' unica rappresentazione, le rappresentazioni possibili dovranno per forza rappresentare tutti i numeri minori di $ (n+1)! $, essendo in pari numero.

Ora, supponiamo per assurdo che esista un numero $ m $ che abbia due diverse rappresentazioni in "base fattoriale". Allora
$ m=a_1*1!+a_2*2!+...+a_n*n! $
$ m=b_1*1!+b_2*2!+...+b_n*n! $
Li sottraggo
$ 0=(a_1-b_1)*1!+(a_2-b_2)*2!+...+(a_n-b_n)*n! $
Sostituisco ad $ (a_k-b_k) \longrightarrow c_k $
Dunque la relazione ora è
$ 0=c_1*1!+c_2*2!+...+c_n*n! $ con $ |c_k|\leq k $ $ \forall k $
Considero il più piccolo $ k $ tale che $ c_k \ne 0 $
Dunque
$ 0=c_k*k!+c_{k+1}*(k+1)!+...+c_n*n! $
Ma i termini successivi a $ c_k*k! $ sono tutti multipli di $ (k+1)! $, quindi posso scrivere la relazione come
$ 0=c_k*k!+M*(k+1)! $
$ Però |c_k*k!|<(k+1)! $
Ciò implica che $ M=0 $, e dunque anche $ c_k=0 $ $ \longrightarrow assurdo! $
Quindi esiste un' unica rappresentazione di qualunque $ m $
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: "Base" fattoriale

Messaggio da Triarii » 04 mag 2013, 18:08

Mi pare giusta ;)
"We' Inge!"
LTE4LYF

Rispondi