Równanie rekurencyjne Mariusz: Rozwiąż równanie rekurencyjne T_n=1 n=1 n−1 T_n=∑ T_k + n² n>1 k=1 Próbowałem rozwiązywać funkcjami tworzącymi ale dostałem podwójną sumę i nie jestem pewny jak zamienić tę podwójną sumę na iloczyn funkcji tworzących

vaultboy: Rozumiem, że T₁=1, bo trochę to dziwnie zapisałeś T_n=(T₁+T₂+T₃+...+T_n−1) + n² Przyjmijmy T₁+T₂+T₃+...+T_n−1=S_n−1 Wtedy S_n−S_n−1=T_n //chyba jasne Podstawiając do równania dostaję S_n−S_n−1=S_n−1+n² czyli S_n−2S_n−1=n² S₁=T₁=1 Znajdźmy wzór na S_n, wtedy dostaniemy wzór na T_n S_n−2S_n−1=n² S_n−1−2S_n−2=(n−1)² | *2 S_n−2−2S_n−3=(n−2)² | *2² S_n−3−2S_n−4=(n−3)² | *2³ ... S₂−2S₁=2² | *2ⁿ⁻² Po wykonaniu wszystkich tych operacji Sumujemy te równania Tam się wszystko skróci, bo mamy sumę teleskopowaną S_n−2ⁿS₁=n²+2(n−1)²+2²(n−2)²+...2ⁿ⁻²2² stąd S_n=n²+2(n−1)²+2²(n−2)²+...2ⁿ⁻²2² + 2ⁿ Trzeba by to jeszcze sprowadzić do czegoś normalnego S_n wynosi n−2 ∑ 2ⁱ(n−i)² + 2ⁿ i=0 Dalej myślę, że dasz rade

Mariusz: http://fotozrzut.pl/zdjecia/c6b7e36362.gif Ja próbowałem w ten sposób tylko nie jestem pewien czy dobrze przekształciłem podwójną sumę na iloczyn funkcji tworzących

Mariusz: 1. Chyba zrobiłeś literówkę S_n=∑2ⁱ(n−1)²+2ⁿ⁻¹ a ty masz S_n=∑2ⁱ(n−1)²+2ⁿ 2. Tę sumę trzeba jakoś policzyć 3. Co z metodą funkcji tworzących ? Chodzi mi głównie o zamianę podwójnej sumy na iloczyn funkcji tworzących

vaultboy: racja powinno być S_n=∑2ⁱ(n−i)²+2ⁿ⁻¹ zauważ, że ∑2ⁱ(n−i)²=∑2ⁱn²−∑2ⁱ(2ni)+∑2ⁱi²=n²∑2ⁱ−2n∑2ⁱi+∑2ⁱi²

Mariusz: To n można było wyciągnąć przed sumę Teraz można łatwo sumując przez części to policzyć

Mariusz: Po takim rozpisaniu trzeba trzech sumowań przez części a można tak zapisać tę sumę aby wystarczyły dwa sumowania przez części