Equazione di ricorrenza con le funzioni generatrici

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.
Questa sezione è un contenitore temporaneo per i topic speciali a pagamento (One-Shot).
#83596
avt
Christian1988
Cerchio

Ciao, vorrei capire come risolvere gli esercizi sulle funzioni generatrici e sulle equazioni di ricorrenza per le successioni.

Eccone uno: usando le funzioni generatrici, risolvere la seguente equazione di ricorrenza e precisare il comportamento asintotico della soluzione:

a_(n+2) = 1+a_n (n ≥ 0) ; a_(0) = a_(1) = 1 .

Ringraziano: quellochetipare
#83600
avt
Omega
Amministratore

Ciao Christian1988!

Esercizio molto carino: la funzione generatrice di una successione di ricorrenza permette di descrivere la successione ricorsiva mediante un'espressione esplicita del tipo a_n_n.

Inoltre ti ringrazio per aver postato un esercizio del genere, perché ad oggi (incredibile a dirsi) non avevamo nulla di simile nella scheda di esercizi risolti sulle successioni ricorsive! emt

Procediamo: consideriamo la successione

a_(n+2) = 1+a_n (n ≥ 0) ; a_(0) = a_(1) = 1

Vediamo per un istante quali sono i primi termini della successione

a_0: = 1 ; a_1: = 1 ; a_2 = a_0+1 = 1+1 = 2 ; a_3 = a_1+1 = 1+1 = 2 ; a_4 = a_2+1 = 2+1 = 3 ; a_5 = a_3+1 = 2+1 = 3 ; a_6 = a_4+1 = 3+1 = 4 ; ...

Ok, abbiamo capito che la successione ricorsiva ripete tutti i numeri naturali due volte: 1,1,2,2,3,3,4,4,....

Consideriamo la funzione generatrice

f(x) = Σ_(n = 0)^(+∞)a_nx^n

il nostro obiettivo consiste proprio nel determinare a_n_n. Prendiamo l'equazione che definisce la successione per ricorrenza

a_(n+2) = a_n+1

e passiamo a considerare

Σ_(n = 0)^(+∞)a_(n+2)x^n = Σ_(n = 0)^(+∞)a_(n)x^n+Σ_(n = 0)^(+∞)x^n

dove naturalmente Σ_(n = 0)^(+∞)x^n è la serie geometrica di ragione x, la cui somma vale (1)/(1−x) purché |x| < 1.

Ora vogliamo riscrivere la precedente uguaglianza in modo da ricavare un'espressione esplicita della funzione generatrice f(x).

Osserviamo che la sommatoria a sinistra è traslata. Lavoriamoci un po':

(Σ_(n = 0)^(+∞)a_(n+2)x^(n+2))/(x^2) = Σ_(n = 0)^(+∞)a_(n)x^n+Σ_(n = 0)^(+∞)x^n

Per ricondurla ad una serie del tipo Σ_(m = 0)^(+∞)a_(m)x^(m) ci basta sommare e sottrarre (a_0+a_1x), vale a dire i termini corrispondenti agli indici m = 0,m = 1

(Σ_(n = 0)^(+∞)a_(n)x^(n)−a_0−a_1x)/(x^2) = Σ_(n = 0)^(+∞)a_(n)x^n+Σ_(n = 0)^(+∞)x^n

Ci siamo, per definizione della funzione generatrice passiamo a riscrivere l'uguaglianza nella seguente forma

(f(x)−a_0−a_1x)/(x^2) = f(x)+(1)/(1−x)

dove ho anche sostituito la somma della serie geometrica.

Un paio di conticini banali ci permettono di arrivare all'espressione per f(x). E già che ci siamo, ricordiamoci che a_0 = 1 = a_1

(f(x)−a_0−a_1x−f(x)x^2)/(x^2) = (1)/(1−x) ; (f(x)−x^2f(x))/(x^2) = (1+x)/(x^2)+(1)/(1−x)

effettuiamo un raccoglimento totale sul primo rapporto e facciamo qualche conto al secondo membro

f(x)(1−x^2)/(x^2) = (1)/(x^2(1−x))

da cui

f(x) = (1)/((1+x)(1−x)^2)

Ora si tratta di applicare il metodo dei fratti semplici (il link rimanda alla lezione sugli integrali in cui lo spieghiamo) per riscrivere la funzione razionale come somma.

Poniamo

(1)/((1+x)(1−x)^2) = (a)/(1+x)+(b)/(1−x)+(c)/((1−x)^2)

e attenzione al terzo addendo, in genere viene dimenticato in sede d'esame. emt

Facendo i conti sul secondo membro, si arriva a riscrivere la funzione razionale nella forma

(1)/((1+x)(1−x)^2) = ((a+b+c)+(c−2a)x+(a−b)x^2)/((1+x)(1−x)^2)

e, grazie al principio di identità dei polinomi, si confrontano i numeratori e si giunge al sistema lineare

a+b+c = 1 ; c−2a = 0 ; a−b = 0

da cui le soluzioni

a = (1)/(4), b = (1)/(4), c = (1)/(2)

da cui la scomposizione cercata

f(x) = (1)/((1+x)(1−x)^2) = (1)/(4)(1)/(1+x)+(1)/(4)(1)/(1−x)+(1)/(2)(1)/((1−x)^2)

Facciamo riferimento alla somma della serie geometrica per riscrivere la funzione generatrice della successione ricorsiva come somma di opportune serie:

f(x) = (1)/(4)Σ_(n = 0)^(+∞)(−x)^n+(1)/(4)Σ_(n = 0)^(+∞)x^n+(1)/(2)(1)/((1−x)^2)

Per riscrivere l'ultimo rapporto come serie serve un piccolo trucchetto, che di norma viene proposto nelle lezioni frontali dell'università

(d)/(dx)x^(n+1) → (n+1)x^n ; (d)/(dx)(1)/(1−x) = (1)/((1−x)^2)

in termini rigorosi, si ricava la somma

(1)/((1−x)^2) = Σ_(n = 0)^(+∞)(n+1)x^n

mediante il teorema di derivazione per le serie di potenze.

Ci siamo

f(x) = (1)/(4)Σ_(n = 0)^(+∞)(−x)^n+(1)/(4)Σ_(n = 0)^(+∞)x^n+(1)/(2)Σ_(n = 0)^(+∞)(n+1)x^n

riscriviamo il secondo membro come un'unica serie

f(x) = Σ_(n = 0)^(+∞)((−x)^n)/(4)+(x^n)/(4)+(n+1)/(2)x^n

ossia

f(x) = Σ_(n = 0)^(+∞)[((−1)^n)/(4)+(1)/(4)+(n+1)/(2)]x^n

ossia

f(x) = Σ_(n = 0)^(+∞)[((−1)^n+3+2n)/(4)]x^n

Dalla definizione della funzione generatrice f(x)

Σ_(n = 0)^(+∞)a_nx^n = Σ_(n = 0)^(+∞)[((−1)^n+3+2n)/(4)]x^n

ricaviamo per confronto il termine generale della tanto agognata successione a_n_n

a_n = ((−1)^n+3+2n)/(4)

Per il comportamento asintotico è sufficiente limitarsi a considerare l'infinito di ordine principale al tendere di n → +∞

a_n ~ _(n → +∞)(n)/(2)

Ringraziano: Ifrit, CarFaby, Christian1988
#83827
avt
Christian1988
Cerchio

Grazie mille Omega, non appena il lavoro me lo permetterà leggerò bene la tua risposta!

Grazie mille!

Ringraziano: Omega
  • Pagina:
  • 1