Successioni definite per ricorrenza e funzioni generatrici

[psion_metacreativo]

Vista la curiosità sviluppata in questo topic a proposito delle funzioni generatrici ecco un esercizio apposito (come sempre credo si possa risolvere in 1000 modi ma è fatto apposta affinchè i conti tornino con le funzioni generatrici che magari in altre situazioni sono macchinose):

Calcolare $ \displaystyle \sum^{k}_{n=0}a_{n} $

dove $ a_{n} $ è la successione definita nel seguente modo:

$ \displaystyle\begin{math}\left\{\begin{array}{l} a_{0}=1\\a_{1}=0\\a_{2}=-5\\a_{n}=4a_{n-1}-5a_{n-2}+2a_{n-3}\ \ \ \ \ \ \forall n\in\mathbb{N}: n\geq3 \end{array}\end{math} $

[karl]

Premetto alcune note formule, che sono (in un opportuno insieme di validita'):
$ \sum\limits_{n = 0}^\infty {nt^{n - 1} = } \sum\limits_{n = 0}^\infty {(n + 1)t^n ;} \sum\limits_{n = 0}^\infty {t^n = \frac{1}{{1 - t}};} \sum\limits_{n = 0}^\infty {nt^{n - 1} = \frac{1}{{(1 - t)^2 }};} $
Cio' posto,per comodita', nell'equazione proposta cambiamo n in n+3:
$ (1)\,\, a_{n + 3} = 4a_{n + 2} - 5a_{n + 1} + 2a_n $
e poniamo $ G(t) = \sum\limits_{n = 0}^\infty {a_n t^n } $ (funzione generatrice)
Moltiplicando la (1) per $ t^n $ e sommando su n da 0 a $ \infty $ risulta:
$ \sum\limits_{n = 0}^\infty {a_{n + 3}t^n } = 4\sum\limits_{n = 0}^\infty {a_{n + 2}t^n } - 5\sum\limits_{n = 0}^\infty {a_{n + 1}t^n } + 2\sum\limits_{n = 0}^\infty {a_n }t^n $
Ovvero:
$ \frac{{G - a_0 - a_1 t - a_2 t^2 }}{{t^3 }} = \frac{{4(G - a_0 - a_1 t)}}{{t^2 }} - \frac{{5(G - a_0 )}}{{t^{} }} + 2G $
da cui per le condizioni iniziali :
$ G(t) = \frac{{4t - 1}}{{2t^3 - 5t^2 + 4t - 1}} = \frac{3}{{(1 - t)^2 }} + \frac{2}{{1 - t}} - \frac{4}{{1 - 2t}} $
Vale a dire:
$ \sum\limits_{n = 0}^\infty {a_n t^n } = 3\sum\limits_{n = 0}^\infty {nt^{n - 1} } + 2\sum\limits_{n = 0}^\infty {t^n } - 4\sum\limits_{n = 0}^\infty {(2t)^n } $
E per la premessa fatta:
$ \sum\limits_{n = 0}^\infty {a_n t^n }=3\sum\limits_{n = 0}^\infty {(n + 1)t^n } + 2\sum\limits_{n = 0}^\infty {t^n } - 4\sum\limits_{n = 0}^\infty {(2t)^n } $
Ed in definitiva:
$ \sum\limits_{n = 0}^\infty {a_n t^n }=\sum\limits_{n = 0}^\infty {(5 + 3n - 2^{n + 2} )t^n } $
Per confronto si ricava che:
$ a_n = 5 + 3n - 2^{n + 2} $
e sommando su n da 0 a k:
$ \sum\limits_{n = 0}^k {a_n } = 5(k + 1) + \frac{{3k(k + 1)}}{2} - 4(2^{k + 1} - 1) $ che e' la somma richiesta.
Con il metodo dell'equazione caratteristica la soluzione e' assai piu' snella.
Una domanda :ma e' sicuro che argomenti di tal fatta siano materia da Olimpiadi ?

[psion_metacreativo]

Io credo che sia sempre utile saper trattare le successioni per ricorrenza e a questo punto posso svelare che la fonte dell'esercizio è il Larson una bibbia per tutti i problem solver.