Algoritmo di Ada Lovelace per i numeri di Bernoulli

L'algoritmo di Ada Lovelace (nata Ada Byron) permette di calcolare i numeri di Bernoulli. Questo algoritmo è noto soprattutto per essere stato il primo programma della storia dell'informatica.

Nota G, diagramma di Ada Lovelace: fu il primo algoritmo per computer pubblicato

La formula utilizzata

Come si vede dal diagramma in figura e dal testo relativo disponibile in lingua inglese, Ada Lovelace nell'implementare il suo algoritmo si servì della seguente formula:

$0=-{1 \over 2}{{2n-1} \over {2n+1}}+B_{2}{{2n} \over 2}+B_{4}{{2n(2n-1)(2n-2)} \over 4!}+B_{6}{{2n(2n-1)...(2n-4)} \over 6!}+...+B_{2n}$

dove abbiamo sostituito gli indici dispari usati da Ada con i pari secondo la moderna notazione dei Numeri di Bernoulli. Utilizzando il fattoriale decrescente possiamo scrivere in forma compatta:

${1 \over 2}{{2n-1} \over {2n+1}}=\sum _{k=1}^{n}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}$

essendo il ${(2n)}^{\underline {2n-1}}=(2n)!$ la precedente equivale a

$B_{2n}={1 \over 2}{{2n-1} \over {2n+1}}-\sum _{k=1}^{n-1}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}~~~per~n>1~~~~~~~per~n=1~~~B_{2}={1 \over 2}{{2-1} \over {2+1}}={1 \over 6}$

Le fonti concordano con Ada stessa, sul fatto che questa formula derivi dalla funzione generatrice e anche nel fornire solo un accenno di dimostrazione per giustificarlo:

${\frac {x}{e^{x}-1}}=:\sum _{k=0}^{\infty }{\frac {{x}^{k}}{k!}}B_{k}$

La funzione generatrice può considerarsi una uguaglianza fra serie formali di potenze o fra funzioni analitiche; in questo caso per la convergenza della serie si chiede che x abbia valore assoluto minore di 2π (il raggio di convergenza della serie stessa).

È sicuramente più semplice mostrare invece che la formula usata dalla Byron non è altro che la consueta formula di ricorrenza:

$B_{m}=-{1 \over {m+1}}\sum _{j=0}^{m-1}{m+1 \choose {j}}B_{j}~~~~ossia:~~~\sum _{j=0}^{m}{m+1 \choose {j}}B_{j}=0~~~~~~(con~m>0~e~B_{0}=1)~$

resa più efficiente per il calcolo automatico. Per questo è sufficiente notare che:

$\sum _{k=1}^{n-1}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}={\frac {1}{2n+1}}\sum _{k=1}^{n-1}{{2n+1} \choose {2k}}B_{2k}$

e che

${\frac {1}{2n+1}}\sum _{k=0}^{1}{{2n+1} \choose {k}}B_{k}={\frac {1}{2n+1}}({{2n+1} \choose {0}}(1)+{{2n+1} \choose {1}}(-{\frac {1}{2}}))=$

$={\frac {1}{2n+1}}(1+(2n+1)(-{\frac {1}{2}}))={\frac {1}{2n+1}}(-{\frac {1}{2}})(-2+2n+1)=-{\frac {1}{2}}{\frac {2n-1}{2n+1}}$

Come si può controllare nella nota G in figura questa è la funzione utilizzata da Ada dato che ai suoi tempi, come aveva indicato anche Jacob Bernoulli nel suo "Ars Conjectandi" più di un secolo prima i numeri di Bernoulli cominciavano dopo i primi due attuali che quindi vanno sostituiti con i loro valori numerici per ottenere la formula usata. Nella nota Ada scrive $B_{1}B_{3}B_{5}...$ che chiaramente corrispondono ai nostri $B_{2}B_{4}B_{6}...$ .

Bibliografia

• (EN) Luigi F. Menabrea, Nota G di Ada Lovelace, in Sketch the analytical engine invented by Charles Babbage, Bibliothèque Universelle de Genève, 1842. URL consultato il 19 giugno 2017.
• Giorgio Pietrocola, Dialogo con una formula d'altri tempi (PDF), su SUPSI. URL consultato il 16 giugno 2023.

Voci correlate

• Ada Lovelace
• Numeri di Bernoulli