• In questa pagina trovate:
• Frazioni egizie e numeri pratici
• Henri Delannoy e i suoi numeri
• Crittografia, antica ma resistente
• Quadrati Triangolari e Ricorrenze
• La Sezione Aurea e i Numeri di Fibonacci
• E' arrivato il 42-esimo numero primo di Mersenne!

31 Luglio 2005

1 - Frazioni egizie e difficili eredità

Per dimenticare il gran caldo estivo mi sono dedicato alla lettura di un piacevole articolo di Premchand Anne, "Egyptian fractions and the inheritance problem" [1]. Inizia con un breve racconto:

Nel Far West tre fratelli ereditano 17 cavalli. Nel testamento viene disposto che 1/2 di essi vada al primogenito, 1/3 al secondo e 1/9 al più giovane. I tre giovani sono disperati perché non sanno come fare.
Per fortuna arriva il giudice di pace, una signora molto abile e saggia. Scende da cavallo, e mette il suo bellissimo puledro in mezzo agli altri. Ora i cavalli sono 18 e si possono fare le parti. La metà (9 cavalli) va al più vecchio, un terzo (6 cavalli) al secondogenito e un nono (2 cavalli) all'ultimo.
Poiché 9 + 6 + 2 = 17, avanza un cavallo. Il giudice riprende il suo e si allontana tra gli applausi di tutti!

1/2 + 1/3 + 1/9 = 17/18
il giudice aggiunge la parte mancate 1/18, e si ottiene
1/2 + 1/3 + 1/9  + 1/18 = 1

(1) Problema del Completamento a Uno
Date k frazioni egizie 1/a_i tali che 1/a₁ + 1/a₂ + ... + 1/a_k < 1,
trovare m frazioni egizie 1/a_k+1, 1/a_k+2, ... , 1/a_k+m tali che:
1/a₁ + 1/a₂ + ... + 1/a_k+m = 1

Sembra che sia stato Fibonacci il primo a trovare un algoritmo esplicito che permette di scrivere qualsiasi razionale P/Q, minore di 1, come somma di frazioni egizie.

(2) Algoritmo di Fibonacci

1) Si ponga x₁ = P/Q.
2) Sia a₁ l'intero positivo più piccolo tale che 1/a₁ £ x₁
3) Si ponga x₂ = x₁ - 1/a₁
4) Si ripetano i passi 2) e 3) aumentando ogni volta di 1 gli indici delle x_i e delle a_i, fino a trovare una x_k nulla.

Le x_i si dicono "residui". Si procede dunque sino a residuo zero. Al termine si avrà:
1/a₁ + 1/a₂ + ... + 1/a_k-1 = P/Q.

Esempio

Sia assegnato P/Q = 16/69.

1) x₁ = 16/69
2) a₁ = 5, perché 1/5 £ 16/69 e 1/4 > 16/69
3) x₂ = x₁ - 1/a₁ = 16/69 - 1/5 = 11/345
2') a₂ = 32, perché 1/32 £ 11/345 e 1/31 > 11/345
3') x₃ = x₂ - 1/a₂ = 11/345 - 1/32 = 7/11040
2'') a₃ = 1578, perché 1/1578 £ 7/11040 e 1/1577 > 7/11040
3'') x₄ = x₃ - 1/a₃ =7/11040 - 1/1578 = 1/2903520
2''') a₄ = 2903520, perché 1/2903520 £ 1/2903520 e 1/2903519 > 1/2903520
3''') x₅ = x₄ - 1/a₄ = 0

Abbiamo ottenuto: 16/69 = 1/5 + 1/32 + 1/1578 + 1/2903520.

Nell'esempio appena visto la sequenza dei residui è:
x1 = 16/69, x2 = 11/345, x3 = 7/11040, x4 = 1/2903520, x5 = 0
La corrispondente sequenza dei numeratori è
16, 11, 7, 1, 0

Si arriva sempre ad avere residuo nullo in numero finito di passi, poiché la successione dei numeratori dei residui è strettamente decrescente. Quindi, trattandosi di interi non negativi, si deve arrivare a 0.
Per chi fosse interessato segue la dimostrazione di questo fatto:

Proposizione  La sequenza dei numeratori dei residui è strettamente decrescente.

Dimostrazione

Supponiamo di essere arrivati al residuo x = c/d. L'Algoritmo di Fibonacci prende 1/a, dove a è il minimo intero positivo tale che

(*) 1/a £ c/d
Il residuo successivo sarà x - 1/a = c/d - 1/a = (ac - d)/(ad). Supponiamo per assurdo che il nuovo numeratore non sia minore in senso stretto di c.
Si avrà allora  ac - d ³ c,   che equivale a   ac - c ³ d.  Segue che   c(a-1) ³ d
e dunque:
(**) 1/(a-1) £ c/d
La (**) contraddice la minimalità di a nella (*). Pertanto il nuovo residuo x' sarà:
x' = c'/d',   con c' = (ac - d) < c  e d' = ad.

L'algoritmo di Fibonacci è un algoritmo goloso (greedy): prende sempre la parte più grande possibile. Si potrebbe dire che è goloso ma anche educato. Dato il residuo x, non prende tutto x o x - ε (per lasciare ε, il cosiddetto "boccone della buona creanza"). Prende sempre la massima parte lecita: ovvero, nel nostro caso, la più grande fetta del tipo 1/a.

Si noti che l'algoritmo di Fibonacci fornisce sempre infinite soluzioni al problema di rappresentare P/Q come somma di frazioni egizie. Per esempio, invece di 16/69 potremmo prendere

x₁ = 16/69 - 1/6 = 3/46

Applicando l'algoritmo (2) si ottiene

3/46 = 1/16 + 1/368

e pertanto

16/69 = 1/6 + 1/16 + 1/368.

Supponiamo di avere la somma di frazioni egizie 1/2 + 1/5 + 1/11 = 87/110.

L'idea è ovviamente quella di applicare l'algoritmo a 1 - 87/110 = 23/110.

Fatto questo otteniamo 23/110 = 1/5 + 1/110. Pertanto:

1 = 87/110 + 23/110 = 1/2 + 1/5 + 1/11 + 1/5 + 1/110

L'espressione però non è valida, perché 1/5 si ripete due volte.

Proviamo allora a sviluppare 23/110 - 1/8. Troviamo 23/110 - 1/8 = 1/12 + 1/1320. Infine:

1/2 + 1/5 + 1/11 + 1/8 + 1/12 + 1/320 = 1

(3) Identità Split

1/x = 1/(1+x) + 1/(x(1+x))

Esempio:   1/5 = 1/6 + 1/30

Usiamo la (3) nell'ultimo caso visto:

1 = 87/110 + 23/110 = 1/2 + 1/5 + 1/11 + 1/5 + 1/110 = 1/2 + 1/5 + 1/11 + 1/6 + 1/30 + 1/110

(4) Algoritmo Split

Si scrive P/Q come 1/Q + 1/Q + ... + 1/Q, sommando P volte 1/Q.
Si eliminano le ripetizioni utilizzando la Identità Split tante volte quanto basta.

Esempio:   P/Q = 3/5

3/5 = 1/5 + 1/5 + 1/5 = 1/5 + 1/6 + 1/30 + 1/6 + 1/30 = 1/5 + 1/6 + 1/30 + 1/7 + 1/42 + 1/31 + 1/930

I numeri pratici (practical numbers) sono stati introdotti da A. K. Srinivasan nel 1948. Ricordiamo che σ(n) rappresenta la somma dei divisori di n (si vedano i blogs Numeri amicali e C'è un limite all'abbondanza?).

(5) Definizioni equivalenti di "numero pratico"

Definizione 1 : Un numero intero positivo n si dice pratico se ogni intero m, 1 £ m £ n, si può scrivere come somma di divisori distinti di n.

Definizione 2 : Un numero intero positivo n si dice pratico se ogni intero m, 1 £ m £ σ(n), si può scrivere come somma di divisori distinti di n.

Per esempio 10 non è pratico, infatti 4 non è somma di 1, 2, 5 o 10.
Invece 12 è pratico:

1 = 1,   2 = 2,   3 = 3,   4 = 4,   5 = 1 + 4,   6 = 6,   
7 = 1 + 6,   8 = 2 + 6,   9 = 1 + 2 + 6,   10 = 4 + 6,   
11 = 1 + 4 + 6,   12 = 12 

(6) Caratterizzazione dei numeri pratici [6] Siano 1 = d₁ < d₂ < ... < d_t = n i divisori di n.
n è pratico se e solo se per ogni s compreso tra 1 e t-1 si ha:

(6.1) d_s+1 £ d₁ + d₂ + ... + d_s + 1

Esempio con n = 12

Ci sono 6 divisori

d1 = 1    d2 = 2    d3 = 3
d4 = 4    d5 = 6    d6 = 12

Facendo variare s da 1 a 5, le condizioni (6.1) diventano:

2 £ 1 + 1
3 £ 1 + 2 + 1
4 £ 1 + 2 + 3 + 1
6 £ 1 + 2 + 3 + 4 + 1
12 £ 1 + 2 + 3 + 4 + 6 + 1

Si verifichi che le (6.1) non sono tutte valide per n = 10, che infatti non è pratico.

d1 = 1
d2 > d1
d2 £ 1 + 1

(7) Proposizione [7]

Tutte le potenze di 2 sono numeri pratici.

Dimostrazione diretta

Sia n = 2^k. Se m £ 2^k - 1, dalla espressione binaria di m vediamo che m è somma di potenze di 2 con esponenti compresi tra 0 e k-1. Queste potenze sono tutti divisori di 2^k.

Dimostrazione indiretta

Sia n = 2^k. I divisori di n sono le potenze 2^j, con 0 £ j £ k. Utilizziamo le (6.1). Nel nostro caso t = k+1, e si ha:
d_s = 2^s-1 per ogni s tra 1 e t. La riga generica delle (6.1) diventa:

2^s £ 1 + 2 + 4 + ... + 2^s-1 + 1

e questo è vero: vale infatti la uguaglianza.

Esempio

n = 2¹⁰ = 1024, m = 1000.
L'espressione binaria di 1000 è 1111101000.
Quindi 1000 = 512 + 256 + 128 + 64 + 32 + 8 è somma di divisori di 1024.

(8) Tre proprietà dei numeri pratici

(8.1) [6] Se n possiede un sottoinsieme di divisori 1 = d₁, d₂,..,d_h = n tale che ogni divisore della sequenza è al massimo due volte il precedente, allora n è pratico.

(8.2) [4] Se n è un numero pratico ed m è un intero positivo non maggiore di n, allora il prodotto mn è pratico. Nelle stesse ipotesi anche m^kn^h è un numero pratico. (Si osservi che questo implica che il prodotto di due numeri pratici è ancora un numero pratico).

(8.3) [6] Se n è un numero pratico e q è un numero coprimo con n e q < 2n, allora qn è pratico.

(9) Due teoremi di Melfi

(9.1) Ogni intero positivo pari è somma di due numeri pratici

(9.2) Esistono infiniti numeri pratici m tali che m-2 e m+2 sono pratici

E' interessante vedere una dimostrazione diretta, del tutto elementare, della osservazione fatta in (8.2):

(10) Proposizione

Il prodotto di due numeri pratici è un numero pratico

Dimostrazione

Sia p e q due numeri pratici. Si prenda un qualsiasi intero positivo k < pq. Dobbiamo provare che k è somma di divisori distinti di pq.
Dividiamo k per q:

k = aq + b   con   0 £ a £ p   0 £ b < q Poiché a £ p e p è pratico a si può scrivere come somma di divisori di p:
a = c₁ + c₂ + ... +c_m    dove i c_j sono distinti e dividono p Lo stesso vale per b:
b = d₁ + d₂ + ... +d_n    dove i d_i sono distinti e dividono q Pertanto:
k = aq + b = c₁q + c₂q + ... + c_mq + d₁ + d₂ + ... +d_n Sia i c_jq che i d_i dividono pq. Tutti i c_jq sono distinti, così come i d_i. Inoltre:
per ogni i e j    d_i £ b < q £ c_jq In conclusione abbiamo provato che k è somma di divisori distinti di pq.

(11) Proposizione - Tutti i numeri della forma 2^m-1(2^m - 1) sono pratici

Dimostrazione

Per la (7), n = 2^m-1 è pratico. Inoltre q = 2^m - 1 è coprimo con n e q < 2n. Dalla (8.3) segue che nq è pratico, che è la nostra tesi.

Corollario - Tutti i numeri perfetti pari sono pratici

Il Corollario segue immediatamente dal Teorema (54) in La Sezione Aurea e i Numeri di Fibonacci.

(12) Metodo per esprimere P/Q come somma di frazioni egizie basato sui numeri pratici [2]

Supponiamo P < Q.
Caso 1) Se Q è un numero pratico, P = d₁ + d₂ + ... +d_n, dove i d_i dividono Q. Pertanto:

P/Q = 1/(Q/d₁) + 1/(Q/d₂) + ... + 1/(Q/d_n) Caso 2) Se Q stesso non è pratico, prendiamo un N pratico maggiore di Q (per esempio - si ricordi ancora la (7) - N può essere la più piccola potenza di 2 che supera Q). Si ha:
P/Q = (PN)/(QN) Poiché PN < QN e QN è pratico per la (8.2), siamo ricondotti al Caso 1).

Esempio

P/Q = 16/69.  N = 72.    PN/QN = 1152/4968
1152 = 2 + 46 + 276 + 828    dove 2, 46, 276, 828 dividono 4968
16/69 = 2/4968 + 46/4968 + 276/4968 + 828/4968 = 1/2484 + 1/108 + 1/18 + 1/6

3 - Una congettura di Erdös

Negli anni 50 Erdös e Straus congetturarono che ogni razionale della forma 4/n, con n maggiore di 4, è uguale alla somma di tre frazioni egizie 1/a + 1/b + 1/c. Da più di cinquanta anni questa congettura resiste ad ogni tentativo di dimostrazione! Essa è stata verificata fin a 10¹⁴.
In [3] si può trovare la dimostrazione (del tutto elementare, e del tutto non ovvia) del fatto che, per ogni n dispari, maggiore di 3 e non divisibile per 3, esistono sempre a, b e c dispari tali che:

• [1] - Premchand Anne, Egyptian fractions and the inheritance problem, The College Mathematical Journal 29 (1998), 296-300
• [2] - Kevin Gong, Egyptian Fractions, UC Berkley, Math 196 Spring 1992
• [3] - Thomas R. Hagerdon, A Proof of a Conjecture on Egyptian Fractions, American Mathematical Montly 107 (2000), 62-63
• [4] - Malcolm R. Heyworth, More on Panarithmic Numbers, New Zealand Mathematics Magazine 17 (1980) 28-34.
• [5] - Giuseppe Melfi, On Two Conjectures about Practical Numbers, Journal of Number Theory 56 (1996), 205-210
• [6] - D. F. Robinson, Egyptian Fractions via Greek Number Theory, New Zealand Mathematics Magazine 16 (1979) 47-52
• [7] - B. M. Stewart, Sums of Distinct Divisors, American Journal of Mathematics 74 (1954), 779-785

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

18 Giugno 2005

1 - Henri Auguste Delannoy

Henri Auguste Delannoy (1833 - 1915)

Henri Auguste Delannoy fu uomo coraggioso, generoso e geniale.

Come gran parte degli intendenti militari Francesi, Henri Delannoy studiò alla Ecole Polytechnique, terminando gli studi a 22 anni. nel 1855. All'epoca negli archivi mantenevano una descrizione fisica degli allievi, fatto che oggi parrebbe assai strano. Queste le caratteristiche riportate: capelli scuri, fronte media, naso medio, occhi azzurri, bocca piccola, mento e faccia rotondi, altezza: 1,68.

Divenuto tenente nel 1857, partecipò alla campagna d'Italia (17 Maggio - 18 Agosto 1859) e alla battaglia di Solferino (24 giugno 1859). Fu promosso capitano nel 1863, e nel 1882 era intendente di prima classe. Lavorò dal 1866 al 1869 in Africa, ed era governatore dell'Ospedale Militare di Sidi - Bel - Abbes (in Algeria) durante una terribile epidemia di tifo.

Venne decorato con la Médaille d’Italie, la Décoration Sarde de la Valeur militaire e la Croix de la Légion d’Honneur nel 1868 e ricevette la Rosette d’Officier de la Légion d’Honneur nel 1886.

Avrebbe potuto raggiungere i vertici della carriera militare ma scelse di ritirarsi ed iniziò una seconda vita, come matematico.

Dall'inizio del 1889 visse a Guerét, capoluogo del dipartimento di la Creuse, dove proprio in questi giorni gli è stata dedicata una via. Già dal 1882 era membro della Société Mathématique de France, alla quale era stato presentato da Lucas e Laisant. Dal 1896 al 1915 fu presidente della Société des Sciences Naturelles et Archéologiques de la Creuse, tuttora assai attiva. Delannoy non si limitava alla matematica e pubblicò presso questa Società 29 articoli a carattere storico-archeologico.

Delannoy fu uno dei pochi matematici dilettanti che hanno ottenuto riconoscimenti a livello professionale. Scrisse più di una dozzina di articoli scientifici, usciti in gran parte sul Bulletin de la Société Mathématique de France. Il matematico Edouard Lucas (quello dei numeri di Lucas) nella prefazione al secondo volume delle sue Récréations mathématiques scrisse: "J’adresse mes plus vifs remerciements à mon ami sincère et dévoué, Henry Delannoy,. . . ". Dopo la morte di Lucas nel 1891, Delannoy curò, con Lemoine e Laisant, la pubblicazione del terzo e quarto volume delle Récréations mathématiques.

Henry Delannoy non smise mai di studiare e di lavorare. Alla sua morte, avvenuta all'età di 81 anni, lasciò una decina di articoli incompiuti.

[Per più ampie notizie biografiche si veda (1)]

2 - Coefficienti binomiali e multinomiali

Ricordiamo che l'espressione n! (da leggersi "enne fattoriale") denota il numero 1·2·3···n :

0! = 1 (per convenzione)
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
...
n! = n·(n-1)!

(x + y)⁴ = (x + y)(x + y)(x + y)(x + y) = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴
Dove:
x⁴ ha coefficiente 1 perché c'è un solo modo di prendere una x da tutte le parentesi
x³y ha coefficiente 4 perché ci sono 4 modi per prendere tre x da 4 parentesi
x²y² ha coefficiente 6 perché ci sono 6 modi per prendere due x da 4 parentesi
(queste sono le sei coppie di parentesi 1,2 - 1,3 - 1,4 - 2,3 - 2,4 - 3,4)
etc...

[1]
     0     0     1     2     3     4     5     6     7     8     9
     0     1     0     0     0     0     0     0     0     0     0
     1     1     1     0     0     0     0     0     0     0     0
     2     1     2     1     0     0     0     0     0     0     0
     3     1     3     3     1     0     0     0     0     0     0
     4     1     4     6     4     1     0     0     0     0     0
     5     1     5    10    10     5     1     0     0     0     0
     6     1     6    15    20    15     6     1     0     0     0
     7     1     7    21    35    35    21     7     1     0     0
     8     1     8    28    56    70    56    28     8     1     0
     9     1     9    36    84   126   126    84    36     9     1

1) Create la prima riga formata da 1 seguito da zeri
2) Create la prima colonna: tutti 1
Completate ora la tavola, dall'alto in basso e da sinistra a destra, seguendo questa regola:
3) Ogni elemento della tavola, fuori dalla prima riga e dalla prima colonna, è la somma
    dell'elemento z che ha immediatamente sopra con quello che è a sinistra di z.
Per esempio (riga 6):
6 = 5 + 1, 15 = 10 + 5, 20 = 10 + 10, 15 = 5 + 10, 6 = 1 + 5, 1 = 0 + 1, 0 = 0 + 0, ....

[2]

1. C(n,k) = n!/((n-k)!k!)
2. C(n.k) = C(n,n-k)
3. C(n,k) = C(n-1,k) + C(n-1,k-1)
4. C(n,k) è il coefficiente di x^ky^n-k in (x + y)ⁿ

Diciamo M(n₁,n₂,n₃) il numero delle possibili distribuzioni. Quanto vale M(n₁,n₂,n₃)?

Non è difficile risolvere questo problema. Ci sono C(n,n₁) modi di riporre n₁ oggetti nella scatola 1, in quanto C(n,n₁) è il numero dei sottoinsiemi con n₁ elementi che si possono prendere da un insieme con n elementi. Rimangono allora n-n₁ elementi, che di possono mettere nella scatola 2, prendendone n₂ alla volta, in C(n-n₁,n₂) modi. A questo punto rimangono n₃ = n - (n₁ + n₂) elementi, che vanno obbligatoriamente nella scatola 3. Pertanto:

Vediamo un esempio:

Calcoliamo M(2,3,1). In questo caso n = 1 + 2 + 3 = 6. Per [3] abbiamo:

M(2,3,1) = C(6,2)·C(4,3) = 15·4 = 60

Si hanno molte espressioni dello stesso numero, apparentemente diverse, perché l'ordine degli argomenti della funzione M è irrilevante. Per esempio:

M(1,2,3) = C(6,1)·C(5,2) = 6·10 = 60
M(3,1,2) = C(6,3)·C(3,1) = 20·3 = 60

Supponiamo n = n₁ + n₂ + n₃ + ... + n_k.
Per definizione M(n₁,n₂,n₃,...,n_k) è il numero delle distribuzioni di n elementi diversi in k scatole, con le restrizioni:
n₁ elementi devono stare nella scatola 1
n₂ elementi devono stare nella scatola 2
...
n_k elementi devono stare nella scatola k

[4]

1. M(n₁,n₂,n₃,...,n_k) = n!/(n₁!n₂!n₃!·...·n_k!)
2. C(n,k) = M(k,n-k)
3. M(n₁,n₂,n₃,...,n_k) = C(n₁+n₂+n₃+...+n_k,n₁)·C(n₂+n₃+...+n_k,n₂)·...·C(n_k-1+n_k,n_k-1)
4. M(n₁,n₂,n₃,...,n_k) è il coefficiente di x₁^n₁·x₂^n₂·...·x_k^n_k in (x₁ + x₂ +...+ x_k)ⁿ

3 - I numeri di Delannoy

I numeri di Delannoy contano il numero di certi percorsi sul reticolo intero nel piano.

Consideriamo nel piano cartesiano il reticolo dei punti di coordinate intere. Ci sono consentiti tre tipi di movimenti:

orizzontale, abbreviato con o, ci fa passare da (x,y) a (x+1,y).
verticale, abbreviato con v, ci fa passare da (x,y) a (x,y+1).
diagonale, abbreviato con d. ci fa passare da (x,y) a (x+1,y+1).

Per definizione il numero di Delannoy D(n,k) è il numero dei percorsi che si possono effettuare partendo dalla origine (0,0) e arrivando nel punto (n,k) soggetti alle due seguenti restrizioni:

1) Ci si può muovere solo con o, v e d. 2) Non si deve uscire dal rettangolo individuato dai vertici (0,0) e (n,k).

Esempi

[5.1] Calcoliamo D(2,2). Dobbiamo rimanere nel quadrato di vertici (0,0), (0,2), (2,2), (2,0).
Questi sono i percorsi, rappresentati come una sequenza di movimenti:
o o v v
v v o o
o v o v
v o v o
o v v o
v o o v
o d v
o v d
d o v
d v o
v o d
v d o
d d

Pertanto D(2,2) = 13

[5.2] Calcoliamo ora D(3,2). Se utilizziamo soltanto movimenti o, v per passare da (0,0) a (3,2) - rimanendo nel rettangolo - occorrono 5 passi, dei quali 3 devono essere o e 2 devono essere v. Vi sono pertanto M(3,2) = M(3,2,0) = C(5,3) = C(5,2) = 10 percorsi dove ci si muove solo verso destra o verso l'alto. Se in un qualche punto si inserisce un passo in diagonale d, questo comporta la eliminazione di un passo o e di un passo v. Se si usa 1 solo d, dovremo fare 4 passi, dei quali 2 o, 1 v e 1 d, in tutti i modi possibili. Abbiamo M(2,1,1) = C(4,2)·C(2,1) = 6·2 = 12 possibilità. Infine se usiamo 2 d, faremo 3 passi: 1 o e 2 d. Ci sono M(1,2) = M(1,0,2) = C(3,1) = 3 possibilità.

Concludendo D(2,3) = 10 + 12 + 3 = 25.

[6]
0           0           1           2           3           4           5           6           7           8           9
0           1           1           1           1           1           1           1           1           1           1
1           1           3           5           7           9          11          13          15          17          19
2           1           5          13          25          41          61          85         113         145         181
3           1           7          25          63         129         231         377         575         833        1159
4           1           9          41         129         321         681        1289        2241        3649        5641
5           1          11          61         231         681        1683        3653        7183       13073       22363
6           1          13          85         377        1289        3653        8989       19825       40081       75517
7           1          15         113         575        2241        7183       19825       48639      108545      224143
8           1          17         145         833        3649       13073       40081      108545      265729      598417
9           1          19         181        1159        5641       22363       75517      224143      598417     1462563

[7] Teorema

D(n,k) = M(n,k,0) + M(n-1,k-1,1) + M(n-2,k-2,2) + .... + M(n-j,k-j,j) + .... + M(n-k,0,k)
ovvero

D(n, k) = åM(n-j, k-j, j), ove j varia tra 0 e k

Dimostrazione

Poiché D(n,k) = D(k,n) possiamo supporre, senza restrizioni, k £ n. Per passare da P = (0,0) a Q = (n,k), rimanendo nel rettangolo di vertici P e Q, occorrono n spostamenti orizzontali e k spostamenti verticali. Se non si procede mai in diagonale, dovremo fare n+k passi, dei quali n o e k v. Abbiamo C(n+k,k) = C(n+k, n) = M(n,k) = M(n,k,0) possibilità.
In generale se decidiamo di fare j passi in diagonale (certamente sarà j £ k) dovremo eseguire:
n-j spostamenti orizzontali o
k-j spostamenti verticali v
j spostamenti diagonali d
in un ordine qualsiasi. Avremo pertanto M(n-j,k-j,j) possibilità. Sommando per j che varia da 0 a k si ottiene la formula del teorema.

[8]

In entrambe le sommatorie, j varia tra 0 e k:

[8.1] D(n, k) = åC(n+j, j)·C(n, k-j)

[8.2] D(n, k) = åC(n, j)·C(k, j)·2^j

[9]

Posto D(0, 0) = D(1, 0) = D(0, 1) = 1, per ogni n e k maggiori di 1 si ha:

D(n, k) = D(n-1, k) + D(n-1, k-1) + D(n, k-1)

Dimostrazione

Si tratta di una semplice osservazione. Possiamo arrivare a (n,k) soltanto da (n-1,k), (n-1,k-1) o (n,k-1). L'ultimo passo è obbligato:
se siamo in (n-1,k) deve essere o
se siamo in (n-1,k-1) deve essere d
se siamo in (n,k-1) deve essere v
Segue immediatamente la tesi.

Si inzia con una riga ed una colonna tutte fatte di 1.
Si costruisce l'interno della tavola procedendo da sinistra a destra e dall'alto in basso.
Un elmento x all'interno della tavola è somma di tre elementi già costruiti: quello che ha sopra - chiamiamolo z, quello a sinistra di z, e quello alla sinistra di x.

[Si veda (2), che contiene interessanti generalizzazioni]

4 - I numeri centrali di Delannoy

Poniamo:

I numeri d(n) - ovvero la diagonale della tavola [6] - vengono chiamati numeri centrali di Delannoy. Ecco i primi 11 con indice che varia da 0 a 10:

[10]

{1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453}

[11.1] d(n) = åC(n+j, j)·C(n, j)

[11.2] d(n) = åC(n, j)²·2^j

[12] per ogni indice n si ha d(n) = P_n(3)
dove P_n(x) è l'n-esimo polinomio di Legendre.

[13]

P₀(x) = 1
P₁(x) = x
per ogni n maggiore di 1:

P_n(x) =((2n-1)·x·P_n-1(x) - (n-1)·P_n-2(x))/n

[14.1]
1
x
(3/2)·x² - 1/2
(5/2)·x³ - (3/2)·x
(35/8)·x⁴ - (15/4)·x² + 3/8
(63/8)·x⁵ - (35/4)·x³ + 15/8

[14.2] P_n(x) = å C(n+j, j)·C(n, j)·((x-1)/2)^j
dove, nella sommatoria, j varia tra 0 ed n.

Dalla relazione di ricorrenza [13] si deduce allora una relazione di ricorrenza per i d(n):

[15]

d₀(x) = 1
d₁(x) = 3
per ogni n maggiore di 1:

d(n) =(3·(2n-1)·d(n-1) - (n-1)·d(n-2))/n

Riporto qui un esempio:

d(n) è il numero delle matrici con 2 righe riempite con 0 ed 1 in modo tale che:

• in ogni riga ci sono esattamente n 1
• in ogni colonna c'è almeno un 1

Nella figura sottostante si vede il caso n = 2 (d(2) = 13).

Quante altre cose interessanti e nascoste conteranno questi numeri di Delannoy?

(1) Cyril Banderier - Sylviane Schwer, Why Delannoy Numbers?, ArXiv:math.CO/0411128 (2002)

(2) John S. Caughman - Clifford R. Haithcock - J.J.P. Veerman, A note on lattice chains and Delannoy numbers, J.J.P. Veerman at Portland State University (February 17, 2005)

(3) Gàbor Hetyei, Central Delannoy Numbers and Balanced Cohen-MacAuley Complexes, UNC Charlotte (2005)

(4)Daniela Romagnoli, Algebra del Calcolo Combinatorio, Quaderni Didattici del Dipartimento di Matematica della Università di Torino (2001)

(5) Robert A. Sulanke, Objects Counted by the Central Delannoy Numbers, Journal of Integer Sequences, Vol. 6, Article 03.1.5 (2003)

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

7 Maggio 2005

§ 1

Cominciamo con l'esaminare cinque classici metodi crittografici.

1 - L'Atbash.

Si tratta di un codice ebraico. Per semplicità consideriamo il seguente alfabeto di 26 lettere italiane:

L'alfabeto viene diviso in due parti uguali, e la seconda viene scritta al contrario sotto la prima così:

abcdefghilmno
èéùàòzvutsrqp

Per codificare un messaggio si sostituisce una lettera con la lettera che le corrisponde nell'altra riga. Il processo di decodifica è identico.

Per esempio chi era scontento, e temeva di manifestarlo, invece della Frase

non ne possiamo proprio più di questo governo

inviava

qpq qò oplltèrp ompomtp otc àt nhòlip vpgòmqp

2 - Il codice di Cesare

L'idea era quella di sostituire ogni lettera con quella che segue tre passi dopo, muovendosi sull'alfabeto in modo ciclico.

Utilizziamo, come modello, il seguente alfabeto, che chiamiamo ALFA:

!"#$%&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~òàùè飧

ALFA ha 101 caratteri. Il primo carattere (numero 1) è ! mentre il carattere numero 101, l'ultimo a destra, non si vede perché è lo spazio.

Si deve pensare ai caratteri come se fossero disposti su un anello chiuso, dove ! e lo spazio sono adiacenti. Se si sostituisce ogni simbolo con quello che sta a tre passi di distanza (in senso orario) si ha che ! va in $, " va in %, ..., e lo spazio va in #.

Con questo metodo la nostra Frase diventa:

qrq#qh#srvvldpr#sursulr#sl£#gl#txhvwr#jryhuqr

Possiamo ruotare l'insieme delle lettere di un altra quantità, diversa da 3. Se per esempio facciamo 93 passi otteniamo:

fgf~f]~hgkkaYeg~hjghjag~hay~\a~im]klg~_gn]jfg

L'idea comune agli esempi 1 e 2 consiste nel sostuire una lettera dell'alfabeto con un'altra. Si applica quindi una permutazione dell'alfabeto. Un codice di questo genere viene detto codice di sostituzione monoalfabetica.

3 - La scitala spartana

La scitala è interessante anche perché si tratta di uno dei primi strumenti creati per cifrare i testi. Come si vede in figura, si avvolge un nastro intorno a un cilindro, e si scrive lungo l'asse dello stesso. Svolgendo il nastro le lettere, se lette di seguito, formano una frase senza alcun senso.

La codificazione cambia a seconda di quante volte si avvolge il nastro. Costruiamo un modello matematico semplificato della scitala. Supponiamo di avvolgere il nastro 9 volte. Ecco allora quello che accade nel processo di cifratura:

1) La Frase (che ha 45 lettere) viene divisa in blocchi di 9 lettere, scritti in righe successive (se il testo contiene un numero di caratteri non divisibile per 9, si aggiungono spazi alla fine) :

non ne po
ssiamo pr
oprio più
 di quest
o governo

Questa è la situazione del nastro avvolto.

2) Svolgere il nastro corrisponde a scrivere il messaggio per colonne. Si ottiene così il testo in cifra:

nso oospd nirig ai onmoqveo ue perppisnorùto

Se codifichiamo la Frase con blocchi di 10 lettere otteniamo una cifratura completamente diversa:

nsr voiiqenaour m ennopsoe it pùo pr oodg spio

La scitala, pur nella sua ingenuità, contiene una idea nuova rispetto ai codici di sostituzione: permutare le posizioni delle lettere. Il processo di permutare le posizioni viene detto trasposizione. I migliori risultati si ottengono alternando sostituzioni e trasposizioni.

4 - La steganografia

La cosa più furba, forse, per impedire che persone non autorizzate leggano i nostri messaggi segreti è occultare il messaggio all'interno di un altro, apparentemente innocuo.

Per esempio A e B possono convenire di leggere i testi che si scambiano tra di loro a righe alterne. Il messaggio sottostante, se letto in questo modo, racchiude in sé un secondo messaggio:

Non ne possiamo proprio più
degli attacchi dei nemici
di questo governo. Cerchiamo
di impedire che essi tentino
di farlo cadere!

Il primo libro di crittografia, Polygraphiae libri sex (Sei libri di poligrafia), fu scritto da Johannes Trithemius (1462-1516). La prima pagina del primo volume comincia così:

a     Deus		      a     clemens

b     Creator		b     clementissimus

c     Conditor		c     pius

....

Vi sono in questo libro migliaia di accoppiamenti lettera - parola. Si formano frasi con queste parole, e chi le riceve risostituisce le lettere alle parole.

Dunque "Creator Deus Conditor pius clemens" diventa "bacca".

Nel 1499 Trithemius scrisse Steganographia, in tre libri. Nei primi due libri vengono esposti sitemi atti a celare messaggi all'interno di frasi, a volte oscure. Nella proposizione:

PARAMESIEL OSHURMI DELMUSON THAFLOIN PEANO CHARUSTREA MELANY LYAMUNTO...

La prima parola PARAMESIEL denota il metodo crittografico usato nel seguito. In questo caso la convenzione è che si mettano di seguito le parole di posto pari (la seconda, la quarta, la sesta ...) :

OSHURMITHAFLOINCHARUSTREALYAMUNTO...

e nella parola ottenuta si leggano solo i caratteri di posto pari. Risultato:

SUMTALICAUTELAUT... ovvero SUM TALI CAUTELA UT...

Così come le tecniche di sostituzione e trasposizione (sia pure realizzate in modi allora impensabili) sono al centro della crittografia moderna, anche la steganografia è attualissima. I messaggi segreti possono essere celati ovunque nel mondo digitale: nelle immagini che girano a terabyte sulla rete, nei file compressi, negli MP3, nel rumore di fondo di un canale. Nel 2002 alcuni importanti giornali americani hanno diffuso la notizia che al-Queda inviava centinaia di messaggi nascosti in immagini digitali, presenti su siti assai noti. Esistono anche applicazioni difensive della steganografia, come il watermarking. Il watermarking consiste nel nascondere le informazioni riguardanti il copyrigth nei documenti accessibili in rete. In sostanza, tra un pixel e l'altro della immagine rubata e fraudolentemente pubblicata si trova il nome dell'autore!

5 - La griglia di Cardano

Si tratta di un altro metodo steganografico dovuto a Girolamo Cardanor> Bisogna predisporre una griglia con un certo numero di righe e colonne, dello stesso formato del foglio su cui scriviamo. In posizioni date la riga ha dei buchi. La griglia, con i suoi buchi, è condivisa dalla persona cui inviamo il messaggio. Sul foglio di carta scriviamo un testo qualsiasi, in modo tale che sovrapponendo al foglio la griglia, il vero messaggio si legga attraverso i buchi.
Per esempio supponiamo di avre una griglia con 9 righe e 5 colonne. Rappresentiamo gli spazi pieni con - e i buchi con O:

-----
--O--
-----
--O--
-----
-----
---O-
---O-
----O

Seguendo la formattazione scriviamo la Frase:

NON N
E POS
SIAMO
 PROP
RIO P
IU DI
 QUES
TO GO
VERNO

Chi riceve sovrappone la griglia e legge

-----
--P--
-----
--R--
-----
-----
---E-
---G-
----O

§ 2

Al termine della seconda guerra mondiale, dopo avere lottato, con successo, contro i codici tedeschi e giapponesi, gli esperti di crittoanalisi si dedicarono per divertimento a rompere i codici antichi conosciuti, e ci riuscirono in quasi tutti i casi. Due notevoli eccezioni sono costituite dal Terzo libro di Trithemius e dal Codice di Voynich.

Il terzo libro di Trithemius

Nella prefazione al libro III della Steganographia, Trithemius annuncia che il suo scopo è quello di offrire, in maniera segreta, un metodo per trasmettere testi a distanza, senza l'uso di parole, libri o messaggeri. Nel volume vi sono strani elenchi di numeri e simboli astrologici. Sotto è riportata parte di una pagina:

Per secoli gli studiosi hanno discusso sulla possibilità che in questo volume non vi fosse alcun codice cifrato, ma venissero invece rappresentate operazioni alchemiche di interesse per gli occultisti. Finalmente nel marzo del 1998 Jim Reeds della AT&T Labs ha pubblicato la soluzione. In realtà, Thomas Ernst, un professore di tedesco, aveva risolto il problema, od almeno parte di esso, alcuni anni prima, quando era ancora studente. Con notevole ingegno, perseveranza, intuizione e fortuna, Ernst e Reeds sono riusciti a scoprire la chiave nascosta ed a rivelare il messaggio. L'inizio della soluzione fu la scoperta che i numeri 650, 649, 648... rappresentavano un alfabeto di 22 lettere A, B, C... Alla fine si è ottenuto un testo abbastanza confuso, come se alcune parti si fossero perdute; quello che rimane è formato da frasi comuni in latino e tedesco della quali, per esempio, una suona più o meno così: "il latore di questa lettera è un brutto furfante ed un ladro". Il libro è stato pubblicato per la prima volta, postumo, nel 1606: sono passati 392 anni prima che si riuscisse a decifrarlo. Non male vero?

Il Codice di Voynich

Si tratta di un piccolo volume (23X18 cm) rilegato di 116 fogli, dei quali ne rimangono 102, senza titolo e senza indicazione dell'autore. Attualmante è conservato nella Beinecke Rare Book Library della Università di Yale. Il testo è scritto in una calligrafia uniforme ed elaborata, con molte illustrazioni assai curate e belle. A prima vista la lingua sembrerebbe latino, ma di latino non c'è nemmeno una parola. Non ci sono correzioni, sembra uscito perfetto dalla mente dello scrittore. Dalle illustrazioni pare che tratti di botanica, astronomia, biologia, cosmologia, farmacia e alchimia.

Foglio del Codice di Voynich

Il codice è stato trascritto in caratteri latini moderni mediante un alfabeto creato appositamente, detto EVA (European Voynich Alphabet). Sotto si vede un esempio di trascrizione:

Testo originale

fachys.ykal.ar.ataiin.shol.shory.cthres.ykor.sholdy sory.cthar.or.y.kair.chtaiin.shar.are.cthar.cthar.dan syaiir.sheky.or.ykaiin.shod.cthoary.cthes.daraiin.sa o'oiin.okeey.oteor.roloty.cth*ar.daiin.otaiin.or.okan sair.y.chear.cthaiin.cphar.cfhaiin -------- ydaraishy

Trascrizione del testo originale in EVA

Il prezioso ed arcano volumetto è stato scoperto dall'antiquario americano Wilfrid Voynich nel 1912. Secondo una lettera del Seicento che conteneva, sarebbe stato acquistato da Rodolfo II di Bavaria nel 1586 per una ingente somma (attualmente si tratterebbe - dicono - di circa 130.000 dollari). Il re era molto interessato all'occulto, e probabilmente riteneva che il testo contenesse importanti rivelazioni, scritte in modo da essere incomprensibili agli incolti. Sta di fatto che, malgrado diversi tentativi, nessuno nel 17° secolo riuscì a decifrarlo. Poi scomparve, per riapparire due secoli e mezzo dopo nelle mani dell'antiquario.

Nel 1921 il filosofo William R. Newbold sostenne la fantasiosa idea che il manoscritto fosse opera di Roger Bacon (XIII secolo), ma la sua analisi si provò infondata. Negli anni quaranta i crittografi dilettanti Joseph M. Feely e Leonell C. Strong tentarono senza successo un attacco basato sui codici di sostituzione. Venne considerato un testo in ucraino senza le vocali da John Stojko nel 1978, e uno scritto cataro nel 1987 dal medico Leo Levitov. In tutti i casi le traduzioni apparirono completamente slegate dalle illustrazioni e incoerenti.

Una delle ipotesi fatte è che il Codice Voynich sia un falso. Un testo cioè scritto ad arte, senza alcun significato, affascinante per le illustrazioni e la calligrafia, crato per essere venduto ad un ricco credulone, con la promessa di chissà quali verità nascoste, delle quali sarebbe diventato unico possessore colui che ne avesse scoperto la chiave.

Il testo però, ad una analisi statistica, appare avere caratteristiche assai particolari. Per esempio le parole con 5 o 6 caratteri sono le più frequenti, e la frequenza di quelle più lunghe o più corte diminuisce rapidamente e in modo simmetrico all'allontanarsi dal picco. Invece nelle lingue umane la distribuzione è più ampia e soprattutto è asimmetrica, a favore delle parole relativamente lunghe. Come un falsario medioevale avrebbe potuto ottenere un effetto del genere? Non certo accostando simboli a caso.

Recentemente Gordon Rugg ha dimostrato che è possibile ottenere un risultato simile utilizzando le griglie di Cardano. Rugg ha costruito effettivamente le griglie, scrivendo manualmente i testi. Vi sono nel manoscritto di Voynich altre proprietà statistiche più complesse. Per provare che anche queste caratteristiche possono emergere in documenti fabbricati ad hoc, Rugg e i suoi collaboratori stanno usando un apposito sofware per produrre su computer grandi quantità di testo, con griglie e tabelle differenti.

I lavori di Rugg tendono solo a dimostrare che il Codice Voynich potrebbe essere un falso. Questo tipo di ricerca non può arrivare ad escludere la possibilità che si tratti di un opera in codice. Il mistero rimane!

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

8 Aprile 2005

1 - Chi sono i numeri Numeri Poligonali

I numeri poligonali derivano da particolari disposizioni di punti, e sono studiati fin dalla antichità. Essi si ottengono come somme di progressioni aritmetiche, per esempio:

(1) successione: 1, 1, 1, 1, 1, ... somma: 1, 2, 3, 4, 5, ... numeri naturali
(2) successione: 1, 2, 3, 4, 5, ... somma: 1, 3, 6, 10, 15, ...numeri triangolari
(3) successione: 1, 3, 5, 7, 9, ... somma: 1, 4, 9, 16, 25, ... numeri quadrati
(4) successione: 1, 4, 7, 10, 13 ... somma: 1, 5, 12, 22, 35, ... numeri pentagonali

Le successioni (1) ... (4) partono tutte da 1.
Nella (1) d=0, la successione è costante.
Nella (2) d=1, la successione è quella dei numeri naturali.
Nella (3) e nella (4) le differenze valgono rispettivamente 2 e 3

Le successioni in grassetto sono date dalle sequenze delle somme parziali della successione che hanno a sinistra.

Esempio:
successione di partenza: 1, 2, 3, 4, 5, ...
successione delle somme parziali: 1, 1+2=3, 3+3=6, 6+4=10, 10+5=15, ...

2 - Successioni Ricorrenti Lineari

L'argomento delle successioni ricorrenti lineari è affascinante e poco noto. Certamente vale la pena di essere appreso, almeno nei suoi fondamenti.

Diciamo successione ricorrente lineare (abbreviata nel seguito con srl) di grado k una sequenza di numeri:
a₀, a₁, a₂, ... , a_n-1, ...
tale che:
(5.1) I k numeri iniziali a₀, a₁, a₂, ... , a_k-1 sono assegnati
(5.2) Per ogni n > k-1 si calcola a_n mediante l'espressione:
a_n = h₁a_n-1 + h₂a_n-2 + ... + h_ka_n-k
I numeri h_j, con j = 1, 2, ..., k, si dicono coefficienti della srl.
Vengono anche utilizzate srl di grado k non omogenee, così definite:
(6.1) I k numeri iniziali a₀, a₁, a₂, ... , a_k-1 sono assegnati
(6.2) E' assegnata una costante additiva c
(6.3) Per ogni n > k-1 si calcola a_n mediante l'espressione:
a_n = h₁a_n-1 + h₂a_n-2 + ... + h_ka_n-k + c
Il polinomio di grado k f(x):
(7) f(x) = x^k - h₁x^k-1 - h₂x^k-2 - ... - h_k-1x - h_k
viene detto polinomio di ricorrenza o polinomio caratteristico della srl che ha gli stessi h_j come coefficienti.
Come vedremo, vi sono infiniti polinomi di ricorrenza per una srl.

(8) Esempio
Sono di grande interesse le srl che hanno polinomio di ricorrenza x² - x - 1. Esse hanno relazione di ricorrenza:
(9) a_n = a_n-1 + a_n-2
perché h₁ e h₂ valgono entrambi 1.
Ci sono infinite successioni di numeri che soddisfano la (9): ognuna di esse è determinata dai due valori iniziali.
Vediamo tre esempi importanti:
(10) 1, 0, 1, 1, 2, 3 , 5, 8, 13, 21, 34, 55, ... successione T_n
(11) 0, 1, 1, 2, 3 , 5, 8, 13, 21, 34, 55, 89, ... successione F_n
(12) 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... successione L_n
La (11) è la famosissima successione dei numeri di Fibonacci. La (12) è la successione dei numeri di Lucas.
Si ricordi sempre che gli indici partono da 0, per cui, ad esempio, F₁₀ = 55.
Si noti la relazione F_n = T_n+1, valida per ogni indice n.
Poiché le ricorrenze sono lineari, una combinazione lineare di due srl (con lo stesso polinomio di ricorrenza) è ancora una srl (con il medesimo polinomio). E' allora evidente che T e F determinano tutte le altre (tecnicamente si dice che sono una base), perché:
presa una qualsiasi srl (c_n) con polinomio di ricorrenza x² - x - 1, essa è determinata completamente dai due elementi iniziali c₀ e c₁, e perciò per ogni indice n si ha
c_n = c₀T_n + c₁F_n
per esempio per ogni n,
L_n = 2T_n + F_n

(13)
Denotiamo con α e β le radici del polinomio di ricorrenza 
x2 - h1x - h2
Supporremo sempre che siano diverse da 0 e distinte tra di loro.
Valgono allora evidentemente la relazione fondamentale
(14) α2 = h1α + h2
e la relazione di ricorrenza, valida per ogni n maggiore di uno
(15) αn = h1αn-1 + h2αn-2
Lo stesso vale per β.

(16)
n		tn		un
0		1		0
1		0		1
2		h2		h1
3		h1h2		h12 + h2

(17.1) Per ogni n, αⁿ = t_n + u_nα, dove
t_n è la srl con polinomio di ricorrenza x² - h₁x - h₂ e valori inziali 1, 0
u_n è la srl con polinomio di ricorrenza x² - h₁x - h₂ e valori inziali 0, 1
Analogamente:
(17.2) Per ogni n, βⁿ = t_n + u_nβ, con gli stessi t_n e u_n.

(18)

La (18) si chiama Formula di Binet.

Si noti che la (18) vale per tutte le srl di grado 2 con valori iniziali 0 e 1!

Per esempio, nel caso dei numeri di Fibonacci si ottiene che F_n vale:

Il numero di Fibonacci F_n

Questo segue subito dalla (18) per il semplice motivo che le radici di x² - x - 1 sono
(1+Ö5)/2 e (1-Ö5)/2
Si osservi che la radice positiva è niente meno che la sezione aurea!

Denotiamo ora con S l'insieme formato da tutte le successioni di numeri. Un elemento di S è pertanto una successione, che indicheremo - a seconda delle necessità - con A, (a_n) oppure (a₀, a₁, a₂, ..., a_n, ...).

Definiamo ora due funzioni (operatori) molto interessanti di S in S che trasformano successioni in successioni.

(19.1) Prodotto di un numero per una successione
Date la costante c e la successione (a_n) poniamo
c(a_n) = (ca_n)
(19.2) Shift di una successione
Data la successione (a_n) diciamo shift di (a_n) la successione x(a_n) così definita:
x(a₀, a₁, a₂, ..., a_n, ...) = (a₁, a₂, a₃, ..., a_n+1, ...)

(20) Per definizione x^k(a_n) è la successione che si ottiene applicando lo shift x alla successione (a_n) k volte, quindi, per ogni k non negativo, si ha:
x^k(a₀, a₁, a, ...)

(21) (c_kx^k + c_k-1x^k-1 + ... + c₁x + c₀)(a_n) = c_k(a_n+k) + c_k-1(a_n+k-1) + ... + c₀(a_n)

(22.1) Consideriamo la successione di Fibonacci (F_n) = 0, 1, 1, 2, 3 , 5, 8, 13, 21, 34, 55, 89, ...
x²(F_n) = 1, 2, 3 , 5, 8, 13, 21, 34, 55, 89, ...
-2(F_n) = 0, -2, -2, -4, -6, -10, -16, -26, -42, -68, ...
(x² - 2)(F_n) = 1, 0, 1, 1, 2, 3 , 5, 8, 13, 21, ...

(22.2) Consideriamo ancora la successione di Fibonacci
(x² - x - 1)(F_n) = (1, 2, 3 , 5, 8, 13...) - (1, 1, 2, 3 , 5, 8...) - (0, 1, 1, 2, 3 , 5...) =
(0, 0, 0, 0, 0, 0...) = (0)

(22.3) Sia (c, c, c, ... ) una successione costante:
(x - 1)(c, c, c, ...) = (c, c, c, ...) - (c, c, c, ...) = (0)

(22.4) Sia (1, c, c², c³, ...) una successione geometrica:
(x - c)(1, c, c², c³, ...) = (c, c², c³, ...) - (c, c², c³, ...) = (0)

(22.5) Consideriamo la successione non omogenea con polinomio di ricorrenza x² - x - 1 (quello di Fibonacci), valori iniziali 3, 4 e costante additiva c uguale a 4:
A = (3, 4, 11, 19, 34, 57, ... )
Dal termine di indice 2 in poi ogni elemento è la somma dei due precedenti + 4. Applichiamo ora (x-1):
(x-1)A = (4, 11, 19, 34, 57, ... ) - (3, 4, 11, 19, 34, ...) = (1, 7, 8, 15, 23, ...)
Si noti che B = (x - 1)A ricorre con x² - x - 1. La costante additiva è stata eliminata. Ora:
C = (x² - x - 1)B = (0)
Se calcoliamo D = (x² - x - 1)A otteniamo:
D = (11, 19, 34, 57, ...) - (4, 11, 19, 34, ...) - (3, 4, 11, 19, ...) = (4, 4, 4, 4, ...)
Evidentemente (x-1)D = (0)
Pertanto:
(x - 1)(x² - x - 1)A = (0) = (x² - x - 1)(x-1)A

Teorema (23)
(23.1) Una successione costante ricorre con polinomio di ricorrenza (x - 1)
(23.2) Una successione geometrica di ragione q ricorre con polinomio di ricorrenza (x - q)
(23.3) Una successione A ha polinomio di ricorrenza f(x) se e solo se f(x)A = (0)
(23.4) Se A ricorre con f(x), ricorre con f(x)g(x) per qualsiasi polinomio g(x)
(23.5) Se A non è omogenea, ha polinomio f(x) e costante c, allora A è una srl con polinomio di ricorrenza (x - 1)f(x)

(24) Definizione
Data la successione A = (a_n), poniamo:
σA = (a₀, a₀+a₁, a₀+a₁+a₂, a₀+a₁+a₂+a₃, ...)

Se A è una srl, anche σA lo è:
(25) Se A ricorre con polinomio f(x), allora σA ricorre con polinomio (x-1)f(x)
Dimostrazione - Poniamo B = σA. Allora l'elemento di posto n di (x-1)B è:
(a₀+a₁+a₂+ ... +a_n+1) - (a₀+a₁+a₂+ ... +a_n) = a_n+1. Pertanto:
(x-1)B = xA
Quindi:
(x-1)f(x)B = f(x)((x-1)B) = f(x)xA = x(f(x)A) = x(0) = 0
Si noti che abbiamo utilizzato due fatti:

i polinomi commutano tra di loro

f(x)A = (0) per (23.3)

(26) Diciamo somma A + B la successione: (a₀+b₀, a₁+b₁, a₂+b₂, ..., a_n+b_n, ...)

(27.1) Se A e B ricorrono entrambe con il polinomio f(x),
allora A + B ricorre con lo stesso polinomio f(x)
Dimostrazione -
f(x)(A+B) = f(x)A + f(x)B = (0) + (0) = (0).

(27.2) Se A e B ricorrono, rispettivamente, con polinomi f(x) e g(x),
allora A + B ricorre con il polinomio prodotto f(x)g(x)
Dimostrazione -
f(x)g(x)(A+B) = f(x)g(x)A + f(x)g(x)B = g(x)(f(x)A) + f(x)(g(x)B) = (0) + (0) = (0).

(27.3) Le (27.1) e (27.2) continuano ovviamente a valere se al posto della somma A + B mettiamo una combinazione lineare di A e B sA + tB, dove s e t sono due costanti.

Fissiamo il polinomio di ricorrenza di grado 2 f(x) = x² - hx + k. Supponiamo che le sue radici siano distinte e diverse da 0.

Allora f(x) = (x - α)(x - β), h = (α + β), e k =α β, come si ricava immediatamente. Sia per α che per β vale la relazione di ricorrenza (15), pertanto le successioni formate dalle loro rispettive potenze (αⁿ) e ( βⁿ) sono ricorrenti con f(x). Esse sono di importanza fondamentale. perché generano linearmente tutte le altre.

Teorema (28)

(28.1) (Formule di Binet) Se (a_n) è una qualsiasi successione ricorrente con polinomio f(x), allora esistono s e t tali che:

per ogni n a_n = sαⁿ + tβⁿ
Dove:
s = (a₁ - a₀β)/(α - β)
t = (a₀α - a₁)/(α - β)

Dimostrazione - Abbiamo detto più volte che le sequenze (αⁿ) e (βⁿ) ricorrono con polinomio f(x). Per le (27.1) e (27.3) anche la sequenza z_n = sαⁿ + tβⁿ ricorre con f(x). Poiché (a_n) e (z_n) hanno lo stesso polinomio di ricorrenza di grado 2, esse sono identiche se e solo se coincidono sui due valori iniziali. Calcoliamo allora s e t in modo tale che si abbia
a₀ = z₀ = sα⁰ + tβ⁰ = s + t
a₁ = z₁ = sα¹ + tβ¹ = sα + tβ
Risolvendo il sistema si ottiene proprio:
s = (a₁ - a₀β)/(α - β)
t = (a₀α - a₁)/(α - β)

(28.2) (inversione delle formule di Binet) Siano s, t, α e β quattro numeri qualsiasi con l'unica restrizione che α e β siano diversi tra loro e non nulli. Allora la successione

a_n = sαⁿ + tβⁿ è ricorrente con polinomio x² - (α + β)x +αβ
Dimostrazione - E' sufficiente osservare che α e β sono gli zeri di f(x) e pertanto le successioni delle potenze di α e β ricorrono con f(x). Il risultato segue utilizzando ancora le (27.1) e (27.3)

(28.3) In generale, se α₁, α₂, ..., α_k sono k numeri non nulli e diversi tra loro, si ha il seguente risultato:

una successione numerica (a_n) è ricorrente con polinomio
f(x) = (x-α₁)(x-α₂) ... (x-α_k) se e solo se esistono k costanti t₁, t₂, ... , t_k tali che, per ogni n, a_n = t₁α₁ⁿ + t₂α₂ⁿ + ... +t_kα_k^k (28.4) (Teorema del quadrato) Se (a_n) è una qualsiasi successione ricorrente con polinomio g(x) = x² - hx + kallora la successione dei quadrati (a_n²) è data da:a_n² = e_n + Ckⁿ, dove:
e_n ricorre con polinomio g₂(x) = x² - (h²-2k)x + k², e C è costante Inoltre (a_n²) ha polinomio di ricorrenza
g₃(x) = x³ - (h² - k)x² + k(h² - k)x - k³
Dimostrazione -
Per il punto 1 si ha a_n = sαⁿ + tβⁿ.
(*) a_n² = s²α²ⁿ + t²β²ⁿ + 2st(αβ)ⁿ = s²(α²)ⁿ + t²(β²)ⁿ + 2stkⁿ = e_n + Ckⁿ
La (*) si è ottenuta ricordando che αβ = k. Si è posto inoltre e_n = s²(α²)ⁿ + t²(β²)ⁿ.
Per il punto 2 e_n ricorre con polinomio x² - (α² + β²)x + (αβ)².
Ora αβ = k e α² + β² = (α + β)² - 2αβ = h² - 2k.
Quindi e_n ricorre proprio con polinomio g₂(x) = x² - (h²-2k)x + k².
Inoltre kⁿ ricorre con (x - k) e pertanto, per le (27.2) e (27.3), (a_n²) ricorre con polinomio prodotto (x - k)g₂(x) = g₃(x).

Esempi di applicazioni del Teorema (28)
(1)
Consideriamo la srl P = (p_n) con polinomio x² - 3x + 3, e valori iniziali p₀ = 1, p₁ = 3. Questi sono i primi valori:
1, 3, 6, 9, 9, 0, -27, -81, -162, -243, -243, 0, 729, 2187, 4374, 6561, 6561, 0, -19683, -59049, -118098, -177147, -177147, 0, 531441, 1594323, 3188646, 4782969, 4782969, 0, ...

Come si vede, ci sono patterns ben precisi. Per esempio:

se n = 6k + 5 allora p_n = 0
se n = 6k allora p_n = (-1)^k 3^3k
... etc ... (quali sono gli altri patterns, e perché ci sono?)

Le radici di x² - 3x + 3 sono:

α = (3 + iÖ3)/2
β = (3 - iÖ3)/2

Calcolando s e t come in (28.1), si ottiene:

s = (1 - iÖ3)/2
t = (1 + iÖ3)/2
dove i è l'unità immaginaria (i² = -1).
pertanto si ha:

p_n = ((1 - iÖ3)/2)((3 + iÖ3)/2)ⁿ + ((1 + iÖ3)/2)((3 - iÖ3)/2)ⁿ

(2)
Poniamo α = 7 e β = 3. Per (28.2), presi comunque s e t, la sequenza:

a_n = s 7ⁿ + t 3ⁿ ricorre con polinomio x² -10x + 21, ovvero a_n = 10a_n-1 - 21a_n-2
Con s = 2 e t = -1, otteniamo la successione:
1, 11, 89, 659, 4721, 33371, 234569, 1644899, 11523041, 80687531, 564891449 ...
Con s = 31 e t = -30, otteniamo la successione:
1, 127, 1249, 9823, 72001, 513727, 3625249, 25464223, 178512001, 1250371327, 8754961249 ...

(3)
Per (28.3), la successione

2ⁿ - 3ⁿ +5ⁿ, ricorre con polinomio (x - 2)(x - 3)(x- 5) = x³ -10x² + 31x - 30. Questo significa che, per ogni n maggiore di 2 si ha:

a_n = 10a_n-1 -31a_n-2 + 30a_n-3 Ecco i primi 10 valori:
1, 4, 20, 106, 560, 2914, 14960, 76066, 384320, 1933954, 9707600, ...

(4)
Vediamo infine una applicazione del Teorema del quadrato.

Consideriamo la successione P = (p_n) definita nel punto (1). Abbiamo h = k = 3.
Per (28.4)
(*) p_n² = e_n + C3ⁿ
dove e_n ricorre con polinomio g₂(x) = x -3x +9.
L'espressione di e_n è data nella dimostrazione di (28.4):

(**) e_n = s²(α²)ⁿ + t²(β²)ⁿ.

I valori di s, t, α e β sono dati nel punto (1). Dalla (**) si ricavano allora i valori iniziali di (e_n):

(***) e₀ = -1, e₁ = 3

Poiché p₀² = 1 da (*) e (***) si ricava C = 2.
Pertanto:

p_n² = e_n + 2·3ⁿ

Questi sono i primi valori delle successioni (p_n²) e (e_n):

(p_n²) = 1, 9, 36, 81, 81, 0, 729, 6561, 26244, 59049, ...
(e_n) = -1, 3, 18, 27, -81, -486, -729, 2187, 13122, 19683, -59049, ... Infine, sempre dalla (28.4) otteniamo che il polinomio di ricorrenza di (p_n²) è:

g₃(x) = x - 6x + 18x - 27

Ora possiamo tornare ai numeri poligonali.

3 - Alcune proprietà dei numeri poligonali

Come si è visto all'inizio, le successioni dei numeri poligonali derivano da progressioni aritmetiche. Per questo motivo introduciamo una notazione specifica:

(29)
Denotiamo con Ari(d), la progressione aritmetica che ha differenza d e inizia da 1:
1, 1+d, 1+2d, ..., 1+nd, ... Il termine n-esimo di Ari(d), dove - come sempre - l'indice n inizia da 0, è 1+nd.

l'n-esimo numero q-gonale. I numeri triangolari sono i 3-gonali, i quadrati sono i 4-gonali e così via. Come si è detto i numeri poligonali sono le successioni delle somme parziali delle Ari(d). Precisamente, utilizzando le notazioni introdotte finora:

Si noti il q-2: i numeri 3-gonali (triangolari) sono le somme parziali di (1, 2, 3, 4, 5, ...) = Ari(1), e così via.

Si racconta che Gauss trovò la formula per il calcolo dei numeri triangolari quando aveva dieci anni, alle elementari. Per punizione l'esuberante scolaresca doveva calcolare la somma dei numeri da 1 a 100. I bimbi, temendo il peggio, iniziarono a calcolare:

1+2=3
3+3=6
6+4=10
10+5=15
....

mmm... (questo è il pensiero Gaussiano)
1 + 100 = 101
2 + 99  = 101
....
vale per tutte le coppie!
....
50 + 51 = 101
....
50 coppie in tutto...
totale:
50·101 = 5050
era facile, è bravo il maestro, in fondo!

E' facile ora ottenere una formula per il calcolo diretto dell'n-esimo numero q-gonale.

Poniamo d = q-2. Allora Pn(q) è la somma dei primi n termini di Ari(d):
Pn(q) = 1 + (1+d) + (1+2d) + (1+3d) + (1 + (n-1)d) =
n + d(1 + 2 + 3 + ... +(n-1)) = n + dPn-1(3)

ovvero

La formula (33) è veramente bella! Tra l'altro essa può essere estesa, così com'è, a tutti gli indici interi, anche negativi. Possiamo costruire una tavola infinita nelle quattro direzioni, dove al posto (q, n) - q-esima riga, n-esima colonna - mettiamo P_n^(q).

Una piccola parte di questa tavola si può vedere qui sotto.

(34) Tavola dei numeri poligonali Pn(q)
    -5    -4    -3    -2    -1     0     1     2     3     4     5
   -65   -44   -27   -14    -5     0     1    -2    -9   -20   -35  -2
   -50   -34   -21   -11    -4     0     1    -1    -6   -14   -25  -1
   -35   -24   -15    -8    -3     0     1     0    -3    -8   -15   0
   -20   -14    -9    -5    -2     0     1     1     0    -2    -5   1
    -5    -4    -3    -2    -1     0     1     2     3     4     5   2
    10     6     3     1     0     0     1     3     6    10    15   3
    25    16     9     4     1     0     1     4     9    16    25   4
    40    26    15     7     2     0     1     5    12    22    35   5
    55    36    21    10     3     0     1     6    15    28    45   6
    70    46    27    13     4     0     1     7    18    34    55   7
    85    56    33    16     5     0     1     8    21    40    65   8

Veniamo ora alle ricorrenze.

(35)
Ari(d) ricorre con polinomio (x-1)² = x² - 2x + 1.
Dimostrazione - Si osserva facilmente che Ari(d) è la successione non omogenea con:

grado 1

valore iniziale 1

polinomio di ricorrenza u(x) = x-1

costante additiva d.
Dunque, per (23.5), il polinomio di ricorrenza di Ari(d) è (x-1)u(x) = (x-1)².

Esempi.
Ari(1) = (1, 2, 3, 4, 5, 6, ...), 10 = 2·9 - 8.
Ari(3) = (1, 4, 7, 10, 13, ...), 31 = 2·28 - 25.
....

Teorema (36)
Fissato q, la successione P_n^(q) ha polinomio di ricorrenza
(x-1)³ = x³ - 3x² + 3x - 1
ovvero, per ogni n:
P_n^(q) = 3P_n-1^(q) - 3P_n-2^(q) + P_n-3^(q)

Pertanto le colonne formano progressioni aritmetiche. Dalla (35) otteniamo:

Teorema (38)
Fissato n, la successione P_n^(q) ha polinomio di ricorrenza
(x-1)² = x² - 2x + 1
ovvero, per ogni q:
P_n^(q) = 2P_n^(q-1)-P_n^(q-2)

Sulle righe:
P₅⁽⁸⁾ = 3P₄⁽⁸⁾ - 3P₃⁽⁸⁾ + P₂⁽⁸⁾ =
3·40 - 3·21 + 8 = 65.
P₀^(-2) = 3P_-1^(-2) - 3P_-2^(-2) + P_-3^(-2) =
3·(-5) - 3·(-14) + (-27) = 0.
Sulle colonne:
P₅⁽⁸⁾ = 2P₅⁽⁷⁾- P₅⁽⁶⁾ =
2·55 - 45 = 65.

4 - I numeri quadrati triangolari

Immaginiamo una compagnia di soldati disposti in quadrato. E' una struttura molto solida, simmetrica, ugualmente disposta sui quattro lati, stabile, probabilmente neutrale o difensiva. All'improvviso il quadrato si scioglie e si ricompone in forma di triangolo. Ben più temibile formazione, puntuta e direzionale, dinamica e forse minacciosa. E' possibile?
Ebbene sì. Pensiamo a 36 soldati in un quadrato di lato 6.

x x x x x x
x x x x x x
x x x x x x
x x x x x x
x x x x x x
x x x x x x
6 x 6 = 36

       x
      x x
     x x x
    x x x x
   x x x x x
  x x x x x x
 x x x x x x x
x x x x x x x x
8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

Ricordando il paragrafo precedente, i numeri quadrati triangolari sono gli interi che sono al tempo stesso P_n⁽³⁾ e P_m⁽⁴⁾:

Per definizione M è quadrato triangolare se e solo se esistono m, n tali che:
(39) M = n(n+1)/2 = m²

2m2 = n2 + n =
(n + 1/2)2 - 1/4.
8m2 = (2n + 1)2 - 1.
(40)(2n + 1)2 -  2(2m)2 = 1

(41) x² - 2y² = 1

(42) Se M è quadrato triangolare, assegnato come nella (39), allora x e y definiti da:
x = 2n+1, y = 2m
sono soluzioni della (41).
Viceversa se x, y sono soluzioni della (41), allora i seguenti interi n ed m:
n = (x-1)/2, m = y/2
determinano il numero quadrato triangolare M dato dalla (39).

Ci sarà estremamente utile un ambiente algebrico, particolare esempio di anello degli interi algebrici. Questi anelli sono di grandissima importanza in teoria dei numeri. Il lettore interessato, anche se profano, non si inquieti, e non tema. L'analisi che segue è diretta, e del tutto elementare.

(43) Definizione
Poniamo A = Z[Ö2] = {a + bÖ2: a,b Î Z}

Detto in parole: A è l'insieme di tutti i numeri della forma a + br, dove sia a che b sono interi relativi ed r è la radice quadrata di 2.

(44.1) (a + bÖ2) + (c + dÖ2) = (a+c) + (b+d)Ö2

(44.2) (a + bÖ2)(c + dÖ2) = (ac+2bd) + (ad+bc)Ö2

(45) Definizione di norma
Diciamo norma di a + bÖ2 il numero N(a + bÖ2) = (a + bÖ2)(a - bÖ2) = a² - 2b²

(46) N è moltiplicativa

Dati α e β in A, N(αβ) = N(α)N(β)

Appare dunque sorprendentemente utile la banale constatazione del fatto che:

(48) N(1 + Ö2) = -1

(49) Per ogni k ≥ 1 N(γ^2k) = 1

(50) Se x e y sono interi positivi e N(x + y Ö2) = 1 allora
x + yÖ2 è una potenza pari di γ

Pertanto, lavorando come come in (13) ... (17), otteniamo che

Posto γⁿ = a_n + b_nγ le successioni a_n e b_n ricorrono con il polinomio g(x), ovvero:

(51.1) a_n+2 = 2a_n+1 + a_n
(51.2) b_n+2 = 2b_n+1 + b_n

Dimostrazione -
γⁿ = a_n + b_nγ = a_n + b_n(1 + Ö2) = (a_n+b_n) + b_nÖ2.
Pertanto w_n = b_n e ricorre, come b_n, con g(x).
Inoltre v_n è la somma di a_n e b_n, che ricorrono entrambe con g(x). Quindi anche v_n ricorre con g(x) per la (27.1). I valori iniziali si ricavano direttamente.

Dalla discussione fatta finora segue che le soluzioni della equazione di Pell x² -2y² = 1 sono esattamente le coppie di interi (v_2n, w_2n), dove v_n e w_n sono dati dal Teorema (52). Se ricordiamo la (42), otteniamo il seguente risultato:

Vediamo quali sono i primi elementi della successione dei lati:

Sequenza dei w_n: 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, ...
Sequenza dei q_n ottenuta dalla (53): q₀ = 0, q₁ = 1, q₂ = 6, q = 35, q₄ = 204, q₅ = 1189, ...
Si ricordi che gli indici iniziano con 0, e pertanto gli elementi di indice 2n pari sono quelli di posto dispari nella successione, il primo, il terzo etc...

Teorema (54) Per ogni n, q_n = v_nw_n
Dimostrazione - Calcoliamo γ²ⁿ in due modi.
γ²ⁿ = v_2n + w_2nÖ2.
γ²ⁿ = (γⁿ)² = (v_n + w_nÖ2)² = v_n²+ 2w_n² + 2v_nw_nÖ2.

Confrontando i coefficienti si ottiene:

v_2n = v_n²+ 2w_n²
w_2n = 2v_nw_n

Il risultato segue infine dal Teorema 53

sequenza v_n =  1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119 ...
sequenza w_n = 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741 ...
la sequenza q_n è il prodotto delle due, termine a termine:
q_n = 0, 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214, 46611179 ...

Dimostrazione - Poniamo η = γ². L'identità γ²ⁿ = v_2n + w_2nÖ2
diventa ηⁿ = v_2n + 2q_nÖ2,
dove si è tenuto conto anche del Teorema (53). Ora η è 3 + 2Ö2. Posto θ = 3 - 2Ö2, η e θ sono gli zeri di
x - 6x + 1
Questo è polinomio di ricorrenza di (q_n), come ormai dovrebbe essere chiaro. Naturalmente lo è anche della successione
v_2n = (v₀, v₂, v₄, ..., v_2n, ... ) = (1, 3, 17, 99, 577, 3363, ... ).

Corollario (56) Per ogni n, q_n = 6q_n-1 - q_n-2, con le condizioni iniziali q₀ = 0 e q₁ = 1.

Dal Teorema (55) e dalla (18), tenendo conto che le radici di x - 6x + 1 sono:

3 + 2Ö2

3 - 2Ö2
otteniamo direttamente la seguente espressione per i q_n:

Corollario (57) Per ogni n, q_n = ((3 + 2Ö2)ⁿ - (3 - 2Ö2)ⁿ))/(4Ö2)

Teorema 58
(Può essere utile alla comprensione una rilettura dell' esempio che segue il Teorema (28)).

(58.1) Si consideri la srl e_n così definita:

1. e₀ = 1/16
   
2. e₁ = 17/16
   
3. e_n = 34e_n-1 - e_n-2, per ogni n maggiore di uno

Allora per ogni n:
Q_n = e_n - 1/16
(58.2) Per ogni n maggiore di uno si ha:
Q_n = 34Q_n-1 - Q_n-2 + 2
(58.3) Per ogni n maggiore di due si ha:
Q_n = 35Q_n-1 - 35Q_n-2 + Q_n-3 Dimostrazione
(58.1) Dal Teorema del Quadrato e dal Teorema 55 sappiamo che
Q_n = q_n² = e_n + C (si noti che in questo caso k = 1)
dove la sequenza e_n ha polinomio di ricorrenza x² - 34x + 1, le cui radici sono α² e β².
Si tratta solo di determinare i valori iniziali e₀, e₁, e la costante C.
Dalla dimostrazione di (28.4) vediamo che:
e_n = s²(α²)ⁿ + t²(β²)ⁿ
dove α e β sono le due radici di x² - 6x + 1. Visto che q₀ = 0, e q₁ = 1, da (28.1) si ottiene:
s = 1/(4Ö2), t = -1/(4Ö2)
Pertanto e₀ = s² + t² = 1/32 + 1/32 = 1/16, e
e₁ = (1/32)(α² + β²) = 34/32 = 17/16.
La costante C si ricava ora da:
Q₀ = 0 = e₀ + C = 1/16 + C. Dunque C = -1/16.

(58.2) Dal punto precedente:
Q_n - 34Q_n-1 + Q_n-2 = (e_n - 34e_n-1 + e_n-2) - (1/16 - 34/16 + 1/16) =
0 - (-2) = 2.

(58.3) Questo segue direttamente da (28.4).
Infatti g₃(x) = x - 35x + 35x - 1, poiché h = 6 e k = 1.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

4 Marzo 2005

1 - La Sezione Aurea

Nel capitolo VII del Timeo, Platone riferisce queste parole di Socrate:

Il "legame" di cui qui si parla è evidentemente la proporzione geometrica:

P : Q = Q : R

Il rapporto tra P e Q è uguale a quello tra Q e R.
Q è detto termine medio della proporzione, o medio proporzionale.

Si noti che

Q² = P·R

Pertanto un rettangolo di lati P ed R è equivalente (cioé ha la stessa area) ad un quadrato di lato Q.

Nella proposizione 11 del libro II degli Elementi, Euclide si chiedeva:

Come dividere un segmento in modo che il rettangolo che ha per lati l' intero segmento e la parte minore sia equivalente al quadrato che ha per lato la parte maggiore.

Per quanto detto il problema è equivalente a questo:

Dividere un segmento dato in due parti tali che la parte maggiore sia media proporzionale tra la parte minore e l'intero segmento.

Una soluzione classica è la seguente:

Figura 1

Dato il segmento AB costruiamo un cerchio di uguale diametro e ad esso tangente in B. Tracciamo la secante AD. E' noto che la tangente AB è il termine medio della proporzione tra AD e AC. Ovvero:

(1) AD : AB = AB : AC

Dalla (1) e dalla costruzione di Figura 1 si ricava:

(AD-AB) : AB = (AB-AC) : AC
AC : AB = EB : AC
AE : AB = EB : AE

e infine:

(2) EB : AE = AE : AB

La (2) prova che effettivamente la costruzione di Figura 1 permette di dividere un qualsiasi segmento AB in due parti AE e EB tali che il rettangolo di lati AB, EB è equivalente al quadrato di lato AE.

Il rapporto AE:EB (o, ciò che è lo stesso, il rapporto AB:AE) viene detto sezione aurea. Si noti che questo rapporto è indipendente dalla lunghezza AB del segmento di partenza.

2 - Il Rettangolo Aureo

Un rettangolo tale che il rapporto tra il lato maggiore e quello minore sia la sezione aurea viene detto rettangolo aureo.

Figura 2

Nella Figura si vede un rettamgolo di lati ab e bc, dove bc è uguale a ae e, come nella Figura 1, si ha:

ab:ae = ae:eb = sezione aurea

Poiché bc è uguale a ae il rapporto tra il lato maggiore e quello minore è la sezione aurea e pertanto il rettangolo abcd è un rettanglo aureo. Levando da abcd il quadrato di lato ae rimane il rattangolo ebcf. Poiché

bc:eb = ae:eb = sezione aurea

anche ebcf è un rettangolo aureo. Possiamo concludere che:

Se da un rettangolo aureo si sottrae il quadrato costruito sul lato minore, rimane un rettangolo aureo.

Chiaramente questa costruzione si può ripetere quante volte si vuole.

Figura 3

Si determina così una sequenza infinita di rettangoli aurei, dove ognuno si ottiene dal precedente levando il massimo quadrato in esso contenuto.

Guardando attentamente, in Figura 3 si osservano nove rettangoli aurei.
In questa direzione si precipita vertiginosamente verso l'infinitamente piccolo. Ma si può anche seguire il cammino opposto:

Se, dato un rettangolo aureo, si costruisce un quadrato sul suo lato maggiore, il rettangolo risultante è aureo.

Figura 4

Nella Figura 4 si parte dal rettangolo aureo iniziale R e si aggiungono in sequenza quattro quadrati, ottenendo quattro nuovi rettangoli aurei R1, R2, R3 e R4, dove:

R1 = R + q1
R2 = R1 + q2
R3 = R2 + q3
R4 = R 3+ q4

Osserviamo che, in entrambe le costruzioni, i rettangoli che si ottengono hanno la stessa forma (infatti la forma di un rettangolo è determinata completamente dal rapporto dei lati), Essi crescono o rimpiccioliscono mantenendo inalterata la forma.
Le medesime costruzioni si possono applicare a partire da un qualunque rettangolo nel piano, ma - se esso non è aureo - daranno luogo a rettangoli di forme diverse.

Se si parte da un rettangolo R nel piano si noterà che, ad ogni passo, sia verso l'interno che verso l'esterno, ci sono due possibilità di sviluppo della figura, perché il quadrato si può togliere (o aggiungere) da un lato o dall'altro. Ad ogni passo il rettangolo ruota di 90 gradi. Se si fissa un verso di rotazione e si toglie (o si aggiuge) il quadrato sempre dalla stessa parte (ruotando come osservatori solidali con esso) si ottiene una figura frattale. Supponiamo di procedere all'infinito, di riempire R con la costruzione verso l'interno e la parte rimanente del piano con quella verso l'esterno. Se ora ci solleviamo e guardiamo la tassellazione ottenuta (il disegno delle piastrelle) essa apparirà uguale a quasiasi distanza! Se ci avviciniamo al centro, dove i rettangoli diventano piccolissimi, e facciamo uno zoom (guardiamo con una lente di ingrandimento) vediamo sempre la stessa figura!

3 - Il numero d'oro

Fino ad ora abbiamo trattato della sezione aurea come di un rapporto tra lunghezze, il cosiddetto rapporto aureo. A questo rapporto corrisponde un numero, (il numero d'oro) che ora calcoleremo.

Ricordiamo la

(2) EB : AE = AE : AB

Poniamo

x = AE
y = EB

Poiché AB è la lunghezza del segmento intero si ha:

AB = x + y

e dalla (2) si ottiene l'equazione:

(3) x² = y (x + y)

Dividendo entrambi i lati per y² e riordinando si ha:

(4) (x/y)² - x/y -1 = 0

Si noti che x/y è il valore di AE:EB, cioé il valore numerico della sezione aurea. La (4) ha due soluzioni, che sono:

x/y = (1 + Ö5)/2
x/y = (1 - Ö5)/2

Soltanto la prima è accettabile, in quanto la seconda è negativa.

Solitamente la sezione aurea viene denotata con la lettera greca Φ (phi maiuscolo)

Abbiamo allora dimostrato che:

(5) Φ = (1 + Ö5)/2

Approssimativamente (con 50 decimali dopo la virgola) Φ vale:

(6) Φ = 1.61803398874989484820458683436563811772030917980576...

Dalla (4) si ottiene subito la relazione fondamentale:

(7) Φ² = 1 + Φ

Moltiplicando entrambi i lati della (7) per Φ^{n - 2} si ottiene la relazione di ricorrenza per Φ:

(7') Φⁿ = Φ^n-2 + Φ^n-1

E' facile ora calcolare il reciproco di Φ.
Dividendo entrambi i lati della (3) per x² e riordinando si ha:

(8) (y/x)² + y/x -1 = 0

Anche la (8) ha due soluzioni, che sono:

y/x = (-1 + Ö5)/2
y/x = (-1 - Ö5)/2

Ancora una volta soltanto la prima è accettabile, perché la seconda è negativa.

Di solito il reciproco della sezione aurea viene denotato con la lettera greca φ (phi minuscolo).

Pertanto:

(9) φ = (-1 + Ö5)/2

La parte decimale di φ è identica a quella di Φ perché:

(10) Φ = 1 + φ

Ne segue che φ vale:

(11) φ = 0.61803398874989484820458683436563811772030917980576...

Dalla (8) si ottiene subito la relazione fondamentale:

(12) φ² = 1 - φ

Moltiplicando entrambi i lati della (12) per φ^{n - 2} si ottiene la relazione di ricorrenza per φ:

(12') φⁿ = φ^n-2 - φ^n-1

Ci sono altre relazioni utili. Dalla definizione stessa di φ abbiamo:

(13) Φ = 1/φ

La (13) con la (10) dà:

(14) Φ = 1 + 1/Φ

Giocando con i rettangoli aurei, come nel paragrafo 2, mi sono posto alcuni problemi. Uno di essi è il seguente:

C'è una relazione semplice tra le lunghezze dei lati del rettangolo iniziale e quelle dell'n-esimo rettangolo costuito?

Consideriamo la fuga verso l'interno. Supponiamo che il lato minore del rettangolo iniziale (rettangolo 0) sia lungo 1 (questo significa semplicemente che si misurerà tutto usando la lunghezza del lato minore come unità di misura). Allora, per definizione di rettangolo aureo, il lato maggiore sarà lungo Φ.
Il secondo rettangolo (rettangolo 1) ha lato maggiore uguale al lato minore del primo, quindi affinché si mantenga il rapporto aureo, i suoi lati avranno lunghezze:

lato maggiore = 1
lato minore = 1/Φ

Il terzo rettangolo (rettangolo numero 2 della costruzione) ha lato maggiore uguale al minore del precedente. Quindi affinché si mantenga il rapporto aureo, i suoi lati avranno lunghezze:

lato maggiore = 1/Φ
lato minore = 1/Φ²

E' ora immediato provare, per induzione, che

(15) I lati del rettangolo n-esimo (nella costruzione verso l'interno) hanno lunghezze:
lato maggiore = 1/Φ^n-1
lato minore = 1/Φⁿ

Dalla (13) si ottiene subito la

(15') I lati del rettangolo n-esimo (nella costruzione verso l'interno) hanno lunghezze:
lato maggiore = φ^n-1
lato minore = φⁿ

E' un risultato interessante. Consideriamo la successione dei rettangoli R_o (quello iniziale), R₁, R₂, ..., R_n,... Da quanto visto le lunghezze dei lati minori di questi rettangoli formano la successione:

φ⁰ = 1, φ, φ², ...., φⁿ, ...

Si tratta di una progressione geometrica di ragione φ.

Sommando i termini della successione si ha la serie geometrica:

Serie Aurea: 1 + φ + φ² + .... + φⁿ + ...

E' ben noto che la somma di una serie geometrica di ragione r minore di 1 è finita e vale:

(16) 1/(1 - r)

Dunque, utilizzando la (12) si ha:

(17) La somma della Serie Aurea vale 1/φ²

Equivalentemente:

(17') La somma della Serie Aurea vale Φ²

O ancora, dalla (7):

(17'') La somma della Serie Aurea vale 1 + Φ

Da questa si ricava immediatamente:

(18) Φ = φ + φ² + .... + φⁿ + ...

Possiamo arrivare da soli a questi risultati, anche senza conoscere la (16), partendo dal solo fatto che la somma della nostra serie esiste ed è finita:

Denotiamo con α la somma della Serie Aurea,
α = 1 + φ + φ2 + .... + φn + ...
raccogliendo φ si ha:
α = 1 + φ (1 + φ + φ2 + .... + φn + ...)
ovvero
α = 1 + φ α
e infine
α = 1/(1 - φ)

La somma dei primi 10 termini della Serie Aurea dà

2.604878371253470009248...

e solo il primo decimale è corretto. La somma dei primi 100 termini dà

2.618033988749894848202...

con 20 cifre corrette dopo la virgola.

Con la Serie Aurea ci si può divertire, si possono ottenere senza fatica risultati sorprendenti. Facciamo un esempio:

1 + Φ = 1 + φ + φ2 + .... + φn + ... =
1 + (φ + φ2) + (φ3 + φ4) + ... =
1 + (1 + φ) φ + (1 + φ) φ3 + ... = 
1 + (1 + φ) (φ + φ3 + φ5 + ...) =
1 + Φ (Somma delle potenze dispari di φ)
Pertanto la somma delle potenze dispari di φ vale 1.

Conseguentemente:

La somma delle potenze pari di φ vale Φ.

Esaminiamo ora la costruzione dei rettangoli aurei verso l'esterno. Partiamo dallo stesso R₀ di prima, di lati 1 e Φ. Poniamo S₀ uguale a R₀e denotiamo con S₁, S₂, S₃... la sequenza dei rettangoli via via generati.

La regola è la seguente:

Sn+1 si ottiene da Sn costruendo un quadrato
sul lato maggiore di Sn

Ne segue immediatamente che:

Il lato minore di S_n+1 è uguale a quello maggiore di S_n

Il lato maggiore di S_n+1 è la somma dei due lati di S_n

Il rettangolo S0 ha lati (minore e maggiore), come si è detto, 1 e Φ. 
S1 ha lati Φ e (1 + Φ) = Φ2.
S2 ha lati Φ2 e (Φ + Φ2) = Φ3.
etc.
In questo calcolo abbiamo usato la relazione di ricorrenza (7').

Concludendo, abbiamo dimostrato che

(19) I lati del rettangolo n-esimo (nella costruzione verso l'esterno) hanno lunghezze:
lato maggiore = Φⁿ⁺¹
lato minore = Φⁿ

Naturalmente per ottenere questo risultato sarebbe stato sufficiente usare la regola di costruzione e il fatto che il rapporto tra i lati rimane sempre Φ. E' però molto interessante, e utile, avere una dimostrazione diversa che usa la ricorrenza.

4 - L'apparizione dei Fibonacci

Supponiamo di fissare un segmento AB come unità di misura. Siamo allora in grado di costruire, con riga e compasso, segmenti di lunghezza φ e Φ. Per esempio la costruzione della Figura 1 ci fa subito trovare φ, che è AE. Possiamo immediatamente costruire Φ prolungando AB (che vale 1) di un segmento uguale a AE. Per la (10) il segmento risultante ha lunghezza Φ.

E' possibile - dato un intero n positivo - costruire, con riga e compasso, i rettangoli R_n e S_n?

Visti i risultati (15') e (19) la domanda è equivalente a:

E' possibile - dato un intero n positivo - costruire, con riga e compasso, segmenti di lunghezza Φⁿ e φⁿ?

Tentiamo di scrivere ogni Φⁿ nella forma a + b Φ, con a e b interi.

Se n è 0, Φ⁰ è 1. Dunque a, b valgono, rispettivamente, 1 e 0.
Se n è 1, Φ¹ è Φ. Dunque a, b valgono, rispettivamente, 0 e 1.
Se n è 2, Φ² è 1 + Φ, per la (7). Pertanto a e b valgono 1 entrambi.
Se n è 3, Φ³ è Φ + Φ² per la (7'). Dunque, per il risulato precedente, Φ³ vale 1 + 2 Φ. In questo caso a e b sono, rispettivamente, 1 e 2.
E' chiaro come si può proseguire. Nella tavola sottostante si riportano i valori di a e b per n che va da 0 a 10:

(20)
n	a	b
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21
9	21	34
10	34	55

Chi ha visto almeno una volta la successione dei numeri di Fibonacci, la riconoscerà immediatamente nelle due colonne sottostanti ad a e b.

Leonardo Pisano, detto Fibonacci, fu un grande matematico e visse tra il 1170 e il 1250. Nel 1202 scrisse il Liber Abaci, uno dei capolavori della letteratura matematica. Nel terzo capitolo di questo libro Fibonacci poneva un problema riguardante una popolazione ideale di conigli:

Ipotesi:

Una coppia di conigli matura produce ogni mese una coppia immatura.

Dopo un mese dalla nascita una coppia immatura diventa matura.

Nessun coniglio muore.

All'inizio c'è una coppia immatura.
Domanda:

Quante coppie ci sono dopo un anno?

Diciamo F_n il numero delle coppie di conigli al mese n, e calcoliamo:

A gennaio c'è una coppia immatura A: F1 = 1
A febbraio c'è una coppia matura A: F2 = 1
A marzo A produce una coppia immatura B: F3 = 2
Ad aprile A produce una coppia immatura C, e B matura: F4 = 3
A maggio ci sono certamente A, B e C. C matura.
A e B producono due coppie immature: F5 = 5
Etc. etc. 

La legge è ora evidente:

(21) F_n = F_n-1 + F_n-2

La legge è formalmente identica alla (7'), ed è esattamente questo il motivo per cui i numeri di Fibonacci appaiono nella tavola (20).

Abbiamo pertanto trovato i numeri interi (a e b) che cercavamo. Ora sappiamo che:

(22) Φⁿ = F_n-1 + F_n Φ

Quindi i rettangoli aurei esterni si possono effettivamente costruire con riga e compasso, a partire da un segmento U di lunghezza 1 e da un segmento V di lunghezza Φ. Per esempio per disegnare S₉ dobbiamo tracciare i due lati, che hanno lunghezze Φ⁹ e Φ¹⁰. Dalla 22 Φ⁹ si ottiene riportando di seguito su una retta 21 copie di U e 34 copie di V. Per il lato maggiore occorrono 34 copie di U e 55 copie di V.

Passiamo alla sequenza dei rettangoli interni, cioé alla costruzione con riga e compasso delle quantità φⁿ. Seguiamo la stessa tattica che abbiamo usato prima.

Tentiamo di scrivere ogni φⁿ nella forma c + d φ, con c e d interi.

Se n è 0, φ⁰ è 1. Dunque c, d valgono, rispettivamente, 1 e 0.
Se n è 1, φ¹ è φ. Dunque c, d valgono, rispettivamente, 0 e 1.
Se n è 2, φ² è 1 - φ, per la (12). Pertanto c è 1 mentre d è -1.
Se n è 3, Φ³ è φ - φ² per la (12'). Dunque, per il risulato precedente, φ³ vale -1 + 2 φ. In questo caso c e d sono, rispettivamente, -1 e 2.
La (23) è l'analogo della tavola (20):

(23)
n	c	d
0	1	0
1	0	1
2	1	-1
3	-1	2
4	2	-3
5	-3	5
6	5	-8
7	-8	13
8	13	-21
9	-21	34
10	34	-55

E' facile ora concludere che:

(24) φⁿ = (-1)ⁿ (F_n-1 - F_n φ)

Per disegnare R₉ dobbiamo disporre delle lunghezze φ⁸ (il lato maggiore) e φ⁹ (il lato minore). Supponiamo di avere i segmenti U e W di rispettive lunghezze 1 e φ. Otteniamo φ⁸ in questo modo: partiamo da un punto su una retta e riportiamo 13 volte U procedendo verso destra, quindi invertiamo la direzione e riportiamo 21 volte φ. Si procede allo stesso modo per φ⁹.

E' istruttivo vedere insieme la (22) e la (24):

(22) Φⁿ = F_n-1 + F_n Φ
(24) φⁿ = (-1)ⁿ (F_n-1 - F_n φ)

Poiché

(-φ)ⁿ = (-1)ⁿ φⁿ

moltiplicando entrambi i lati della (24) per (-1)ⁿ otteniamo:

(22) Φⁿ = F_n-1 + F_n Φ
(24') (-φ)ⁿ = F_n-1 - F_n φ

Sottraendo la (24') dalla (22) si hanno le:

(25) Φⁿ - (-φ)ⁿ = F_n (Φ + φ)

cioé:

(25')

Ricordiamo ora la (5) e la (9);

(5) Φ = (1 + Ö5)/2
(9) φ = (-1 + Ö5)/2

Da queste e dalla (25') si ottiene per F_n la seguente espressione:

(26)

La (26) è veramente un risultato straordinario! Ricordiamo che i numeri di Fibonacci sono definiti da una relazione ricorsiva: si ottiene l'elemento n-esimo sommando i due precedenti. Apparentemente quindi per calcolare F₁₀₀ è necessario conoscere F₉₉ e F₉₈. Invece la (26) dà F₁₀₀, o F_n, in un colpo solo, senza richiedere la conoscenza degli elementi precedenti.

Inoltre la formula (26) contiene potenze di numeri irrazionali, mentre F_n è un numero intero!

5 - Il più nobile di tuti i numeri!

Il questo paragrafo parleremo di uno strumento matematico poco noto ma estremamente utile e potente: le frazioni continue.

L'espressione in frazione continua (abbreviato FC) di un numero α è la seguente:

(27)

I coefficienti che appaiono nella (27) sono chiamati quozienti parziali.

Se α è irrazionale la FC che lo esprime è infinita. Questo è il caso che ci interessa. Se la FC si taglia ad un certo punto si ottiene una frazione, un numero razionale, che viene detto convergente di α.

Diciamo P_k/Q_k il k-esimo convergente.

Con semplici calcoli troviamo:

P₀/Q₀ = a₀ = a₀/1
P₁/Q₁ = a₀ + 1/a₁ = (1 + a₀a₁)/a₁
P₂/Q₂ = a₀ + 1/(a₁ + 1/a₂)) = (a₀ + a₂ + a₀a₁a₂) /(1 + a₁a₂)

I convergenti si possono calcolare ricorsivamente:

(28)
Dati:
P₀ = a₀, Q₀ = 1
P₁ = 1 + a₀a₁, Q₁ = a₁
Per ogni k > 1 si ha:
P_k = a_kP_k-1 + P_k-2
Q_k = a_kQ_k-1 + Q_k-2

Vediamo ora come si determinano i quozienti parziali a_k. Ricordiamo che con [z] si intende la parte intera di z, ovvero il più grande intero minore o uguale a z.

(29) - Procedimento per la generazione dei quozienti parziali di α
Poniamo α₀ = α e a₀ = [α₀].
Per ogni k > 1 definiamo α_k e a_k così:
α_k = 1/(α_k-1 - a_k-1)
a_k = [α_k]

E' facile calcolare lo sviluppo in FC di una irrazionalità quadratica Ön. Proviamo con Ö3:

(30) Sviluppo in frazione continua di Ö3
α₀ = Ö3, a₀ = [Ö3] = 1.
α₁ = 1/(α₀ - a₀) = 1/(Ö3 - 1)
e, moltiplicando sopra e sotto per Ö3 + 1:
α₁ = (Ö3 + 1)/2.
a₁ = [α₁] = 1.
α₂ = 1/(α₁ - a₁) = 1/((Ö3 + 1)/2 - 1) = 2/(Ö3 - 1)
e, moltiplicando sopra e sotto per Ö3 + 1:
α₂ = Ö3 + 1.
a₂ = [α₂] = 2.
α_k si ripetono, pertanto:
Ö3 = [1, 1, 2, 1, 2, 1, 2, ... ].

Sussiste il notevole teorema (che in parte era già noto a Euclide):

(31)
Un numero α ha FC periodica se e solo se α = (a + Ön)/b
dove a, b sono interi qualsiasi (ovviamente b ¹ 0) ed n è un intero positivo non quadrato.

Inoltre:

(32)
Se α = Ön, con n positivo non quadrato allora:
1) Il periodo comincia subito dopo a₀.
2) L'ultimo termine a_mdel periodo è sempre uguale a 2a₀.
3) La parte di periodo a₁, a₂, ..., a_m-1 è una palindrome.
Ovvero:
Ön = [a₀, a₁, a₂, a₃, ...., a_m-1, 2a₀, a₁, a₂, a₃, ..., a_m-1,2a₀, ... ]
dove [a₁, a₂, a₃, ..., a_m-1] = [a_m-1, a_m-2, a_m-3, ..., a₁]

Come esempio di quanto asserito nella (32) esaminiamo la FC di Ö2005:

Ö2005 = [44, 1, 3, 2, 21, 1, 16, 1, 21, 2, 3, 1, 88, 1, 3, 2, ... ]
Il periodo termina con 88 e [1, 3, 2, 21, 1, 16, 1, 21, 2, 3, 1] è una palindrome.

La FC di α serve a creare una successione di approssimazioni sempre migliori di α. Queste approssimazioni sono i convergenti P_k/Q_k.
Per semplificare le notazioni poniamo

C_k = P_k/Q_k

Si dimostra che:

(33)
1) La successione dei convergenti C_k ha come limite α
2) Per ogni k C_2k < α < C_2k+1
3) |α - C_k| < 1/(Q_kQ_k+1)

La (33.1) non è particolarmente interessante, a prima vista. Ci sono infinite sequenze di numeri razionali che convergono ad α. La più ovvia, è più usata, è quella data dalla espressione decimale infinita di α. Prendiamo come esempio un personaggio unico, potente e famoso: π.

π = 3,1415926535897932384626433832795028841971...

La sequenza dei razionali:

(34)
3/1, 31/10, 314/100, 3141/1000, 31415/10000, ....

coverge a π.

Se sviluppiamo π in FC troviamo:

(35)
π = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1 ...]
e la sequenza dei convergenti è (da C₀ a C₁₂):
3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317, 312689/99532, 833719/265381, 1146408/364913, 4272943/1360120, 5419351/1725033, 80143857/25510582, ...

I razionali della (34) approssimano tutti π per difetto, mentre la (33.2) dice che i convergenti della (35) "colpiscono" una volta a sinistra e una volta a destra del bersaglio. Tutti i pari sono a sinistra e tutti i dispari a destra. Ma la cosa più importante è la precisione dei "colpi"!

Dalle (28) e (33.3) si ricava che un convergente C_k è una approssimazione particolarmente efficace quando a_k+1 fa un salto di grandezza rispetto ai precedenti quozienti parziali. Nel tratto iniziale di π questo avviene per k uguale a 1 e a 3.

(36)
Nelle (35) leggiamo che
C₁ = 22/7
ora 22/7 = 3,142... approssima π con due decimali esatti e
C₃ = 355/113 = 3.1415929... approssima π con sei decimali esatti!

Quanto detto nella (36) non è un caso, infatti vale questo formidabile risultato:

(37)
I convergenti C_k = P_k/Q_k di α sono le migliori approssimazioni possibili ad α.
Lo sono in questo senso molto preciso:
Tra tutte le frazioni i cui denominatori sono minori di una data quantità, quella che è più vicino ad α è sempre uno dei convergenti di α.

Questo è il motivo per cui certe frazioni, come 22/7 (Archimede, 287-212 AC) e 355/113 (Zu Chongzhi, 429-500) sono note fin dall'antichità.

Veniamo ora alla nostra amata sezione aurea Φ. Determiniamo la sua FC con il procedimento (29)

(38)
Φ₀ = Φ, a₀ = [Φ] =1.
Φ₁ = 1/(Φ -1) = Φ per la relazione fondamentale (7).
Dunque a₁ = [Φ₁] = 1. Da questo punto tutto si ripete e infine:
Φ = [1, 1, 1, 1, 1, .... ]

Calcolando i convergenti a Φ con le (28) otteniamo la sequenza:

1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89, 233/144, 377/233 ...

Ovviamente li riconosciamo, sono loro, i Fibonacci! Pertanto, abbiamo scoperto che:

(39)
La sequenza dei convergenti a Φ è così fatta:
per ogni k > 1
C_k-2 = F_k/F_k-1

Immediatamente cosegue che:

(40)
Sia F_k il k-esimo numero di Fibonacci, con k > 1:
1) La successione F_k/F_k-1 converge alla sezione aurea Φ
2) Le frazioni F_k/F_k-1 sono le migliori approssimazioni possibili a Φ

Poiché i quozienti parziali della FC di Φ sono tutti 1, da quanto detto sopra risulta immediatamente che tra tutti i numeri irrazionali Φ è quello che viene approssimato più lentamente dai suoi convergenti!

Per questo motivo alcuni chiamano Φ il più irrazionale dei numeri. Altri, poiché Φ si lascia avvicinare meno facilmente di qualsiasi altro, lo chiamano il più nobile degli irrazionali.

6 - I numeri di Fibonacci e i numeri primi

I numeri di Fibonacci appaiono nelle soluzioni di moltissimi problemi combinatoriali e generano infinite e meravigliose identità aritmetiche.

Ecco alcune delle loro proprietà:

(41)
1) F₁ + F₂ + F₃ + ... + F_n = F_n+2 - 1
2) F₁² + F₂² + F₃² + ... + F_n² = F_nF_n+1
3) F₁ + F₃ + F₅ + ... + F_2n-1 = F_2n
4) F_n-1 F_n+1 - F_n² = (-1)ⁿ
5) Se m divide n, allora F_m divide F_n

Dalla (41.4) si deduce immediatamente che due Fibonacci consecutivi sono sempre coprimi, cioé non hanno divisori diversi da 1 in comune.

La (41.5) è molto interessante: evidenzia un legame tra la divisivilità degli indici e quella dei relativi Fibonacci. Da essa si ottiene:

(42)
Se F_n è primo, allora n = 4, oppure n è primo.

Purtroppo il viceversa della (42) non vale, per esempio

F₁₉ = 1921 = 13 · 113

Attualmente è noto che F_n è primo per i seguenti valori di n:

n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 81839

Rimane aperta la seguente

(43) Congettura:
F_n è primo per infiniti indici n

Una delle caratteristiche più interessanti dei Fibonacci è che

(44)
Dato un qualsiasi primo p, esiste un n tale che p divide F_n

Dalla (44) e dalla (41.5) segue subito che

(45)
Dato un qualsiasi primo p, p divide infiniti F_n

E' spontaneo chiedersi: dato il primo p, come trovare esplicitamente un n tale che p divide F_n? A questa domanda sappiamo rispondere!
Ricordiamo che

Con a mod n si denota il resto della divisione di a per n
Esempi: 10 mod 3 = 1, 10 mod 5 = 0, 15 mod 6 = 3, ...

(46) Teorema
Supponiamo p primo.
p divide F_p-1 se p mod 5 =1 o p mod 5 = 4, altrimenti p divide F_p+1

Per esempio:

....
17 divide F₁₈ = 2³·17·19, perché 17 mod 5 = 2
19 divide F₁₈, perché 19 mod 5 = 4
23 divide F₂₄ = 2⁵·3²·7·23, perché 23 mod 5 = 3
....

Esiste una importante generalizzazione dei numeri di Fibonacci:

(47)
Diciamo successione lineare ricorsiva di grado 2 (abbreviato con SLR), una sequenza di numeri a_n così definita:
a₀ = A,
a₁ = B,
a_n+2 = P a_n+1 + Q a_n
dove A, B, P, Q sono numeri assegnati.

La successione dei Fibonacci è una SLR con parametri
A = 0, B = 1, P = 1, Q = 1

Una delle più notevoli SLR è la seguente, che denotiamo con L, dovuta a Lucas:

(48) Definizione della successione L
L è la SLR di parametri A = 2, B = 4, P = 4, Q = -1
I primi 20 termini di L sono:
2, 4, 14, 52, 194, 724, 2702, 10084, 37634, 140452, 524174, 1956244, 7300802, 27246964, 101687054, 379501252, 1416317954,5285770564, 19726764302, 73621286644, 274758382274

La sequenza L è intimamente legata ai numeri perfetti attraverso i numeri primi di Mersenne.
I numeri perfetti appassionavano i matematici di 2500 anni fa, e sono anche oggi oggetto di attive ricerche.

(49) Definizione di numero perfetto
Un numero n si dice perfetto
se la somma dei suoi divisori (compreso se stesso) è uguale a 2n.

Per esempio :
12 = 1 + 2 + 3 + 6,
56 = 1 + 2 + 4 + 7 + 14 + 28,
992 = 1 + 2 + 4 + 8 + ... + 496.
I primi quattro numeri perfetti sono 6, 28, 496 e 8128.

Sono noti 42 numeri perfetti, tutti pari. Malgrado recenti tentativi di dimostrazione, rimane aperta la:

(50) Congettura
Non esistono numeri perfetti dispari

Per elencare i 42 numeri perfetti noti ci vorrebbe un volume di centinaia di pagine, perché i più grandi di essi hanno milioni di cifre! E' possibile però identificarli esattamente, mediante i numeri primi di Mersenne.

(51) Definizione di numero di Mersenne
diciamo n-esimo numero di Mersenne l'intero
M_n = 2ⁿ - 1

(52)
diciamo primo di Mersenne un numero di Mersenne primo.

Si vede facilmente che:

(53)
M_n è primo solo se n è primo
Purtroppo non vale il "se e solo se". Per esempio:
M₁₁ = 23·89.

Tra l'insieme dei numeri perfetti pari e l'insieme dei primi di Mersenne esiste una corrispondenza biunivoca, espressa dal:

(54) Teorema
N è un numero perfetto pari se e solo se:
N = M_p 2^p-1 con M_p primo

Dunque, come si fa a trovare i numeri perfetti pari? Si cercano i primi di Mersenne M_p.
Ma, come si fa a vedere se, dato il primo p, M_p è effettivamente primo?
La risposta a questa domanda segna anche la fine di questa nostra breve avventura matematica. E' uno splendido teorema che lega in modo indissolubile la sequenza L di Lucas ai primi di Mersenne, e quindi ai numeri perfetti:

(55) Teorema
M_p è primo se e solo se
M_p divide L_n
con n = 2^p-2

Il 42-esimo numero primo di Mersenne (e quindi il 42-esimo numero perfetto pari) è stato trovato appena qualche giorno fa, si veda il mio Blog precedente.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

2 Marzo 2005

E' arrivato il 42-esimo numero primo di Mersenne!

225.964.951 - 1 è primo!

Il 18 febbraio 2005, il tedesco Martin Nowak ha scoperto il più grande numero primo noto: 2^25.964.951 - 1.
Questo numero ha 7.816.230 cifre!
Il dottor Novak è un chirurgo oculista e dilettante matematico, e da parecchio tempo partecipa alla GIMPS (Great Internet Mersenne Prime Search). Utilizza ben 24 computers per questa ricerca. La dimostrazione della primalità di questo gigante ha richiesto più di cinquanta giorni di calcolo da parte di un PC Pentium 4, 2,4 GHz.
Il risultato è stato verificato in cinque giorni da Tony Reix, di Grenoble, con l'uso di 16 Itanium CPU Bull NovaScale 5000 HPC e di un sofware molto potente, creato appositamente dallo spagnolo Guillermo Ballester.
I primi di Mersenne sono in corrispondenza biunivoca con i numeri perfetti.

Sono disponibili anche:
Il 41-esimo primo di Mersenne
Il 40-esimo primo di Mersenne
L'elenco dei 42 primi di Mersenne noti

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.