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}^{n-1}{{2n+1} \choose {k}}B_{k}=-{\frac {1}{2}}{\frac {2n-1}{2n+1}}~~~~~~(con~~B_{0}=1~~e~~B_{1}=-{\frac {1}{2}})}$ 

Note

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

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