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)

Se hai acquistato uno o più Topic speciali, puoi pubblicarli qui cliccando su "Apri un Topic".

Il registro completo dei Topic risolti e in corso è disponibile sul proprio profilo.

Equazione di ricorrenza con le funzioni generatrici #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:

\left\{\begin{matrix}a_{n+2} = 1 + a_n & (n \geq 0 )\\ a_{0}= a_{1} = 1 & \end{matrix}\right.
Ringraziano: quellochetipare
 
 

Equazione di ricorrenza con le funzioni generatrici #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

\begin{cases}a_{n+2} = 1 + a_n & (n \geq 0 )\\ a_{0}= a_{1} = 1 & \end{cases}

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)=\sum_{n=0}^{+\infty}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

\sum_{n=0}^{+\infty}a_{n+2}x^n=\sum_{n=0}^{+\infty}a_{n}x^n+\sum_{n=0}^{+\infty}x^n

dove naturalmente \sum_{n=0}^{+\infty}x^n è la serie geometrica di ragione x, la cui somma vale \frac{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':

\frac{\sum_{n=0}^{+\infty}a_{n+2}x^{n+2}}{x^2}=\sum_{n=0}^{+\infty}a_{n}x^n+\sum_{n=0}^{+\infty}x^n

Per ricondurla ad una serie del tipo \sum_{m=0}^{+\infty}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

\frac{\sum_{n=0}^{+\infty}a_{n}x^{n}-a_0-a_1x}{x^2}=\sum_{n=0}^{+\infty}a_{n}x^n+\sum_{n=0}^{+\infty}x^n

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

\frac{f(x)-a_0-a_1x}{x^2}=f(x)+\frac{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

\\ \frac{f(x)-a_0-a_1x-f(x)x^2}{x^2}=\frac{1}{1-x}\\ \\ \\ \frac{f(x)-x^2f(x)}{x^2}=\frac{1+x}{x^2}+\frac{1}{1-x}

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

f(x)\frac{1-x^2}{x^2}=\frac{1}{x^2(1-x)}

da cui

f(x)=\frac{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

\frac{1}{(1+x)(1-x)^2}=\frac{a}{1+x}+\frac{b}{1-x}+\frac{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

\frac{1}{(1+x)(1-x)^2}=\frac{(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

\begin{cases}a+b+c=1\\ c-2a=0\\ a-b=0\end{cases}

da cui le soluzioni

a=\frac{1}{4},\ b=\frac{1}{4},\ c=\frac{1}{2}

da cui la scomposizione cercata

f(x)=\frac{1}{(1+x)(1-x)^2}=\frac{1}{4}\frac{1}{1+x}+\frac{1}{4}\frac{1}{1-x}+\frac{1}{2}\frac{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)=\frac{1}{4}\sum_{n=0}^{+\infty}(-x)^n+\frac{1}{4}\sum_{n=0}^{+\infty}x^n+\frac{1}{2}\frac{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à

\\ \frac{d}{dx}x^{n+1}\ \to\ (n+1)x^n\\ \\ \frac{d}{dx}\frac{1}{1-x}=\frac{1}{(1-x)^2}

in termini rigorosi, si ricava la somma

\frac{1}{(1-x)^2}=\sum_{n=0}^{+\infty}(n+1)x^n

mediante il teorema di derivazione per le serie di potenze.

Ci siamo

f(x)=\frac{1}{4}\sum_{n=0}^{+\infty}(-x)^n+\frac{1}{4}\sum_{n=0}^{+\infty}x^n+\frac{1}{2}\sum_{n=0}^{+\infty}(n+1)x^n

riscriviamo il secondo membro come un'unica serie

f(x)=\sum_{n=0}^{+\infty}\frac{(-x)^n}{4}+\frac{x^n}{4}+\frac{n+1}{2}x^n

ossia

f(x)=\sum_{n=0}^{+\infty}\left[\frac{(-1)^n}{4}+\frac{1}{4}+\frac{n+1}{2}\right]x^n

ossia

f(x)=\sum_{n=0}^{+\infty}\left[\frac{(-1)^n+3+2n}{4}\right]x^n

Dalla definizione della funzione generatrice f(x)

\sum_{n=0}^{+\infty}a_nx^n=\sum_{n=0}^{+\infty}\left[\frac{(-1)^n+3+2n}{4}\right]x^n

ricaviamo per confronto il termine generale della tanto agognata successione \{a_n\}_n

a_n=\frac{(-1)^n+3+2n}{4}

Per il comportamento asintotico è sufficiente limitarsi a considerare l'infinito di ordine principale al tendere di n\to +\infty

a_n\sim_{n\to +\infty}\frac{n}{2}
Ringraziano: Ifrit, CarFaby, Christian1988

Re: Equazione di ricorrenza con le funzioni generatrici #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
Os