A volte riesce facile, a volte meno, come da titolo, in che modo si passa da una relazione ricorsiva a una formula chiusa?
(ho l'impressione che ci sia della teoria dietro, ma non so di che tipo xD)
Posto un esempio, così ci capiamo:
[tex]S_{n+1}=2S_n+A_n+B_n[/tex]
[tex]A_{n+1}=2A_n+A_n+B_n[/tex]
[tex]B_{n+1}=2B_n+S_n+A_n[/tex]
Scrivere [tex]S_{n+1}[/tex] in formula chiusa (in funzione di [tex]n[/tex] e di [tex]A_1,B_1,S_1[/tex]), o almeno indicare come si deve procedere.
Passare da relazioni ricorsive a formule chiuse
Re: Passare da relazioni ricorsive a formule chiuse
C'è della teoria dietro; piuttosto che buttarti lì il modo elementare calato dal cielo, scrivo come ci si arriva (magari esistono modi più semplici). Se non la capisci penso la cosa migliore sia aspettare finché non studierai algebra lineare.
La relazione, a meno di un typo, penso sia in forma matriciale
\[\begin{pmatrix}
S_{n+1} \\
A_{n+1} \\
B_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
2 &1 &1 \\
1 & 2 &1 \\
1& 1& 2
\end{pmatrix}
\begin{pmatrix}
S_{n} \\
A_{n} \\
B_{n}
\end{pmatrix} \]
o per brevità
\[ X_{n+1}=MX_n. \]
Notiamo ora che
\[M=JDJ^{-1} \]
ove
\[ D=\begin{pmatrix}
1 &0 &0\\
0 & 1 &0 \\
0& 0& 4
\end{pmatrix},
J=\begin{pmatrix}
-1 &-1 &1\\
0 & 1 &1 \\
1& 0& 1
\end{pmatrix},
J^{-1}=\frac 1 3 \begin{pmatrix}
-1 &-1 &2\\
-1 & 2 &-1 \\
1& 1& 1
\end{pmatrix}.
\]
Quindi
\[X_n=M^nX_0=(JDJ^{-1})^nX_0=JD^nJ^{-1}X_0=\]
\[ =\begin{pmatrix}
-1 &-1 &1\\
0 & 1 &1 \\
1& 0& 1
\end{pmatrix}
\begin{pmatrix}
1 &0 &0\\
0 & 1 &0 \\
0& 0& 4^n
\end{pmatrix}
\frac 1 3 \begin{pmatrix}
-1 &-1 &2\\
-1 & 2 &-1 \\
1& 1& 1
\end{pmatrix}
\begin{pmatrix}
S_0 \\
A_0 \\
B_0
\end{pmatrix}
.\]
Quindi, a meno di errori di conto, $3S_n=4^n(S_0+A_0+B_0)+(2S_0-A_0-B_0)$.
La relazione, a meno di un typo, penso sia in forma matriciale
\[\begin{pmatrix}
S_{n+1} \\
A_{n+1} \\
B_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
2 &1 &1 \\
1 & 2 &1 \\
1& 1& 2
\end{pmatrix}
\begin{pmatrix}
S_{n} \\
A_{n} \\
B_{n}
\end{pmatrix} \]
o per brevità
\[ X_{n+1}=MX_n. \]
Notiamo ora che
\[M=JDJ^{-1} \]
ove
\[ D=\begin{pmatrix}
1 &0 &0\\
0 & 1 &0 \\
0& 0& 4
\end{pmatrix},
J=\begin{pmatrix}
-1 &-1 &1\\
0 & 1 &1 \\
1& 0& 1
\end{pmatrix},
J^{-1}=\frac 1 3 \begin{pmatrix}
-1 &-1 &2\\
-1 & 2 &-1 \\
1& 1& 1
\end{pmatrix}.
\]
Quindi
\[X_n=M^nX_0=(JDJ^{-1})^nX_0=JD^nJ^{-1}X_0=\]
\[ =\begin{pmatrix}
-1 &-1 &1\\
0 & 1 &1 \\
1& 0& 1
\end{pmatrix}
\begin{pmatrix}
1 &0 &0\\
0 & 1 &0 \\
0& 0& 4^n
\end{pmatrix}
\frac 1 3 \begin{pmatrix}
-1 &-1 &2\\
-1 & 2 &-1 \\
1& 1& 1
\end{pmatrix}
\begin{pmatrix}
S_0 \\
A_0 \\
B_0
\end{pmatrix}
.\]
Quindi, a meno di errori di conto, $3S_n=4^n(S_0+A_0+B_0)+(2S_0-A_0-B_0)$.
Re: Passare da relazioni ricorsive a formule chiuse
Premettendo che non so nulla di algebra lineare (e che mi sono arrangiato cercando su wikipedia):
In pratica applichi [tex]n[/tex] volte la trasformazione [tex]M[/tex].
Poi ti trovi [tex]J[/tex] t.c. puoi prendere una matrice che esponenzialmente la controlli facilmente, e [tex]J[/tex] non lo calcoli perchè hai l'inverso (ma qui evito di fare altre figuracce, e quindi mi fermo).
E svolgi i prodotti (mi rimane il dubbio sulla commutatività delle operazioni).
La formula è all'incirca giusta (c'è giusto un errore all'esponente forse) ma bon, non è importante.
Se invece volessi ricavarla in modo elementare, come potrei fare (è troppo presto per l'algebra lineare)?
In pratica applichi [tex]n[/tex] volte la trasformazione [tex]M[/tex].
Poi ti trovi [tex]J[/tex] t.c. puoi prendere una matrice che esponenzialmente la controlli facilmente, e [tex]J[/tex] non lo calcoli perchè hai l'inverso (ma qui evito di fare altre figuracce, e quindi mi fermo).
E svolgi i prodotti (mi rimane il dubbio sulla commutatività delle operazioni).
La formula è all'incirca giusta (c'è giusto un errore all'esponente forse) ma bon, non è importante.
Se invece volessi ricavarla in modo elementare, come potrei fare (è troppo presto per l'algebra lineare)?
Re: Passare da relazioni ricorsive a formule chiuse
Diciamo che $J$ e $J^{-1}$ le calcolo ma è un conto facile; piuttosto che usare la commutatività della moltiplicazione (che per matrici è falsa) uso semplicemente l'associatività. Anche se si potrebbe riformulare in termini di trick elementari, l'idea che ci sarebbe dietro sarebbe sempre quella di diagonalizzare un'opportuna matrice, ovvero farla diventare una matrice diagonale tramite coniugio. Questo perché sia una matrice diagonale sia l'operazione di coniugio si comportano molto bene facendo le potenze: la potenza di una matrice diagonale $D$ è la matrice diagonale con le potenze degli elementi diagonali di $D$ sulla sua diagonale, e d'altra parte $(JDJ^{-1})^n=JD^nJ^{-1}$.
Se ti soddisfa di più, la roba che ho scritto sopra si può riformulare senza algebra lineare come "definisco $\tilde{S}_n=(2B_n-S_n-A_n)/3$, $\tilde{A}_n=(2A_n-S_n-B_n)/3$, $\tilde{B}_n=(S_n+A_n+B_n)/3$, e noto che per magia queste nuove quantità soddisfano ricorsioni lineari non intrecciate, che so risolvere"; ma sarebbe appunto lo stesso risultato riformulato in altri termini e per di più calato dal cielo, e la tecnica generale per arrivare a queste scritture è quella che ho scritto prima.
Se ti soddisfa di più, la roba che ho scritto sopra si può riformulare senza algebra lineare come "definisco $\tilde{S}_n=(2B_n-S_n-A_n)/3$, $\tilde{A}_n=(2A_n-S_n-B_n)/3$, $\tilde{B}_n=(S_n+A_n+B_n)/3$, e noto che per magia queste nuove quantità soddisfano ricorsioni lineari non intrecciate, che so risolvere"; ma sarebbe appunto lo stesso risultato riformulato in altri termini e per di più calato dal cielo, e la tecnica generale per arrivare a queste scritture è quella che ho scritto prima.