Algoritmo di Ada Lovelace per i numeri di Bernoulli

L'algoritmo di Ada Lovelace (nata Ada Byron) permette di calcolare i numeri di Bernoulli, senza dover conteggiare tutti quelli ad essi precedenti. Questo algoritmo è considerato un risultato brillante, sia per la valenza computazionale che per la felice coniugazione di matematica e informatica. È 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 Ada Lovelace nell'implementare il suo algoritmo si servì della seguente formula:

${\displaystyle {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!}+...=\sum _{k=1}^{n}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}}$ 

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

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

Alcune fonti ^[1] affermano con solo un accenno di dimostrazione che questa formula deriva dalla funzione generatrice

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

Questa 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).

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

${\displaystyle 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:

${\displaystyle \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

${\displaystyle {\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}}))=}$ 

${\displaystyle ={\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 ${\displaystyle B_{1}B_{3}B_{5}...}$  che chiaramente corrispondono ai nostri ${\displaystyle B_{2}B_{4}B_{6}...}$  .

Note

1. ^ Adity Kar, Ada Lovelace, su people.maths.ox.ac.uk.

  Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica