Formule chiuse successioni per ricorrenza

[Fede:)]

Come posso trovare una formula chiusa a successioni con una relazione ricorsiva del tipo [math] a_n=ka_{n-1}+f(n) con una generica [math]f(n) e con [math]a_0 noto?
Ho capito che andrebbe introdotta una seconda successione [math]b_n che soddisfa la legge ricorsiva, così sottraendola alla prima se ne ottiene una terza [math]c_n senza [math] f(n), ma poi per trovare una formula chiusa per [math]a_n dovrei conoscere quella per [math]b_n, e visto che hanno la stessa legge ricorsiva sono da punto a capo.

[matpro98]

prova a spulciare qualche videolezione del senior, credo che tu possa trovare questi argomenti spiegati abbastanza bene in alcuni video A3 Medium (correggetemi se sbaglio)

[karlosson_sul_tetto]

In generale non c'è una formula "bella" per scrivere la soluzione, a differenza di una ricorrenza omogenea (cioé senza il termine $f(n)$), principalmente perché $f(n)$ potrebbe essere una funzione brutta a piacere.

Tuttavia se $f$ è un polinomio, esponenziale o una cominazione di esponenziali e polinomi, c'è un modo per indovinare una soluzione particolare $b_n$.

Per esempio, sia $f(n)=n^2-1$ un polinomio di secondo grado. Allora come guess per $b_n$, prendo un generico polinomio di secondo grado:
$$b_n=An^2+Bn+C$$

Impongo che valga la relazione $b_n=k b_{n-1} + f(n)$ per trovare i coefficienti A,B,C:

$$(An^2+Bn+C) = k (A (n-1)^2 + B(n-1) + C) + n^2 -1 $$
Espando e porto tutto al membro di destra:
$$ n^2 (kA +1 - A) + n (-2k A + kB - B) + (kA-kB+kC -1 - C) = 0$$
Questo dev'essere 0 per ogni valore di $n$; dato che è un polinomio, vuol dire che tutti i suoi coefficienti sono 0:
$kA + 1 - A=0$ implica $A=\frac{1}{1-k}$
$-2k A + kB - B=0$ implica $B=\frac{-2kA}{1-k} = \frac{-2k}{(1-k)^2}$
Infine da $kA-kB+kC -1 - C$ si ottiene $C=\frac{kB-kA+1}{1-k}=\frac{1}{(1-k)^3}(2-k+2k^2)$

Hai ottenuto i coefficienti del polinomio, dunque sai calcolarti $b_n$. (e sai risolvere l'equazione originale aggiungendo le soluzioni dell'omogenea, come hai già detto ).


Se hai un'esponenziale, per esempio $f(n)=3^n$, allora come soluzione particolare provi un altro esponenziale: $b_n= D*E^n$.
Imponendo $b_n=k b_{n-1} + f(n)$ vedi che dev'essere necessariemente $E=3$, e facendo qualche conto trovi il valore della costante moltiplicativa $D$. Se la $f$ è ancora più complicata, puoi provare combinazioni con esponenziali e polinomi, come $b_n=(n^3-2n)\cdot 5^n - n\cdot 2^n$.

Ora, un po' di domande:

1) Trova una soluzione particolare di $a_n = k\cdot a_{n-1} + 4n$

2) Come risolvere $a_n = 4a_{n-1}-3a_{n-2} + 2^n + (1/6)^n +15^n + 2n^3-5n+1$ senza morire di conti? (hint: come ci siamo eliminati il problema "dell'omogenea"?)

3) Nella soluzione di sopra compare un $\frac{1}{1-k}$, dunque le costanti che abbiamo calcolato non sono definite se $k=1$. Per questo valore, perché non funziona? Come si può calcolare alternativamente?

4) Risolvere $a_n = 5 a_{n-1} -6 a_{n-2} +2^n$




Puoi trovare altri esempi ed applicazioni nelle lezioni senior medium A3 degli ultimi anni.

[Fede:)]

Grazie mille!
In realtà è proprio in un video del senior basic(non sapevo si trattassero anche al medium) A3 che ho visto quest'idea dell'introdurre una nuova successione, e mi sono venuti questi dubbi, ovviamente intuivo che non poteva esistere una formula generale ma non avevo capito come scegliere [math]b_n in casi più tosti.
Quindi credo di aver capito che nei limiti dei calcoli o con qualche trucchetto è fattibile ma se [math]f(n) è tanto brutta posso fare poco, e alla fine la formula chiusa devo un po' intuirla per introdurre [math]b_n.
1)

Testo nascosto:

Visto che [math]f(n) è un polinomio di primo grado introduco [math]b_n=An+B e imponendo che soddisfi la legge ricorsiva, applicando il principio di identità tra polinomi, ottengo [math]A=4/(1-k) e [math]B=-4k/(1-k)^2 quindi [math]a_n=a_0k^n+4k/(k-1)-4k/(k-1)^2.

2) Questo proprio non mi viene, ho anche dato un'occhiata ai pdf del medium ma niente

Testo nascosto:

Sia [math]b_n una successione che soddisfa la legge ricorsiva, e sia [math]x_n=a_n-b_n, da cui [math]x_n=4x_{n-1}-3x_{n-2} e quindi [math] x_n=u+v3^n da cui [math] a_n=u+v3^n+b_n con [math]u,v che trovo con le due condizioni iniziali su [math]a_0 e [math]a_1, ma qui non ho idea di quale possa essere una buona [math]b_n visto che costante non può essere e non vedo trucchetti come quello che ho usato sul 4, quindi non saprei proprio

3)

Testo nascosto:

Se [math] k=1 ,[math] P(n) non soddisfa mai quella condizione ma si può notare [math]a_n=a_{n-1}+f(n)=a_{n-2}+f(n)+f(n-1)=a_{n-3}+f(n)+f(n-1)+f(n-2)=... da cui [math]a_n=a_0+\sum_{i=1}^n{ f(i)} e con [math]f(n)=n^2-1 concludo [math]a_n=a_0+n(n+1)(2n+1)/6 -n.

4)

Testo nascosto:

[math]a_{n-1}=5a_{n-2}-6a_{n-3}+2^{n-1}, moltiplicandola per 2 e sottraendola a quella del testo ottengo [math]a_n=7a_{n-1}-16a_{n-2}+12a_{n-3}, le soluzioni del polinomio caratteristico sono [math]3 e [math]2 con molteplicità 2, quindi la formula chiusa sarà [math]a_n=u3^n+v2^n+wn2^n, conoscendo [math]a_0 e [math]a_1 ricavo [math]a_2 dalla relazione iniziale, e con queste 3 condizioni trovo [math]u,v e [math]w.

[karlosson_sul_tetto]

Benissimo!

Riguardo il 2: quando ci sono più pezzi in [math]f(n), è possibile "separarli" e risolvere separatemente ogni equazione (compresa l'omogenea), e poi combinarle insieme.
Per semplicità lo mostro con un'equazione ridotta: [math]a_n=4a_{n-1}-3a_{n-2}+2^n+(\frac{1}{6})^n

La soluzione dell'omogenea [math]x_n=4x_{n-1}-3x_{n-2} è [math]x_n = u + v 3^n.
Considera ora la "prima" equazione particolare, [math]c_n = 4c_{n-1}-3c_{n-2}+2^n; provando[math] c_n = \alpha 2^n si trova [math]\alpha=-4.
Guardando solo il secondo pezzo, [math]d_n = 4d_{n-1}-3d_{n-2}+(\frac{1}{6})^n, una sua soluzione particolare è [math]d_n=\frac{1}{73} \cdot (\frac{1}{6})^n.

Dunque la soluzione generale è data da

[math]a_n = omogenea + particolare_1 + particolare_2 = x_n + c_n + d_n = u + v\cdot 3^n - 4 \cdot 2^n + \frac{1}{73} \cdot (\frac{1}{6})^n

Perché è effettivamente una soluzione? Se guardiamo la formula ricorsiva, si vede meglio:

[math]a_n = x_n + c_n + d_n = (4x_{n-1}-3x_{n-2}) + (4c_{n-1}-3c_{n-2}+2^n) + (4d_{n-1}-3d_{n-2}+(\frac{1}{6})^n) =
[math]=4 (x_{n-1} + c_{n-1}+ d_{n-1}) - 3 (x_{n-2} + c_{n-2}+ d_{n-2}) + 2^n +(\frac{1}{6})^n = 4a_{n-1}-3a_{n-2}+2^n+(\frac{1}{6})^n

E quindi soddisfa la relazione di ricorrenza.
Lo stesso trucco funziona anche per più addendi (anche con polinomi, o termini misti come [math]n^2\cdot 5^n).


Un'altra osservazione interessante: non è un caso che nel punto 3), la formula per [math]a_n sia un polinomio. Infatti, nascosta sotto al tappeto c'è lo stesso principio di "se non funziona un esponenziale [math]k^n, prova con [math]n\cdot k^n, n^2 \cdot k^n, ecc; solo che la base è $k=1$, (radice dell'equazione omogenea associata [math]a_n=a_{n-1}, che di per se una ricorrenza stupida), quindi non si nota la presenza dell'esponenziale.

[Fede:)]

Grazie!