Algoritmo di Ada Lovelace per i numeri di Bernoulli
# 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.

## 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:

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}...$ .

