Ricorsione lineare omogenea di grado 3
Ciao a tutti,
è un po' che tento senza successo di trovare una soluzione ad una ricorsione lineare omogenea di grado 3, a naso direi che la soluzione dovrebbe essere semplice ma purtroppo non trovo materiale su internet (Trovo solo chi si ferma al grado 2...)
la ricorsione è la seguente:
\(\displaystyle
a_n=a_{n-1}-a_{n-2}+a_{n-3}
\\ con \\
a_0=0, a_1=1, a_2=0
\)
Io l'ho approcciata in questo modo:
Polinomio caratteristico:
\(\displaystyle
r^3-r^2+r-1=0
\\ovvero
\\(r-1)(r^2+1)
\)
La cui unica radice è 1, qui mi fermo, però mi viene detto che in una ricorsione di grado 2 se trovo una sola radice, posso trovare un altra soluzione moltiplicando per n la precedente, in questo modo:
\(\displaystyle
a_n = r^n
\\ a'_n = nr^n
\)
Dunque io ho azzardato che essendo la mia ricorsione di grado 3 ho bisogno di almeno 3 soluzioni, dunque ho provato a fare in questo modo:
\(\displaystyle
a_n = r^n
\\ a'_n = nr^n
\\ a''_n = nnr^n
\)
e quindi ad avere una soluzione di questo tipo:
\(\displaystyle
a_n=C_1r^n+C_2nr^n+C_3nnr^n
\)
che assieme alle condizioni iniziali mi da il seguente sistema:
\left\{\begin{matrix}
C_1=0
\\ C_1+C_2+C_3=1
\\ C_1+2C_2+4C_3=0
\end{matrix}\right.
che risolto mi da C1=0, C2=2, C3=-1
dunque la soluzione dovrebbe essere:
\(\displaystyle
a_n=2n-n^2
\)
L'unico problema è che dopo averla testata assieme a qualche risultato della ricorsione originale, non combacia nulla :'(
Potete aiutarmi? (Ci batto la testa da due giorni)
Grazie!
Luca
è un po' che tento senza successo di trovare una soluzione ad una ricorsione lineare omogenea di grado 3, a naso direi che la soluzione dovrebbe essere semplice ma purtroppo non trovo materiale su internet (Trovo solo chi si ferma al grado 2...)
la ricorsione è la seguente:
\(\displaystyle
a_n=a_{n-1}-a_{n-2}+a_{n-3}
\\ con \\
a_0=0, a_1=1, a_2=0
\)
Io l'ho approcciata in questo modo:
Polinomio caratteristico:
\(\displaystyle
r^3-r^2+r-1=0
\\ovvero
\\(r-1)(r^2+1)
\)
La cui unica radice è 1, qui mi fermo, però mi viene detto che in una ricorsione di grado 2 se trovo una sola radice, posso trovare un altra soluzione moltiplicando per n la precedente, in questo modo:
\(\displaystyle
a_n = r^n
\\ a'_n = nr^n
\)
Dunque io ho azzardato che essendo la mia ricorsione di grado 3 ho bisogno di almeno 3 soluzioni, dunque ho provato a fare in questo modo:
\(\displaystyle
a_n = r^n
\\ a'_n = nr^n
\\ a''_n = nnr^n
\)
e quindi ad avere una soluzione di questo tipo:
\(\displaystyle
a_n=C_1r^n+C_2nr^n+C_3nnr^n
\)
che assieme alle condizioni iniziali mi da il seguente sistema:
\left\{\begin{matrix}
C_1=0
\\ C_1+C_2+C_3=1
\\ C_1+2C_2+4C_3=0
\end{matrix}\right.
che risolto mi da C1=0, C2=2, C3=-1
dunque la soluzione dovrebbe essere:
\(\displaystyle
a_n=2n-n^2
\)
L'unico problema è che dopo averla testata assieme a qualche risultato della ricorsione originale, non combacia nulla :'(
Potete aiutarmi? (Ci batto la testa da due giorni)
Grazie!
Luca
Risposte
Il polinomio caratteristico della ricorrenza ha tre radici, una reale e due complesse coniugate, cioé:
\[
r_1=1,\ r_2=\imath,\ r_3=-\imath\; ,
\]
dunque la soluzione generale della ricorrenza (pensata, per fare i conti, come successione complessa) ha il termine generale nella forma:
\[
a_n= A + B\ \imath^n + C\ (-\imath)^n
\]
con \(A,B,C\) costanti complesse da determinare imponendo le condizioni iniziali:
\[
\begin{split}
0 &= A+B+C\\
1 &= A+\imath B -\imath C\\
0 &= A - B - C
\end{split}
\]
da cui si ricava \(A=0\), \(B=-\frac{1}{2}\imath\) e \(C=\frac{1}{2}\imath\); perciò, usando un po' di algebra, la soluzione è:
\[
a_n = - \frac{\imath^{n+1} + (-\imath)^{n+1}}{2}\; .
\]
Ma si ha:
\[
\imath^{n+1} = \begin{cases} \imath &\text{, se } n=4k\\
-1 &\text{, se } n=4k+1\\
-\imath &\text{, se } n=4k+2\\
1 &\text{, se } n=4k+3
\end{cases} \qquad \text{e} \qquad (-\imath)^{n+1} = \begin{cases} -\imath &\text{, se } n=4k\\
-1 &\text{, se } n=4k+1\\
\imath &\text{, se } n=4k+2\\
1 &\text{, se } n=4k+3
\end{cases}
\]
quindi:
\[
\imath^{n+1} + (-\imath)^{n+1} = \begin{cases} 0 &\text{, se } n=4k\\
-2 &\text{, se } n=4k+1\\
0 &\text{, se } n=4k+2\\
2 &\text{, se } n=4k+3
\end{cases}
\]
ed infine:
\[
a_n=\begin{cases} 0 &\text{, se } n=4k\\
1 &\text{, se } n=4k+1\\
0 &\text{, se } n=4k+2\\
-1 &\text{, se } n=4k+3
\end{cases}
\]
ossia:
\[
a_n = \cos \left( \frac{(n-1)\pi}{2}\right)\; .
\]
\[
r_1=1,\ r_2=\imath,\ r_3=-\imath\; ,
\]
dunque la soluzione generale della ricorrenza (pensata, per fare i conti, come successione complessa) ha il termine generale nella forma:
\[
a_n= A + B\ \imath^n + C\ (-\imath)^n
\]
con \(A,B,C\) costanti complesse da determinare imponendo le condizioni iniziali:
\[
\begin{split}
0 &= A+B+C\\
1 &= A+\imath B -\imath C\\
0 &= A - B - C
\end{split}
\]
da cui si ricava \(A=0\), \(B=-\frac{1}{2}\imath\) e \(C=\frac{1}{2}\imath\); perciò, usando un po' di algebra, la soluzione è:
\[
a_n = - \frac{\imath^{n+1} + (-\imath)^{n+1}}{2}\; .
\]
Ma si ha:
\[
\imath^{n+1} = \begin{cases} \imath &\text{, se } n=4k\\
-1 &\text{, se } n=4k+1\\
-\imath &\text{, se } n=4k+2\\
1 &\text{, se } n=4k+3
\end{cases} \qquad \text{e} \qquad (-\imath)^{n+1} = \begin{cases} -\imath &\text{, se } n=4k\\
-1 &\text{, se } n=4k+1\\
\imath &\text{, se } n=4k+2\\
1 &\text{, se } n=4k+3
\end{cases}
\]
quindi:
\[
\imath^{n+1} + (-\imath)^{n+1} = \begin{cases} 0 &\text{, se } n=4k\\
-2 &\text{, se } n=4k+1\\
0 &\text{, se } n=4k+2\\
2 &\text{, se } n=4k+3
\end{cases}
\]
ed infine:
\[
a_n=\begin{cases} 0 &\text{, se } n=4k\\
1 &\text{, se } n=4k+1\\
0 &\text{, se } n=4k+2\\
-1 &\text{, se } n=4k+3
\end{cases}
\]
ossia:
\[
a_n = \cos \left( \frac{(n-1)\pi}{2}\right)\; .
\]
Grazie per la risposta gugo!
Però il mio dubbio è questo: il corso per cui sto affrontando questo esercizio è un corso di Matematica Discreta per Scienze Informatiche e sono sicuro che il professore non abbia mai affrontato la questione dei numeri complessi e che sia prevista la risoluzione di questo esercizio solamente facendo riferimento al campo dei reali.
In questo http://www.cs.cmu.edu/~adamchik/21-127/lectures/recursion_5_print.pdf documento ho trovato alla pagina 2 il teorema: "Sia (lambda) una radice di ordine p dell'equazione caratteristica. Allora"
\(\displaystyle
\lambda^n , n\lambda^n, n^2\lambda^n, ..., n^{p-1}\lambda^n
\)
"Sono tutte soluzioni della ricorrenza."
non è possibile utilizzare questo teorema per risolvere il problema?
Però il mio dubbio è questo: il corso per cui sto affrontando questo esercizio è un corso di Matematica Discreta per Scienze Informatiche e sono sicuro che il professore non abbia mai affrontato la questione dei numeri complessi e che sia prevista la risoluzione di questo esercizio solamente facendo riferimento al campo dei reali.
In questo http://www.cs.cmu.edu/~adamchik/21-127/lectures/recursion_5_print.pdf documento ho trovato alla pagina 2 il teorema: "Sia (lambda) una radice di ordine p dell'equazione caratteristica. Allora"
\(\displaystyle
\lambda^n , n\lambda^n, n^2\lambda^n, ..., n^{p-1}\lambda^n
\)
"Sono tutte soluzioni della ricorrenza."
non è possibile utilizzare questo teorema per risolvere il problema?
"oslinux":
Però il mio dubbio è questo: il corso per cui sto affrontando questo esercizio è un corso di Matematica Discreta per Scienze Informatiche e sono sicuro che il professore non abbia mai affrontato la questione dei numeri complessi e che sia prevista la risoluzione di questo esercizio solamente facendo riferimento al campo dei reali.
Il libro di riferimento che dice? Possibile che non faccia mensione del caso complesso?
Ad ogni modo, nel caso in cui il polinomio caratteristico abba come radici la coppia di numeri complessi coniugati:
\[
\alpha\pm \beta\imath
\]
con \(\beta > 0\), allora nell'espressione della soluzione generale della ricorrenza puoi sempre rimpiazzare le due potenze complesse \((\alpha +\beta\ \imath)^n\) e \((\alpha -\beta\ \imath)^n\) con le successioni:
\[
\sqrt{\alpha^2 +\beta^2}\ \cos (n\ \theta)\qquad \text{e}\qquad \sqrt{\alpha^2 +\beta^2}\ \sin (n\ \theta)
\]
in cui \(\theta\in [0,\pi]\) è l'argomento del numero complesso \(\alpha +\beta \imath\).
"oslinux":
In questo http://www.cs.cmu.edu/~adamchik/21-127/lectures/recursion_5_print.pdf documento ho trovato alla pagina 2 il teorema: "Sia (lambda) una radice di ordine p dell'equazione caratteristica. Allora"
\(\displaystyle
\lambda^n , n\lambda^n, n^2\lambda^n, ..., n^{p-1}\lambda^n
\)
"Sono tutte soluzioni della ricorrenza."
non è possibile utilizzare questo teorema per risolvere il problema?
Ovviamente no.
Infatti, nel tuo caso il polinomio caratteristico non ha radici multiple, ma solo tre radici semplci (perché distinte).
Il teorema che citi avresti potuto applicarlo per risolvere, ad esempio, la ricorrenza:
\[
a_n-3a_{n-1}+4a_{n-3}=0
\]
il cui polinomio caratteristico è \(r^3-3r^2+4 = (r-2)^2(r+1)\); conseguentemente le radici del polinomio caratteristico sono \(r_1=2\) ed \(r_2=-1\), con \(r_1\) di molteplicità \(2\), ed il teorema da te citato si applica, fornendo come soluzione generale la successione di termine generale:
\[
a_n = A\ 2^n + B\ n2^n + C\ (-1)^n\; .
\]
Non abbiamo libri di riferimento, gli appunti per le lezioni non danno informazioni a riguardo ed essendo un corso del primo semestre del primo anno, non abbiamo esperienze con i numeri complessi, non è possibile che ci sia qualche semplificazione a priori nella ricorsione?
Grazie comunque del tuo tempo, sei stato chiaro e gentilissimo.
Grazie comunque del tuo tempo, sei stato chiaro e gentilissimo.
Per quanto riguarda i testi, essi devono essere consigliati dal docente.
Non esiste che un docente universitario non suggerisca una bibliografia (anche minima) per studiare gli argomenti del corso.
Per la questione della semplificazione, si potrebbe fare come segue.
Ponendo \(b_n:=a_n-a_{n-1}\) per \(n\geq 1\), la ricorrenza si riscrive come:
\[
\begin{cases}
b_n=-b_{n-2}\\
b_1=1\\
b_2=-1
\end{cases}
\]
che ha associato il polinomio caratteristico:
\[
r^2+1=0
\]
il quale ha radici complesse \(\pm \imath\).
Come vedi, in questi problemi qui i numeri complessi vengono fuori in maniera del tutto naturale; quindi mi pare davvero strano che non li abbiate mai usati durante il corso, e che non vi sia mai stata menzionata l'eventualità che il polinomio caratteristico associato alla ricorrenza abbia radici complesse.
Non esiste che un docente universitario non suggerisca una bibliografia (anche minima) per studiare gli argomenti del corso.
Per la questione della semplificazione, si potrebbe fare come segue.
Ponendo \(b_n:=a_n-a_{n-1}\) per \(n\geq 1\), la ricorrenza si riscrive come:
\[
\begin{cases}
b_n=-b_{n-2}\\
b_1=1\\
b_2=-1
\end{cases}
\]
che ha associato il polinomio caratteristico:
\[
r^2+1=0
\]
il quale ha radici complesse \(\pm \imath\).
Come vedi, in questi problemi qui i numeri complessi vengono fuori in maniera del tutto naturale; quindi mi pare davvero strano che non li abbiate mai usati durante il corso, e che non vi sia mai stata menzionata l'eventualità che il polinomio caratteristico associato alla ricorrenza abbia radici complesse.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo