[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Successioni ricorsive lineari

Coraggio, prima o poi bisogna studiarle!

Successione ricorsiva 1
Consideriamo la seguente successione definita ricorsivamente.

a0 = 5
an = 2an-1

con n >= 1

Quanto vale il settimo termine, ovvero a7?
E' possibile trovare una formula esplicita che permetta di calcolare il n-esimo termine in funzione di n?
In pratica si chiede se è possibile calcolare direttamente il termine n-esimo, senza compiere gli n passaggi di ricorsione.

Successione ricorsiva 2
Determinare il termine n-esimo della successione definita ricorsivamente nel modo seguente:

a0 = 1
a1 = 3
an = 5an-1 + 6an-2

con n>=2

Successione ricorsiva 3
Determinare il termine n-esimo della successione definita ricorsivamente nel modo seguente:

a0 = 1
a1 = 4

an+2 = an+1 + an
--------------
2

con n>=0

Successione ricorsiva 4
Risolvere la seguente successione

a0 = 3
an+1 = 2an + 2n

La successione di Fibonacci
La successione di Fibonacci è definita così:
f0 = 0
f1 = 1
fn = fn-1 + fn-2

Trovare una formula esplicita che permetta di calcolare fn in funzione di n.

Ultimo aggiornamento: marzo 2005

Risposte & riflessioni

Successione ricorsiva 1
a0 = 5
an = 2an-1

con n >= 1

Scriviamo alcuni valori in una tabella.

n 0 1 2 3 4 5 6 7
an 5 5*2 5*22 5*23 5*24 5*25 5*26 5*27

E' facile intuire che la formula cercata è:
an = 5*2n

Successione ricorsiva 2
a0 = 1
a1 = 3
an = 5an-1 + 6an-2

con n>=2

A questo punto non si può andare avanti per tentativi ed esempi, ci vuole un po' di teoria.

Un po' di teoria

Definizioni
La successione:

a0 = 1
a1 = 3
an = 5an-1 + 6an-2

è una successione ricorsiva lineare del secondo ordine, omogenea.

  • Ricorsiva, perché il termine ennesimo è definito in base ad alcuni termini che lo precedono.

  • Lineare, perché i termini sono tutti di 1° grado.

  • Del secondo ordine, perché an è definita in base ad an-1 e an-2, cioè in base ai due termini che lo precedono.

  • Omogenea, perché ci sono solo termini del tipo an e manca una funzione di n aggiuntiva.

Invece la successione:

a0 = 5
an = 2an-1

è una successione ricorsiva lineare del primo ordine, omogenea.

Infine la successione:

a0 = 3
an+1 = 2an + 2n

è una successione ricorsiva lineare del primo ordine, non omogenea.

Riprendiamo la nostra successione:

a0 = 1
a1 = 3
an = 5an-1 + 6an-2

Sperando che esista, come nell'esercizio precedente, una soluzione del tipo:
an = c*rn
scriviamo:
rn = 5rn-1 + 6rn-2 si chiama equazione caratteristica
Dividiamo per rn-2 e otteniamo:
r2 = 5r + 6
r2 - 5r - 6 = 0
Le radici caratteristiche sono 6 e -1.

Allora:
an = u*6n + v*(-1)n
I valori di u, v, si trovano utilizzando le condizioni iniziali:
a0 = 1
a1 = 3

1 = u*60 + v*(-1)0
3 = u*61 + v*(-1)1

u + v = 1
6u - v = 3

Da cui si ricava:
u = 4/7
v = 3/7

Infine, ecco la funzione cercata:
an = (4/7)*6n + (3/7)*(-1)n

Ancora teoria

Generalizziamo quanto visto sopra, con alcune aggiunte.

Successione:
an   =  ban–1  + can–2

Equazione caratteristica:
r2  - br  – c = 0 

Radici caratteristiche:
r1, r2

Teorema.
Se le radici caratteristiche sono distinte, r1, r2, allora la soluzione generale è:
an  =  x r1n + y r2n

Teorema.
Se le radici caratteristiche sono coincidenti, r1, r1, allora la soluzione generale è:
an  =  x r1n + y n r1n

Per trovare una soluzione particolare, date le condizioni iniziali, ao, a1, si risolve il seguente sistema:
ao =  x   +   y
a1 =  r1x  +  r2y
Naturalmente, se le radici non sono distinte, il sistema è impossibile.

Due casi particolari: successioni geometriche e successioni aritmetiche

Successioni del tipo:
a0 = h
an = kan-1
sono successioni geometriche di ragione k.
an = h*kn

Esempio:
a0 = 3
an = 1,2*an-1
an = 3*1,2n

Successioni del tipo:
a0 = h
an = an-1 + k
sono successioni aritmetiche di differenza k.
an = h + n*k

Esempio:
a0 = 3
an = an-1+ 2
an = 3 + 2n

That's all, folks

Successione ricorsiva 3
a0 = 1
a1 = 4

an+2 = an+1 + an
--------------
2

con n>=0

Lavorandoci un po' su, si ottiene:
an = 3 - 2(-1/2)n

Successione ricorsiva 4
a0 = 3
an+1 = 2an + 2n

Soluzione generale:
an  =  2n a0 + n2n

Soluzione particolare
an  =  3 (2n) + n2n

La successione di Fibonacci
f0 = 0
f1 = 1
fn = fn-1 + fn-2

Lavorandoci un po' su, si ottiene la classica formula di Binet:

Fib(n) = 1
Ö5		 [ ( 1+Ö5
2		 ) n

 		 - ( 1-Ö5
2		 ) n

 		 ]

Il numero phi = (1+Ö5)/2 che compare nella relazione precedente, è il famoso rapporto aureo.
Siccome: (1-Ö5)/2 = 1-phi, la formula di Binet può essere scritta così:

Fib(n) = 1
Ö5		 [ ( phi ) n - ( 1-phi ) n ]

N.B. Il simbolo Ö5 è la radice quadrata di 5

Sito Web realizzato da Gianfranco Bo