Re: Domino in scatola
Inviato: 04 ott 2011, 16:50
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.
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.
l'ho scaricato e ora provo a dargli un'occhiata.
)