OliForum Matematico

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.

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)

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.

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) 2) Questo proprio non mi viene, ho anche dato un'occhiata ai pdf del medium ma niente 3) 4)

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.

Grazie!