Ricorsione lineare..
Ciao a tutti sto cercando degli appunti sulla ricorsione lineare dato che google mi cerca solo risultati inerenti alla programmazione ricorsiva
il testo dell'esercizio è:
RISOLVERE LA RICORSIONE LINEARE $an=3an-1 + 4an-3$ per $ a >= 3 $
con le condizioni iniziali $a0=0,a1=1,a2=0$
mi date una mano a trovare materiale per risolvere queste ricorsioni GRAZIE MILLE!!!!
il testo dell'esercizio è:
RISOLVERE LA RICORSIONE LINEARE $an=3an-1 + 4an-3$ per $ a >= 3 $
con le condizioni iniziali $a0=0,a1=1,a2=0$
mi date una mano a trovare materiale per risolvere queste ricorsioni GRAZIE MILLE!!!!
Risposte
Immagino che l'esercizio sia questo:
Prova a scrivere quanto viene $a_3$, $a_4$,... e così via fino a $a_10$
Magari riesci a vedere come è fatta la successione
Trovare una forma precisa per $a_n$
${(a_n=3a_(n-1) + 4a_(n-3) ),(a_0=0),(a_1=1),(a_2=0):}$
Prova a scrivere quanto viene $a_3$, $a_4$,... e così via fino a $a_10$
Magari riesci a vedere come è fatta la successione
non so come si scrivono le formule come hai fatto te comunque
se $n=3$
$a3=3a3-1+4a3-2$ quindi dovrebbe essere così $a3=3*0+4*1$ quindi $a3=4$
perdonami ma devo calcolare in questo modo?
se $n=3$
$a3=3a3-1+4a3-2$ quindi dovrebbe essere così $a3=3*0+4*1$ quindi $a3=4$
perdonami ma devo calcolare in questo modo?
Aspetta un attimo:
La successione è $a_n=3a_(n-1) + 4a_(n-3) $ oppure $a_n=3a_(n-1) + 4a_(n-2) $?
Nel primo post hai scritto in un modo, nell'ultimo nell'altro modo.
Perchè se fosse il primo caso la vedo un po' difficile, mentre nel secondo caso mi sembra un po' più semplice.
Tornando alla tua domanda, la mia era solo un'idea.
Scrivendo precisamente quanto valgono $a_3$, $a_4$,... ci si può fare un'idea di come sia la successione
https://www.matematicamente.it/forum/com ... 26179.html
Qui è spiegato come scrivere le formule
La successione è $a_n=3a_(n-1) + 4a_(n-3) $ oppure $a_n=3a_(n-1) + 4a_(n-2) $?
Nel primo post hai scritto in un modo, nell'ultimo nell'altro modo.
Perchè se fosse il primo caso la vedo un po' difficile, mentre nel secondo caso mi sembra un po' più semplice.
Tornando alla tua domanda, la mia era solo un'idea.
Scrivendo precisamente quanto valgono $a_3$, $a_4$,... ci si può fare un'idea di come sia la successione
https://www.matematicamente.it/forum/com ... 26179.html
Qui è spiegato come scrivere le formule
scusami veramente.... il testo dell'esercizio scritto correttamente è così:
Risolvere la ricorsione lineare
$a_n=3a_(n-1)+4a_(n-3)$
per $n>=3$, con condizioni iniziali $a_0=0,a_1=1,a_2=0$
ora spero di essere stato un po piu chiaro spero che qualcuno mi sappia aiutare.
Risolvere la ricorsione lineare
$a_n=3a_(n-1)+4a_(n-3)$
per $n>=3$, con condizioni iniziali $a_0=0,a_1=1,a_2=0$
ora spero di essere stato un po piu chiaro spero che qualcuno mi sappia aiutare.
Intanto bravo, hai usato le formule e si legge tutto molto più chiaramente 
Temo che non ci sia una forma chiusa per definire $a_n$. O, se c'è, non è banalissima. Ecco
Magari qualcun altro potrà illuminarti o, spero, smentirmi
Temo che non ci sia una forma chiusa per definire $a_n$. O, se c'è, non è banalissima. Ecco
Magari qualcun altro potrà illuminarti o, spero, smentirmi
Ci sono molti modi per approcciare il problema.
Uno di questi è "indovinare" che la soluzione si esprime come multiplo di una potenza di un numero reale [tex]$t$[/tex] da determinarsi, ossia che si abbia [tex]$a_n=A\ t^n$[/tex] con [tex]$A\neq 0$[/tex].
Per trovare [tex]$t$[/tex], semplicemente sostituiamo la presunta espressione di [tex]$a_n$[/tex] nella ricorrenza: semplificando i coefficienti [tex]$A$[/tex] otteniamo [tex]$t^n=3t^{n-1}+4t^{n-3}$[/tex] e, semplificando le potenze, abbiamo infine [tex]$t^3-3t^2-4=0$[/tex].
Questa equazione di terzo grado ha una soluzioni reale [tex]$\tau_1$[/tex] e due complesse coniugate [tex]$\tau_2,\tau_3$[/tex] (che si possono calcolare con le formule di Cardano).
Conseguentemente, ogni successione del tipo [tex]$a_n=A_i\tau_i^n$[/tex] per [tex]$i=1,2,3$[/tex] risolve la ricorrenza e, dato che l'equazione è lineare, anche ogni successione del tipo [tex]$a_n=A_1\tau_1^n+A_2\tau_2^n+A_3\tau_3^n$[/tex] è soluzione della ricorrenza.
Trovata la "soluzione generale" della ricorrenza, bisogna solo determinare le costanti [tex]$A_i$[/tex] per le quali sono soddisfatte le condizioni iniziali (si noti lo straordinario parallelo con i metodi risolutivi del problema di Cauchy per le equazioni differenziali): ciò si fa imponendo le condizioni e ricavando un sistema lineare nelle [tex]$A_i$[/tex], che nel caso in esame è:
[tex]$\begin{cases} A_1+A_2+A_3=0 \\ \tau_1A_1+\tau_2A_2+\tau_3A_3=1 \\ \tau_1^2 A_1+\tau_2^2A_2+\tau_3^2A_3=0\end{cases}$[/tex];
risolvendo si trova:
[tex]$A_1=\frac{1}{\begin{vmatrix} 1 & 1 & 1 \\ \tau_1 & \tau_2 & \tau_3 \\ \tau_1^2 & \tau_2^2 & \tau_3^2 \end{vmatrix}}\ \begin{vmatrix} 0 & 1 & 1 \\ 1 & \tau_2 & \tau_3 \\ 0 & \tau_2^2 & \tau_3^2 \end{vmatrix} =-\frac{\tau_3+\tau_1}{(\tau_3-\tau_2)(\tau_2-\tau_1)}$[/tex]
[tex]$A_2=\frac{1}{\begin{vmatrix} 1 & 1 & 1 \\ \tau_1 & \tau_2 & \tau_3 \\ \tau_1^2 & \tau_2^2 & \tau_3^2 \end{vmatrix}}\ \begin{vmatrix} 1 & 0 & 1 \\ \tau_1 & 1 & \tau_3 \\ \tau_1^2 & 0 & \tau_3^2 \end{vmatrix}=\frac{\tau_3+\tau_2}{(\tau_3-\tau_1)(\tau_2-\tau_1)}$[/tex]
[tex]$A_3=\frac{1}{\begin{vmatrix} 1 & 1 & 1 \\ \tau_1 & \tau_2 & \tau_3 \\ \tau_1^2 & \tau_2^2 & \tau_3^2 \end{vmatrix}}\ \begin{vmatrix} 1 & 1 & 0 \\ \tau_1 & \tau_2 & 1 \\ \tau_1^2 & \tau_2^2 & 0 \end{vmatrix} =-\frac{\tau_2+\tau_1}{(\tau_3-\tau_1)(\tau_3-\tau_2)}$[/tex]
[N.B.: i determinanti al denominatore sono di Vandermonde e si calcolano con la nota formula.] quindi la soluzione cercata è:
[tex]$a_n=-\frac{\tau_3+\tau_1}{(\tau_3-\tau_2)(\tau_2-\tau_1)}\ \tau_1^n +\frac{\tau_3+\tau_2}{(\tau_3-\tau_1)(\tau_2-\tau_1)}\ \tau_2^n -\frac{\tau_2+\tau_1}{(\tau_3-\tau_1)(\tau_3-\tau_2)}\ \tau_3^n$[/tex].
La cosa divertente di tutta la faccenda è che la [tex]$a_n$[/tex] è formata da numeri naturali (se si vogliono fare le cose per bene, ciò si prova per induzione), nonostante nella sua espressione esplicita compaiano potenze di numeri complessi a gogo... Una cosa simile succede, ad esempio, con i numeri di Fibonacci.
P.S.: Ovviamente, ricontrollate i conti.
Uno di questi è "indovinare" che la soluzione si esprime come multiplo di una potenza di un numero reale [tex]$t$[/tex] da determinarsi, ossia che si abbia [tex]$a_n=A\ t^n$[/tex] con [tex]$A\neq 0$[/tex].
Per trovare [tex]$t$[/tex], semplicemente sostituiamo la presunta espressione di [tex]$a_n$[/tex] nella ricorrenza: semplificando i coefficienti [tex]$A$[/tex] otteniamo [tex]$t^n=3t^{n-1}+4t^{n-3}$[/tex] e, semplificando le potenze, abbiamo infine [tex]$t^3-3t^2-4=0$[/tex].
Questa equazione di terzo grado ha una soluzioni reale [tex]$\tau_1$[/tex] e due complesse coniugate [tex]$\tau_2,\tau_3$[/tex] (che si possono calcolare con le formule di Cardano).
Conseguentemente, ogni successione del tipo [tex]$a_n=A_i\tau_i^n$[/tex] per [tex]$i=1,2,3$[/tex] risolve la ricorrenza e, dato che l'equazione è lineare, anche ogni successione del tipo [tex]$a_n=A_1\tau_1^n+A_2\tau_2^n+A_3\tau_3^n$[/tex] è soluzione della ricorrenza.
Trovata la "soluzione generale" della ricorrenza, bisogna solo determinare le costanti [tex]$A_i$[/tex] per le quali sono soddisfatte le condizioni iniziali (si noti lo straordinario parallelo con i metodi risolutivi del problema di Cauchy per le equazioni differenziali): ciò si fa imponendo le condizioni e ricavando un sistema lineare nelle [tex]$A_i$[/tex], che nel caso in esame è:
[tex]$\begin{cases} A_1+A_2+A_3=0 \\ \tau_1A_1+\tau_2A_2+\tau_3A_3=1 \\ \tau_1^2 A_1+\tau_2^2A_2+\tau_3^2A_3=0\end{cases}$[/tex];
risolvendo si trova:
[tex]$A_1=\frac{1}{\begin{vmatrix} 1 & 1 & 1 \\ \tau_1 & \tau_2 & \tau_3 \\ \tau_1^2 & \tau_2^2 & \tau_3^2 \end{vmatrix}}\ \begin{vmatrix} 0 & 1 & 1 \\ 1 & \tau_2 & \tau_3 \\ 0 & \tau_2^2 & \tau_3^2 \end{vmatrix} =-\frac{\tau_3+\tau_1}{(\tau_3-\tau_2)(\tau_2-\tau_1)}$[/tex]
[tex]$A_2=\frac{1}{\begin{vmatrix} 1 & 1 & 1 \\ \tau_1 & \tau_2 & \tau_3 \\ \tau_1^2 & \tau_2^2 & \tau_3^2 \end{vmatrix}}\ \begin{vmatrix} 1 & 0 & 1 \\ \tau_1 & 1 & \tau_3 \\ \tau_1^2 & 0 & \tau_3^2 \end{vmatrix}=\frac{\tau_3+\tau_2}{(\tau_3-\tau_1)(\tau_2-\tau_1)}$[/tex]
[tex]$A_3=\frac{1}{\begin{vmatrix} 1 & 1 & 1 \\ \tau_1 & \tau_2 & \tau_3 \\ \tau_1^2 & \tau_2^2 & \tau_3^2 \end{vmatrix}}\ \begin{vmatrix} 1 & 1 & 0 \\ \tau_1 & \tau_2 & 1 \\ \tau_1^2 & \tau_2^2 & 0 \end{vmatrix} =-\frac{\tau_2+\tau_1}{(\tau_3-\tau_1)(\tau_3-\tau_2)}$[/tex]
[N.B.: i determinanti al denominatore sono di Vandermonde e si calcolano con la nota formula.] quindi la soluzione cercata è:
[tex]$a_n=-\frac{\tau_3+\tau_1}{(\tau_3-\tau_2)(\tau_2-\tau_1)}\ \tau_1^n +\frac{\tau_3+\tau_2}{(\tau_3-\tau_1)(\tau_2-\tau_1)}\ \tau_2^n -\frac{\tau_2+\tau_1}{(\tau_3-\tau_1)(\tau_3-\tau_2)}\ \tau_3^n$[/tex].
La cosa divertente di tutta la faccenda è che la [tex]$a_n$[/tex] è formata da numeri naturali (se si vogliono fare le cose per bene, ciò si prova per induzione), nonostante nella sua espressione esplicita compaiano potenze di numeri complessi a gogo... Una cosa simile succede, ad esempio, con i numeri di Fibonacci.
P.S.: Ovviamente, ricontrollate i conti.
grazie mille per le vostre risposte ma esiste un metodo molto più semplice che per mancanza di appunti non reperibili non ho modo di farvi vedere comunque cercherò di contattare il professore per vedere se mi da una mano ma non ci credo GRAZIE ANCORA!!!!!!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo