Fissate le costanti , con , diremo che l’equazione ricorsiva: è una equazione ricorsiva lineareequazione ricorsiva lineare (omogenea) di ordine . Il polinomio con gli stessi coefficienti: si chiama polinomio caratteristicopolinomio caratteristico associato all’equazione lineare (7.4).
Ad esempio la successione di Fibonacci definita da (7.2) è una soluzione dell’equazione ricorsiva lineare del secondo ordine: il cui polinomio caratteristico è
Teorema 7.24 (indipendenza delle successioni esponenziali). Siano numeri complessi distinti. Allora le successioni definite da sono vettori indipendenti nello spazio vettoriale complesso di tutte le successioni a valori complessi.
Dimostrazione. Dobbiamo mostrare che se una combinazione lineare delle successioni è nulla allora tutti i coefficienti sono nulli. Lo dimostriamo per induzione sul numero . Se il risultato è banale. Supponiamo allora di sapere che sono indipendenti e dimostriamo che allora anche lo sono.
Supponiamo quindi di avere tali che Significa che per ogni si ha Se al posto di mettiamo si ha Se ora moltiplichiamo (7.5) per e sottraiamo l’equazione precedente si ottiene: Posto si ottiene dunque, per ogni Per ipotesi induttiva sappiamo che i coefficienti devono essere tutti nulli che significa, essendo che anche sono tutti nulli. Ma allora (7.5) diventa che per implica che anche . □
dimostrazione alternativa. Valutando l’equazione (7.5) per si ottiene
che è un sistema lineare la cui matrice associata è la matrice di VandermondeVandermonde che notoriamente (lo si può dimostrare per induzione) ha determinante e dunque è invertibile se e solo se i sono tra loro distinti.
Dunque è l’unica soluzione del sistema lineare. □
Teorema 7.25 (dimensione delle soluzioni). L’insieme di tutte le successioni soluzioni dell’equazione (7.4) di ordine è un sottospazio vettoriale di dimensione dello spazio di tutte le successioni.
Dimostrazione. Denotiamo con la successione . L’insieme delle soluzioni dell’equazione (7.4) è un sottospazio vettoriale di in quanto se e sono soluzioni anche è soluzione e se è soluzione anche è soluzione per ogni (si faccia la verifica).
Consideriamo allora l’operatore (chiamato jetjet) definito da E’ facile verificare che è un operatore lineare in quanto la valutazione di una funzione in un punto è una operazione lineare.
Vogliamo ora determinare Se significa che i primi termini della successione sono tutti nulli. Ma se sappiamo che vale (7.4) e dunque anche è nullo. Applicando (7.4) ricorsivamente otteniamo che per ogni e dunque . Dunque e per le note proprietà degli operatori lineari possiamo affermare che è iniettivo. Dunque .
Ma possiamo anche osservare che è suriettivo in quanto fissati i valori di l’equazione (7.4) ci permette di determinare, induttivamente, tutti i termini successivi. Dunque fissato è possibile trovare tale che .
Visto che è iniettivo e suriettivo concludiamo che . □
Teorema 7.26 (caratterizzazione delle soluzioni). Se il polinomio caratteristico dell’equazione (7.4) ha zeri distinti allora ogni soluzione dell’equazione si scrive nella forma dove sono costanti arbitrarie.
Dimostrazione. Sia lo spazio vettoriale di tutte le successioni. Possiamo definire l’operatore di shift Risulta quindi che dove è la composizione di con se stesso per volte. Possiamo quindi riscrivere l’equazione (7.4) nella forma ovvero dove con si intende l’operatore ottenuto applicando il polinomio caratteristico all’operatore .
Se sono le radici del polinomio si può decomporre il polinomio tramite il teorema 1.130 di Ruffini la stessa decomposizione può essere fatta per e quindi l’equazione (7.4) può essere scritta nella forma: dove è l’operatore identità . Visto che nella decomposizione (7.6) l’ordine in cui vengono moltiplicati i fattori non conta, anche nell’equazione (7.7) possiamo applicare gli operatori in qualunque ordine (gli operatori commutano). Dunque è immediato accorgersi che se risolve per un qualunque allora . Ma quest’ultima equazione è facile da risolvere in quanto ponendo si esplicita nella forma: che è soddisfatta se se si sceglie .
Dunque la successione definita da è un elemento di . Per abbiamo trovato soluzioni distinte . Queste soluzioni sono indipendenti grazie al teorema 7.24 e quindi essendo per il teorema 7.25 possiamo affermare che queste soluzioni formano una base di che è esattamente quanto volevamo dimostrare. □
Esempio 7.27 (formula esplicita per la successione di Fibonacci). La successione di Fibonacci definita da (7.2) soddisfa una equazione ricorsiva lineare del secondo ordine con polinomio associato . Risolvendo l’equazione si trovano le due radici distinte: La radice più grande, , corrisponde al rapporto aureorapporto aureo che usualmente viene chiamato . Visto che si trova . Dunque, per il teorema precedente, sappiamo che esistono due costanti e tali che Imponendo le condizioni , (imporre è equivalente a ) si ottiene da cui è possibile trovare e ottenere così la formula di Binet per il -esimo numero di Fibonacci: Formula di Binet Risulta piuttosto sorprendente osservare che i valori ottenuti con questa espressione siano tutti numeri interi.