Funzioni Generatrici Ordinarie ed Equazioni di Ricorrenza

1) Funzioni generatrici ordinarie di una variabile

Le funzioni generatrici sono uno strumento importante per risolvere problemi combinatoriali di vario tipo. Un problema tipico è il calcolo del numero di oggetti in funzione della dimensione \(n\), che possiamo indicare con \(a_{n}\). Per ogni valore di \(n\) intero non negativo abbiamo quindi una successione di valori \(\{a_{0},a_{1}, \cdots a_{n}, \cdots \}\). Chiamiamo funzione generatrice della successione \(a_{n}\) la seguente espansione di potenze:

\[ G(x) = \sum_{n=0}^{\infty}a_{n}x^{n} = a_{0}+a_{1}x + a_{2}x^{2} + \cdots \]

Se c’è un numero infinito di termini si tratta di una serie di potenze; nel caso finito è un polinomio.
Due funzioni generatrici \( F(x) = \sum_{n=0}^{\infty}a_{n}x^{n}\) e \( G(x) = \sum_{n=0}^{\infty}b_{n}x^{n}\) sono equivalenti se \(a_{n}=b_{n}\) per ogni valore di \(n\).
Nello studio delle funzioni generatrici in genere si trascurano gli aspetti relativi alla convergenza delle serie. In questo caso la funzione generatrice viene anche chiamata serie formale. In questo senso la funzione generatrice è semplicemente un modo di rappresentare le successioni di numeri, e le potenze di \(x\) indicano il posto associato ai vari termini della successione. Le serie formali sono uno strumento utile per rappresentare le successioni di numeri anche se hanno molte limitazioni. Se si vogliono utilizzare le forme chiuse delle funzioni generatrici (ad esempio la funzione \(\frac{1}{1-x}\) della serie geometrica), allora è indispensabile analizzare anche l’intervallo di convergenza della serie. Vediamo con alcuni esempi come le funzioni generatrici possono essere di aiuto nei problemi di conteggio.

Esempio 1.1 – Il teorema binomiale di Newton
Supponiamo di voler calcolare il numero dei sottoinsiemi di \(k\) oggetti, presi da un insieme di \(n\) elementi. È noto che il valore è dato dal coefficiente binomiale \(\displaystyle \binom{n}{k}\). Quindi la funzione generatrice di questi coefficienti è il polinomio di Newton:

\[ G(x) = \sum_{k=0}^{n} \binom{n}{k}x^{k} = (1+x)^{n} \]

Esempio 1.2
Data la successione \(\{1,1,1,1, \cdots \}\), la funzione generatrice è la serie geometrica:

\[ \begin{split} G(x) &= 1 + x + x^{2}+ x^{3} + \cdots = \\ &= \sum_{n=0}^{\infty}x^{n}= \frac {1}{1-x} \text{ se \(|x| < 1\)} \end{split} \]

Esercizio 1.1
Trovare la funzione generatrice della successione \(\{1,2,4,8, \cdots \}\).

Esercizio 1.2
Trovare la successione generata dalla seguente funzione:

\[ f(x) = \frac{1- \sqrt{1-4x}}{2} \]

Suggerimento
Utilizzare lo sviluppo in serie di McLaurin della funzione.

I numeri della successione generata dalla funzione sono i numeri di Catalan \(C_{n}= \frac{1}{n}\binom{2n-2}{n-1}\). Per maggiori dettagli sui numeri di Catalan vedere il seguente link.

Esercizio 1.3
Trovare la funzione generatrice della successione dei numeri di Fibonacci, che sono così definiti:

\[ F_{n}=F_{n-1} + F_{n-2} \quad \text{se \(n > 1\)} \]

con i valori iniziali \(F_{0}=0 \quad F_{1}=1\).

Suggerimento
Combinare le serie \(G(x)\), \(xG(x)\) e \(x^{2}G(X)\) fra loro. Si trova la seguente espressione per la funzione generatrice dei numeri di Fibonacci:

\[ G(x)= \frac{x}{1-x-x^{2}} \]

---

2) Operazioni con le funzioni generatrici

2.1) Somma e prodotto di funzioni generatrici

Date due funzioni generatrici \( F(x) = \sum_{n=0}^{\infty}a_{n}x^{n}\) e \( G(x) = \sum_{n=0}^{\infty}b_{n}x^{n}\), vengono definite le seguenti operazioni di somma e prodotto:

\[ \begin{split} F(x) + G(x) &= \sum_{n=0}^{\infty}(a_{n}+b_{n})x^{n} \\ F(x) \cdot G(x) &= \sum_{n=0}^{\infty}c_{n}x^{n} \text{ dove } c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \end{split} \]

Il prodotto di due serie viene anche chiamato prodotto di Cauchy e l’espressione \(c_{n}\) ha un ruolo importante nel conteggio di oggetti indistinguibili.
Due funzioni generatrici \(F(x),G(x)\) sono reciproche se risulta \(F(x)G(x)=1\). L’inverso di \(F(x)\) esiste se e solo se \(a_{0} \neq 0\).

Esempio 2.1
La funzione generatrice inversa della \(F(x)=\sum_{n=0}^{\infty}x^{n}\) è la funzione \(F(x)=1-x\) in quanto

\[ (1-x)(1+x+ x^{2}+ \cdots)=1 \]

2.2) Cambiamento di scala

Moltiplicare una funzione generatrice per una costante equivale a scalare ogni termine della successione per lo stesso valore.
Ad esempio la funzione generatrice \(\frac{1}{1-x^{3}}\) genera la successione \((1,0,0,1,0,0,1, \cdots)\). Se moltiplichiamo per \(5\), la nuova funzione \(\frac{5}{1-x^{3}}\) genera la successione \((5,0,0,5,0,0, \cdots)\).

2.3) Shift a destra della successione

Sia data la successione \(\{a_{0},a_{1},a_{2}, \cdots \}\) e la relativa funzione generatrice \(G(x) = \sum_{n=0}^{\infty}a_{n}x^{n}\). Se cambiamo la successione aggiungendo \(k\) zeri a sinistra \(\{0,0, \cdots, 0,a_{0},a_{1},a_{2}, \cdots \}\), la nuova funzione generatrice è \(x^{k}G(x)= a_{0}x^{k}+ a_{1}x^{k+1}+ \cdots \).

Esempio 2.2
La funzione generatrice della successione \(\{0,0,0,1,1,1, \cdots \}\) è la funzione \(G(x)= \frac{x^{3}}{1-x}\).

2.4) Operazione di derivazione

Data la successione \(\{a_{0},a_{1},a_{2}, \cdots \}\) e la relativa funzione generatrice \(G(x) = \sum_{n=0}^{\infty}a_{n}x^{n}\). La derivata della funzione \(G(x)\) è la funzione generatrice della successione \(\{a_{1},2a_{2},3a_{3}, \cdots \}\).

Esempio 2.3
La derivata della funzione \(\frac{1}{1-x}\) è la funzione \(\frac{1}{(1-x)^{2}}\), che è generatrice della successione dei numeri naturali \(\{1,2,3,4, \cdots\}\).

---

3) Calcolo dei coefficienti delle funzioni generatrici

Un problema fondamentale è quello di determinare i valori di una successione per ogni \(n\), a partire dalla funzione generatrice espressa in forma chiusa come funzione di \(x\).

Esercizio 3.1
Trovare il coefficiente \(a_{n}\) delle seguenti funzioni generatrici, espresse in forma chiusa:

\[ \begin{split} G(x) &= (1+x)^{3000} \\ G(x) &= \frac{1}{1-5x} \end{split} \]

Esercizio 3.2
Trovare i coefficienti \(a_{n}\) della seguente funzione generatrice, espressa in forma chiusa:

\[ G(x) = \frac{1}{(1-x)^{r}} \text{ , r intero} \ge 0 \]

Soluzione
Moltiplicando gli \(r\) sviluppi della funzione \(\frac{1}{1-x}\), si vede che il coefficiente davanti a \(x^{n}\) è il numero dei modi in cui è possibile scrivere \(n= p_{1} + p_{2} + \cdots + p_{r} \text { dove } p_{i}\ge 0\). Questo non è altro che il problema di trovare il numero di combinazioni con ripetizioni di \(r\) oggetti presi a gruppi di \(n\). Come è noto tale valore è \(a_{n}= \binom{n+r-1}{r-1}=\binom{n+r-1}{n}\).

Definizione 3.1
Data una successione di numeri \(a_{0}, a_{1}, \dots \), definiamo il prodotto parziale di ordine \(n\): \(\prod_{i=0}^{n} a_{i}=a_{0}a_{1} \cdots a_{n}\). Definiamo quindi il prodotto infinito come limite del prodotto parziale (in analogia alla definizione di somma di una serie infinita):

\[ \prod_{i=0}^{\infty}a_{i}= \lim_{n \to\infty}\prod_{i=0}^{n}a_{i} \]

Lo studio dei prodotti infiniti è molto importante in Analisi Matematica, come quello delle serie. Per un approfondimento vedere ad esempio il bellissimo libretto di Knopp^[1].

Sia \(p(n)\) la funzione aritmetica che conta il numero di partizioni del numero intero positivo \(n\), in parti non necessariamente distinte. Non si tiene conto dell’ordine. Ad esempio se \(n=4\), \(p(4)=5\). Le partizioni sono le seguenti:

\[ 4=1+1+1+1=1+1+2=1+3=2+2 \]

Esercizio 3.3
Determinare la funzione generatrice della funzione \(p(n)\) che rappresenta il numero di partizioni di un intero positivo \(n\) in parti non necessariamente distinte.

Soluzione
Analizziamo la seguente identità:

\[ \prod_{k=1}^{\infty} \frac{1} {(1-x^{k})}=\prod_{k=1}^{\infty}(1+x^{k}+x^{2k}+x^{3k}+ \cdots) \]

Osserviamo in primo luogo che nonostante ci sia un prodotto infinito, per il calcolo del coefficiente \(a(n)\) della potenza \(x^{n}\) bisogna analizzare soltanto un numero finito di termini, precisamente quelli che hanno una potenza minore od uguale a \(n\).
Nel nostro caso il coefficiente della potenza \(x^{n}\) è proprio la funzione \(p(n)\) in quanto il termine che scegliamo in ogni fattore \((1+x^{k}+x^{2k}+x^{3k}+ \cdots)\) determina quante volte il numero \(k\) appare nella partizione. Quindi abbiamo:

\[ \prod_{n=1}^{\infty} \frac{1} {(1-x^{n})}=\sum_{n=0}^{\infty}p(n)x^{n} \]

Esercizio 3.4
Determinare la funzione generatrice della funzione \(p^{d}(n)\) che rappresenta il numero di partizioni di un intero positivo \(n\) in parti distinte.

Soluzione: [\(\prod_{n=1}^{\infty} (1+x^{n})\)]

Esercizio 3.5
Dimostrare la seguente identità:

\[ \prod_{n=1}^{\infty}(1+x^{n}) = \prod_{n=1}^{\infty}\frac{1}{(1-x^{2n-1})} \]

Suggerimento
Moltiplicando due fattori per volta nei seguenti prodotti infiniti, otteniamo:

\[ \begin{split} (1-x)(1+x)(1+x^{2})(1+x^{4})(1+x^{8}) \cdots &= 1 \\ (1-x^{3})(1+x^{3})(1+x^{6})(1+x^{12})(1+x^{24})\cdots &= 1 \\ \end{split} \]

Proseguendo in questo modo otteniamo la seguente relazione finale:

\[ \prod_{n=1}^{\infty}(1+x^{n}) \prod_{n=1}^{\infty}(1-x^{2n-1}) = 1 \]

Esercizio 3.6
Dimostrare la seguente relazione:

\[ \sum_{k=0}^{n} \binom{n}{k}^{2} = \binom{2n}{n} \]

Suggerimento
Notare che \((1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^{k}\). Inoltre:

\[ \\ (1+x)^{2n} = ((1+x)^{n})^{2} = \left(\sum_{k=0}^{n}\binom{n}{k}x^{k}\right )^{2} \]

Quindi concludere ricordando l’uguaglianza \(\binom{n}{k}=\binom{n}{n-k}\).

---

4) Funzioni generatrici polinomiali

Una classe di funzioni generatrici molto importante è costituita dai polinomi ottenuti moltiplicando fattori polinomiali con coefficienti uguali ad \(1\). Ad esempio il polinomio

\[ p(x) = (1 + x + x^{2})^{6} \]

Il coefficiente di \(x^{k}\) corrisponde al numero delle soluzioni intere dell’equazione \(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}= k\), con \(0 \le a_{i} \le 2\). La soluzione di questa equazione è equivalente al problema di scegliere \(k\) oggetti fra una collezione di \(6\) tipi, con due oggetti per ogni tipo. Oppure è equivalente al problema di distribuire \(k\) oggetti identici in \(6\) scatole distinte, con al massimo due oggetti per ogni scatola.
Viceversa dato un problema combinatorio di scelta con ripetizione di oggetti identici possiamo determinare la funzione generatrice corrispondente.

Esempio 4.1
Date 3 tipi di palline di diverso colore: rosso, nero, verde. Calcolare, tramite la funzione generatrice, il numero di modi possibili per scegliere con ripetizione 6 oggetti, con al massimo 4 oggetti di ogni tipo.

Soluzione
In termini di equazione diofantea, cioè a soluzioni intere, si tratta di risolvere l’equazione \( a_{1}+ a_{2} +a_{3}=6, \quad 0 \le a_{i} \le 4\). Si trova facilmente che la soluzione è il coefficiente di \(x^{6}\) della funzione generatrice \(G(x)= (1 + x + x^{2}+ x^{3}+x^{4})^{3}\) .

---

5) Equazioni di ricorrenza

Definizione 5.1
Un’equazione lineare di ricorrenza di grado \(k\) a coefficienti costanti è una relazione del tipo

\[ y_{n+k} + c_{1}y_{n+k-1}+ c_{2}y_{n+k-2}+ \cdots +c_{k}y_{n} = f(n) \]

dove i coefficienti \(c_{i}\) sono costanti. Si dice omogenea se \(f(n)=0\), altrimenti si dice non omogenea.

Esempio 5.1
La relazione \(y_{n}= n \cdot y_{n-1}, \quad y_{1}=1\) definisce la funzione fattoriale di \(n\).

Molti problemi di natura combinatoria si riducono a trovare la soluzione di una equazione di ricorrenza, con delle opportune condizioni iniziali. Sostanzialmente un’equazione di ricorrenza scompone un problema di ordine \(n\) in uno o più problemi simili di ordine inferiore. Molti algoritmi ricorsivi di divide et impera (divide and conquer) come il merge-sort hanno una complessità temporale che può essere modellizzata con relazioni di ricorrenza. Per uno studio approfondito degli algoritmi ricorsivi vedere ^[2] oppure ^[3].
Un’equazione di ricorrenza viene anche chiamata equazione alle differenze finite. C’è una stretta analogia con le equazioni differenziali ordinarie lineari. Per risolvere una equazione di ricorrenza non omogenea prima si trova la soluzione generale dell’equazione omogenea, quindi si aggiunge una soluzione particolare dell’equazione non omogenea.

5.1) Soluzione dell’equazione omogenea

Per risolvere l’equazione omogenea bisogna prima risolvere l’equazione caratteristica:

Definizione 5.2
L’equazione caratteristica della equazione di ricorrenza di grado \(k\) sopra definita è la seguente equazione algebrica:

\[ r^{k} + c_{1}r^{k-1} + \cdots + c_{k} = 0 \]

Nel caso delle equazioni differenziali lineari ordinarie come base per le radici si prendono le funzioni esponenziali \(e^{\lambda x}\). Nelle equazioni di ricorrenza si utilizzano le funzioni \(y_{n}=r^{n}\). Affinché siano soluzioni dell’equazione di ricorrenza, deve essere soddisfatta l’equazione caratteristica. Le soluzioni algebriche di questa equazione si chiamano radici caratteristiche. Bisogna distinguere 3 casi:

• radici reali e distinte
• alcune radici sono uguali
• alcune radici sono numeri complessi

Nel primo caso la soluzione generale dell’equazione omogenea è la seguente :

\[ y_{n} = a_{1} r_{1}^{n}+ a_{2} r_{2}^{n}+ \cdots a_{k} r_{k}^{n} \]

dove \(a_{1},a_{2}, \cdots a_{k}\) sono costanti arbitrarie.
Nel secondo caso, ad esempio se una radice è doppia \(r_{1}=r_{2}\), abbiamo la soluzione \((a_{1} +a_{2}n) r_{1}^{n}\). E formule simili se la molteplicità della radice è maggiore di \(2\).
Nel terzo caso per ogni soluzione complessa \(\alpha + i \beta\) esiste anche la complessa coniugata \(\alpha – i \beta\). Quindi possiamo scrivere la soluzione, per ogni radice complessa, in questo modo: \( A(\alpha + i \beta)^{n} + B(\alpha – i \beta)^{n}\).
Per uno studio completo sui metodi di soluzione delle equazioni alle differenze finite vedere ^[4].

Esercizio 5.1
Trovare la soluzione generale dell’equazione di ricorrenza:

\[ y_{n}-6y_{n-1}+9y_{n-2}=0 \]

Esercizio 5.2
Trovare la soluzione generale dell’equazione di ricorrenza:

\[ y_{n} + 3y_{n-1} + 3y_{n-2} + y_{n-3}=0 \]

Risposta: [\((A+Bn+ Cn^{2}) (-1)^{n}\)]

Esercizio 5.3
Trovare la soluzione dell’equazione di ricorrenza:

\[ \begin{split} y_{n} = 4y_{n-1} – 4y_{n-2} \\ y_{0}=2,y_{1}=5 \end{split} \]

Esercizio 5.4
Trovare la soluzione della seguente equazione di ricorrenza: \(y_{n}=3y_{n-1}\) con \(n >0\) e \(y_{0}=2\).

Risposta: [\( y_{n}=2 \cdot 3^{n}\)]

5.2) Soluzione dell’equazione non omogenea

Per risolvere l’equazione non omogenea basta trovare una soluzione particolare dell’equazione complessiva e sommarla alla soluzione generale dell’equazione omogenea. Le soluzioni particolari possono essere trovate in genere tramite metodi che variano a seconda del formato del termine non omogeneo \(f(n)\).

Esercizio 5.5
Risolvere l’equazione \(y_{n+2}-4y_{n+1}+4y_{n}=n\) .

Soluzione
L’equazione caratteristica \(r^{2}-4r+4=0\) ha una soluzione doppia \(r=2\). Quindi la soluzione generale dell’equazione omogenea è \(y_{n}=a 2^{n} + bn 2^{n}\), dove \(a,b\) sono due costanti arbitrarie da determinare mediante due condizioni iniziali.
Per trovare una soluzione particolare dell’equazione non omogenea bisogna guardare la forma del termine a destra dell’equazione. In questo caso si prova con un polinomio di grado uguale al massimo grado del termine a destra. Quindi proviamo con \(y_{n}=An + B\). Sostituendo questa espressione nell’equazione e uguagliando i coefficienti delle varie potenze di \(n\) otteniamo i valori \(A=1; B=2\). Quindi la soluzione generale dell’intera equazione non omogenea è la seguente:

\[ y_{n} = a2^{n} + bn2^{n} + n + 2 \]

Esercizio 5.6
Risolvere l’equazione \(y_{n+2}-4y_{n+1}+4y_{n}=n^{2}\)

In questo caso trovare la soluzione particolare dell’equazione non omogenea partendo dal polinomio \(y_{n}=An^{2}+Bn+C\).

Soluzione: [\(y_{n}=a2^{n} + bn2^{n} + n^{2} +4n + 8\)]

Esercizio 5.7 – Equazione di Perrin
Risolvere l’equazione \(y_{n}= y_{n-2}+y_{n-3}\) per \(n \ge 3\), con le condizioni iniziali \(a_{0}=3,a_{1}=0,a_{2}=2\).

Soluzione
Risolviamo mediante il metodo della funzione generatrice. Poniamo \( G(x) = \sum_{n=0}^{\infty}a_{n}x^{n}\). Calcoliamo in primo luogo le espressioni \(xG(x),x^{2}G(x),x^{3}G(x)\). Quindi mettendo insieme con un po’ di calcoli otteniamo la seguente espressione per la funzione generatrice:

\[ G(x) = \frac{x^{2}-3}{x^{3}+x^{2}-1} \]

L’equazione algebrica al denominatore ha tre radici, una reale \(r_{1}\) e due complesse coniugate \(r_{2},r_{3}\). L’inverso della radice reale viene chiamata anche numero plastico il cui valore approssimato è 1.32471 (vedi link).
Utilizziamo ora il metodo di scomposizione in frazioni parziali:

\[ G(x) = \frac{x^{2}-3}{x^{3}+x^{2}-1} = \frac{A}{x-r_{1}}+\frac{B}{x-r_{2}}+\frac{C}{x-r_{3}} \]

Svolgendo i calcoli troviamo i seguenti valori per le tre costanti: \(A=-r_{1},B=-r_{2},C=-r_{3}\). Quindi mettendo insieme lo sviluppo in serie delle tre funzioni otteniamo la seguente formula per il coefficiente \(a(n)\) della funzione generatrice:

\[ a(n)= \left(\frac{1}{r_{1}}\right)^{n}+ \left(\frac{1}{r_{2}}\right)^{n}+ \left(\frac {1}{r_{3}}\right)^{n} \]

---

6) I numeri di Fibonacci e di Lucas

6.1) I numeri di Fibonacci

I numeri di Fibonacci (1170-1235) sono interi non negativi definiti dalla seguente equazione di ricorrenza:

\[ \begin{split} F_{0} & = 0 \\ F_{1} & = 1 \\ F_{n} & = F_{n-1} + F_{n-2} \\ \end{split} \]

I primi numeri di Fibonacci sono \(\{0,1,1,2,3,5,8,13, \cdots \}\).

Esercizio 6.1
Dimostrare le seguenti relazioni:

\[ \begin{split} F_{1} + F_{3} + \cdots + F_{2n-1} &= F_{2n} \\ F_{2} + F_{4} + \cdots + F_{2n} &= F_{2n+1}-1 \\ \end{split} \]

Primo metodo di soluzione dell’equazione di ricorrenza

Risolviamo l’equazione alle ricorrenze soddisfatta dai numeri di Fibonacci con il metodo della funzione caratteristica. Poniamo \(F_{k}= r^{k}\). In questo caso l’equazione caratteristica e le sue soluzioni sono le seguenti:

\[ \begin{split} r^{2} – r – 1 &= 0 \\ r_{1} &= \frac{1 + \sqrt{5}}{2} \\ r_{2} &= \frac{1 – \sqrt{5}}{2} \\ \end{split} \]

La soluzione generale dell’equazione omogenea è quindi:

\[ F_{n} = A\left(\frac{1 + \sqrt{5}}{2}\right)^{n} + B \left(\frac{1 – \sqrt{5}}{2}\right)^{n} \]

Notiamo che la soluzione generale contiene due costanti arbitrarie. Tenendo conto delle condizioni iniziali \(F_{0}=0, F_{1}=1\), abbiamo infine la soluzione che da la formula per i numeri di Fibonacci:

\[ F_{n} = \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^{n} – \frac{1}{\sqrt{5}}\left(\frac{1 – \sqrt{5}}{2}\right)^{n} \]

Secondo metodo di soluzione dell’equazione di ricorrenza

Risolviamo l’equazione alle ricorrenze soddisfatta dai numeri di Fibonacci con il metodo della funzione generatrice, che è stata trovata il precedenza:

\[ \begin{split} F(x) &= \frac{x}{1-x-x^{2}} \end{split} \]

Teoricamente si potrebbe sviluppare questa funzione con lo sviluppo di Taylor nel punto \(x=0\) e trovare i coefficienti delle potenze di \(x\), che sono proprio i numeri di Fibonacci. Tuttavia sarebbe un calcolo troppo complicato; in questo caso essendo la funzione un rapporto fra due polinomi (funzione razionale) è meglio effettuare la decomposizione mediante il metodo delle frazioni parziali. Osserviamo in primo luogo che \(x^{2}-x-1=(1- r_{1}x)(1-r_{2}x)\), dove \(r_{1},r_{2}\) sono le due radici trovate in precedenza. Quindi si può scrivere la seguente decomposizione:

\[ \frac{x}{1-x-x^{2}} = \frac{A}{1 – r_{1}x} + \frac{B}{ 1 – r_{2} x} \]

Facendo il minimo comune multiplo delle due frazioni a destra, e uguagliando con l’espressione a sinistra, troviamo i seguenti valori per le costanti: \(A= \frac{1}{\sqrt{5}}, B= -\frac{1}{\sqrt{5}}\). Ricordando ora lo sviluppo in serie della funzione geometrica:

\[ \frac{1}{1-x} = 1 + x + x^{2} + x^{3} + \cdots \]

e mettendo insieme i risultati otteniamo nuovamente l’espressione generale per i coefficienti \(F_{n}\) già trovata in precedenza.

6.2) Il rapporto aureo

Due quantità \(a,b\) sono dette in rapporto aureo se risulta la seguente proporzione:

\[ (a+b):a= a:b \]

Se indichiamo \(x = \frac{a}{b}\) abbiamo l’equazione \(x^{2}-x-1=0\), le cui radici sono come abbiamo visto in precedenza \(r_{1},r_{2}\). Si usa il simbolo \(\Phi\) per indicare il valore \(\Phi = \frac{1+\sqrt{5}}{2}= 1,1618033\cdots \), che è un numero irrazionale.
In geometria si dice che un segmento è diviso in due parti secondo la sezione aurea se il loro rapporto ha il valore di \(\Phi\).

Esercizio 6.2
Dimostrare la seguente formula:

\[ \lim_{n \to \infty} \frac{F_{n+1}}{F_{n}}= \Phi \]

Suggerimento
Scrivere \(\frac{F_{n+1}}{F_{n}} = \frac{F_{n}+F_{n-1}}{F_{n}}\) e quindi passare al limite.

6.3) I numeri di Lucas

I numeri di Lucas (1842-1891) sono definiti in modo simile ai numeri di Fibonacci:

\[ L_{n}= L_{n-1} + L_{n-2} \quad (n \ge 2) \]

ma con condizioni iniziali diverse:

\[ L_{0}=2, L_{1}=1 \]

I primi numeri di Lucas sono \(\{2,1,3,4,7,11,18, \cdots \}\). L’equazione di ricorrenza è la stessa dei numeri di Fibonacci, quindi la soluzione generale è la stessa. Tuttavia la soluzione particolare, ottenuta imponendo le due condizioni iniziali, è naturalmente diversa:

\[ L_{n} = \left(\frac{1 + \sqrt{5}}{2}\right)^{n} + \left(\frac{1 – \sqrt{5}}{2}\right)^{n} \]

Esercizio 6.3
Dimostrare la seguente relazione: \( F_{2n}=L_{n}F_{n}\)

---

Conclusione

Come abbiamo visto in questo articolo le funzioni generatrici ordinarie sono uno strumento utile per risolvere molti problemi combinatori con ripetizioni. In un prossimo articolo descriveremo le funzioni generatrici esponenziali, che sono utili per risolvere problemi di distribuzione di oggetti distinti.

---

Bibliografia

^[1]K. Knopp – Theory and Application of Infinite Series (Dover)

^[2]T. Cormen – Introduction to Algorithms (The Mid Press)

^[3]J. Edmonds – How to Think about Algorithms (Cambridge U.P.)

^[4]M. Spiegel – Finite Differences and Difference Equations (McGraw-Hill)