Rappresentabilitร  dei naturali in base arbitraria

Teorema

Sia bโˆˆN con bโ‰ฅ2. Ogni numero nโˆˆN รจ rappresentabile in base b, cioรจ esiste una successione {ฮตi}iโˆˆN composta da interi 0โ‰คฮตi<bi, che sia definitivamente nulla, ovvero per la quale esiste un valore kโˆˆN per cui ฮตi=0ย โˆ€i>k, e tale che n=โˆ‘i=0โˆžฮตiโ‹…bi. Inoltre, se esiste un'altra tale successione {ฮตiโ€ฒ}iโˆˆN, vale ฮตiโ€ฒ=ฮตi per ogni iโˆˆN.

Dimostrazione

Esistenza

Ogni n รจ rappresentabile in base b?
Procediamo per induzione su nโˆˆN di seconda forma.
n=0 (BASE DELL'INDUZIONE)
Osserviamo che essendo n=0 posso esprimere 0 come una somma polinomiale di zeri.
n=0=โˆ‘iโˆˆN0โ‹…bi

nโ‰ฅ1,โˆ€k<nโŸนn (PASSO INDUTTIVO)
Assumiamo per ipotesi induttiva che tutti i kโˆˆN, con k<n si possa rappresentare in base b.
Dobbiamo dimostrare che anche n ammette una tale rappresentazione in base b.
Consideriamo la divisione euclidea tra n e b.

n=qโ‹…b+r,ย ย 0โ‰คr<|b|

Per ipotesi sappiamo che bโ‰ฅ2, quindi vale q<qโ‹…bโ‰คqb+r=n
Poichรจ q<n, grazie all'ipotesi induttiva, q si puรฒ rappresentare in base b, ovvero โˆƒ{ฮดi}iโˆˆI in Ib definitivamente nulla e $$q = \underline{\sum_{i = 0}^{\infty}\delta_i \cdot b^i}$$
Segue che:

n=(โˆ‘i=0โˆžฮดiโ‹…bi)โ€•b+r=โˆ‘i=0โˆžฮดiโ‹…bi+1+r

Sia ora r=ฮต0. Effettuando un cambio di indice (j=i+1), otteniamo:

n=ฮต0+โˆ‘j=1โˆžฮดjโˆ’1โ‹…bj=ฮต0b0+ฮด0b1+ฮด1b2+...=โˆ‘iโˆˆNย ฮตibi

Il passo induttivo รจ stato fatto. Grazie al principio di induzione di seconda forma, ogni n รจ rappresentabile in base b.

Unicitร 

Possono esistere due diverse rappresentazioni per un n?
Procediamo per induzione su nโˆˆN di seconda forma.

n=0 (BASE DELL'INDUZIONE)
Se n=0 allora tutti gli addendi della sommatoria saranno nulli โŸนฮตi=0ย ย โˆ€iโˆˆN

n>0,โˆ€k<nโŸนn (PASSO INDUTTIVO)
Sia n>0. Assumiamo che ogni kโˆˆN con k<n ammette una sola rappresentazione in base b (ipotesi induttiva). Dobbiamo provare che ciรฒ รจ vero anche per n.
Siano {ฮตi}iโˆˆN, {ฮตiโ€ฒ}iโˆˆN due successione definitivamente nulle. Proviamo che ฮตi=ฮตiโ€ฒย ย โˆ€iโˆˆN. Osserviamo che:

n=โˆ‘i=0โˆžฮตiโ‹…bi=ฮต0+b(โˆ‘i=1โˆžฮตiโ‹…biโˆ’1)n=โˆ‘i=0โˆžฮตiโ€ฒโ‹…bi=ฮต0โ€ฒ+b(โˆ‘i=1โˆžฮตiโ€ฒโ‹…biโˆ’1)

dove ฮต0,ย ฮต0โ€ฒ sono i resti delle divisioni di n per b. Ma per l'unicitร  della divisione euclidea vale ฮต0=ฮต0โ€ฒ.
Stesso discorso per i quozienti, che inoltre risultano per definizione <n. Segue, cambiando gli indici della sommatoria:

q=โˆ‘j=0โˆžฮตj+1โ‹…bj=โˆ‘j=0โˆžฮตj+1โ€ฒโ‹…bj<n

In conclusione si ha che ฮตi=ฮตiโ€ฒย ย โˆ€iโˆˆN.
Il passo induttivo รจ stato fatto. Dunque, grazie al principio di induzione di seconda forma, ogni nโˆˆN ammette una sola rappresentazione in base b.