Da sommatoria a formula

Durante una delle lezioni ci è stata proposta la seguente serie, descritta come sommatoria:

$f (n) = \sum_{k = 1}^{n} 4 k + 3$

Dal cilindro il prof ci ha estratto questa formula:

$f (n) = \sum_{k = 1}^{n} 4 k + 3 =$ 2n²+5n

Poi, con il principio di induzione, ha dimostrato che è vera. E ci ha anche detto che a volte è richiesto che lo studente risalga a questa funzione da solo.

Panico.
Panico da Settimana Enigmistica, ma comunque panico.

Come si risale da una sommatoria a una funzione? Questa è una domanda molto importante soprattutto quando si studiano algoritmi e strutture dati, perché una serie che considera il risultato precedente ha delle prestazioni decisamente più scadenti di una "formuletta" non ricorsiva.

Per risolvere l'enigma, ho pensato alla semplice sommatoria di tutti i numeri da 1 a n:

$\sum_{k = 1}^{n} k = \frac{k \cdot (k + 1)}{2}$

che crea la serie

P₁ = 1
P₂ = P₁ + 2 = 3
P₃ = P₂ + 3 = 6
P₄ = P₃ + 4 = 10
P₅ = P₄ + 5 = 15
P₆ = P₅ + 6 = 21
P₇ = P₆ + 7 = 28
P_... = P_... + ... = ...

Cosa succede se moltiplico per (ad esempio) 3 l'indice?

$\sum_{k = 1}^{n} 3 k = ???$

P₁ = 3
P₂ = P₁ + 6 = 9
P₃ = P₂ + 9 = 18
P₄ = P₃ + 12 = 30
P₅ = P₄ + 15 = 45
P₆ = P₅ + 18 = 63
P₇ = P₆ + 21 = 84
P_... = P_... + ... = ...

La soluzione non può essere molto distante da

$\frac{k \cdot (k + 1)}{2}$

Infatti, dopo qualche tentativo, ho trovato questa formula:

$\frac{3 k \cdot (k + 1)}{2}$

Apparentemente la formula sembra applicarsi ai numeri razionali, e non ai naturali, perché è evidente il 3/2.
Però è vero anche che tra n e n+1 uno dei due DEVE essere pari, e quello si semplifica con il 2 al denominatore.

Poi ho provato ad aggiungere una costante alla sommatoria, per cercare in che modo la costante cambia la formula.

$\sum_{k = 1}^{n} k + 4 = ???$

P₁ = 5
P₂ = P₁ + 2 + 4 = 11
P₃ = P₂ + 3 + 4 = 18
P₄ = P₃ + 4 + 4 = 26
P₅ = P₄ + 5 + 4 = 35
P₆ = P₅ + 6 + 4 = 45
P₇ = P₆ + 7 + 4 = 56
P_... = P_... + ... = ...

Siccome ogni volta che aggiungo la costante me la "porto dietro" per k volte, ho provato semplicemente ad aggiungere k 4 volte alla formula:

$\frac{k \cdot (k + 1)}{2} + 4 k$

(no, non ci sono arrivato subito, al primo tentativo, in maniera brillante e sicura)

A questo punto ho tutto quanto mi serve per affrontare la serie proposta dal prof.

$f (n) = \sum_{k = 1}^{n} 4 k + 3$

diventa

$\frac{4 k \cdot (k + 1)}{2} + 3 k$

Questo non assomiglia per niente alla 2n²+5n, ma proviamo a fare qualche passaggio in più.

$\frac{4 k \cdot (k + 1)}{2} + 3 k = \frac{{4 k}^{2}}{2} + \frac{4 k}{2} + 3 k = 2 k^{2} + 2k+3k=2k^{2}+5k$