Domino in scatola

[FrancescoVeneziano]

Quello che intendevo è:
Trovi la ricorrenza, che per mia comodità adesso riscrivo come
$$C_{n+2}=2C_{n+1}+C_n+4\sum_{i=0}^{n} C_i,$$ che vale per ogni $n\geq 0$.
Definisci la funzione generatrice $$C(x)=\sum_{n\geq 0} C_n x^n.$$

Prendi la tua ricorrenza, la moltiplichi per $x^n$, e sommi su tutti gli n ottenendo
$\sum_{n\geq 0} C_{n+2} x^n=2\sum_{n\geq 0} C_{n+1} x^n+\sum_{n\geq 0} C_n x^n+4\sum_{n\geq 0} \sum_{i=0}^n C_i x^n$
Adesso osservi che
$\sum_{n\geq 0} C_{n+1} x^n = \frac{C(x)-1}{x}$
$\sum_{n\geq 0} C_{n+2} x^n = \frac{C(x)-1-2x}{x^2}$
$\sum_{n\geq 0} \sum_{i=0}^n C_i x^n = \frac{C(x)}{1-x}$
e quindi sostituendo nella relazione di prima ottieni
$$\frac{C(x)-1-2x}{x^2}=2 \frac{C(x)-1}{x} + C(x) + 4 \frac{C(x)}{1-x}.$$
Risolvi per $C(x)$ ed hai
$$C(x)=\frac{1-x}{x^3-3x^2-3x+1}=\frac{1-x}{(x+1)(x^2-4x+1)}.$$

Se chiami $\alpha_\pm=2\pm\sqrt{3}$ le due radici di $x^2-4x+1$, espandendo in frazioni parziali hai che
$$C(x)=\frac{\alpha_+}{6(1-\alpha_+ x)}+\frac{\alpha_-}{6(1-\alpha_- x)}+\frac{1}{3(1+x)}$$
e quindi, espandendo le tre serie geometriche sulla destra e confrontando con la definizione di $C(x)$,
$$C_n=\frac{\alpha_+^{n+1}+\alpha_-^{n+1}+2(-1)^n}{6}\sim \frac{\alpha_+^{n+1}}{6}.$$

Questo metodo è completamente automatico, trova e dimostra la formula chiusa, e non richiede grossi salti di immaginazione.

Chi vuole saperne di più può cercare Generatingfunctionology (lo trovate gratis e legalmente su internet) e studiarsi i primi capitoli.

[stergiosss]

Se vuoi una trattazione più completa, incluso cosa succede quando ci sono radici ripetute, guardati la lezione C3 del senior di un anno qualunque, il primo pezzo è sempre sulle successioni per ricorrenza.

Grazie, ma dove le posso trovare le lezioni del senior?

Questo metodo è completamente automatico, trova e dimostra la formula chiusa, e non richiede grossi salti di immaginazione.

Chi vuole saperne di più può cercare Generatingfunctionology (lo trovate gratis e legalmente su internet) e studiarsi i primi capitoli.

E grazie anche a te l'ho scaricato e ora provo a dargli un'occhiata.

Anche se nella tua spiegazione non mi è chiaro questo passaggio

$\sum_{n\geq 0} \sum_{i=0}^n C_i x^n = \frac{C(x)}{1-x}$

ma fa niente, penso di aver capito il ragionamento.


Grazie a entrambi per l'aiuto

[fph]

Grazie, ma dove le posso trovare le lezioni del senior?

http://olimpiadi.dm.unibo.it/videoLezio ... r=Training

BTW, perdona, mi sono sbagliato, intendevo A3, non C3 (che non esiste). Vado a rieditare il vecchio messaggio per i posteri...

[FrancescoVeneziano]

Lo vedi se espandi la serie geometrica di $1/(1-x)$ e svolgi il prodotto tra le serie
$$C(x)\frac{1}{1-x}=(1+2x+C_2x^2+C_3x^3+\cdots)(1+x+x^2+x^3+\cdots)=1+(1+2)x+(1+2+C_2)x^2+\cdots$$

[stergiosss]

Grazie, ma dove le posso trovare le lezioni del senior?

http://olimpiadi.dm.unibo.it/videoLezio ... r=Training

BTW, perdona, mi sono sbagliato, intendevo A3, non C3 (che non esiste). Vado a rieditare il vecchio messaggio per i posteri...

Gentilissimo grazie (lo ribadisco, questo smile mi fa schifo )

Grazie a entrambi per il materiale linkato, sto trovando molto interessante Generatingfunctionology e i video


Ora che ho appreso qualche nuova tecnica sono dell'idea che il metodo più "comodo" di risolvere questo problema fosse:
1) Trovare la ricorrenza per $C(n)$ come ho fatto nel primo post
2) Applicare il "trucco" suggerito da fph per trovare $S_n = 3S_{n-1}+3S_{n-2}-S_{n-3}$
3) Risolvere questa successione, e di conseguenza la $C(n)$, con le funzioni generatrici