Formule chiuse successioni per ricorrenza

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Fede:)
Messaggi: 6
Iscritto il: 15 mar 2020, 11:51

Formule chiuse successioni per ricorrenza

Messaggio da Fede:) »

Come posso trovare una formula chiusa a successioni con una relazione ricorsiva del tipo [math] con una generica [math] e con [math] noto?
Ho capito che andrebbe introdotta una seconda successione [math] che soddisfa la legge ricorsiva, così sottraendola alla prima se ne ottiene una terza [math] senza [math], ma poi per trovare una formula chiusa per [math] dovrei conoscere quella per [math], e visto che hanno la stessa legge ricorsiva sono da punto a capo.
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Formule chiuse successioni per ricorrenza

Messaggio da 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)
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Formule chiuse successioni per ricorrenza

Messaggio da 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.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Fede:)
Messaggi: 6
Iscritto il: 15 mar 2020, 11:51

Re: Formule chiuse successioni per ricorrenza

Messaggio da 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] in casi più tosti.
Quindi credo di aver capito che nei limiti dei calcoli o con qualche trucchetto è fattibile ma se [math] è tanto brutta posso fare poco, e alla fine la formula chiusa devo un po' intuirla per introdurre [math].
1)
Testo nascosto:
Visto che [math] è un polinomio di primo grado introduco [math] e imponendo che soddisfi la legge ricorsiva, applicando il principio di identità tra polinomi, ottengo [math] e [math] quindi [math].
2) Questo proprio non mi viene, ho anche dato un'occhiata ai pdf del medium ma niente
Testo nascosto:
Sia [math] una successione che soddisfa la legge ricorsiva, e sia [math], da cui [math] e quindi [math] da cui [math] con [math] che trovo con le due condizioni iniziali su [math] e [math], ma qui non ho idea di quale possa essere una buona [math] 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],[math] non soddisfa mai quella condizione ma si può notare [math] da cui [math] e con [math] concludo [math].
4)
Testo nascosto:
[math], moltiplicandola per 2 e sottraendola a quella del testo ottengo [math], le soluzioni del polinomio caratteristico sono [math] e [math] con molteplicità 2, quindi la formula chiusa sarà [math], conoscendo [math] e [math] ricavo [math] dalla relazione iniziale, e con queste 3 condizioni trovo [math] e [math].
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Formule chiuse successioni per ricorrenza

Messaggio da karlosson_sul_tetto »

Benissimo!

Riguardo il 2: quando ci sono più pezzi in [math], è possibile "separarli" e risolvere separatemente ogni equazione (compresa l'omogenea), e poi combinarle insieme.
Per semplicità lo mostro con un'equazione ridotta: [math]

La soluzione dell'omogenea [math] è [math].
Considera ora la "prima" equazione particolare, [math]; provando[math] si trova [math].
Guardando solo il secondo pezzo, [math], una sua soluzione particolare è [math].

Dunque la soluzione generale è data da

[math]

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

[math]
[math]

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


Un'altra osservazione interessante: non è un caso che nel punto 3), la formula per [math] sia un polinomio. Infatti, nascosta sotto al tappeto c'è lo stesso principio di "se non funziona un esponenziale [math], prova con [math] ecc; solo che la base è $k=1$, (radice dell'equazione omogenea associata [math], che di per se una ricorrenza stupida), quindi non si nota la presenza dell'esponenziale.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Fede:)
Messaggi: 6
Iscritto il: 15 mar 2020, 11:51

Re: Formule chiuse successioni per ricorrenza

Messaggio da Fede:) »

Grazie!
Rispondi