Dzień dobry!
Podczas rozwiązywania równania rekurencyjnego metodą funkcji tworzących doszłam do momentu, w którym postać zwartą przedstawia się za pomocą sumy ułamków prostych. I nie bardzo wiem, co teraz zrobić. Czy otrzymana równość jest poprawna? Czy stopień wielomianów w liczniku i mianowniku może być równy?
\(\displaystyle{ G(x) = \frac{-5x^2+x}{1-x} \cdot \frac{1}{1-2x} = \frac{A}{1-x} + \frac{B}{1-2x}}\)
\(\displaystyle{ -5x^2 + x= A - 2Ax + B - Bx}\)
Na pewno jednym z równań będzie:
\(\displaystyle{ 1 = -2A-B.}\)
Jak wyliczyć pozostałe?-- 20 cze 2018, o 18:59 --PS. Równanie, które rozwiązuję to:
\(\displaystyle{ T(1) = 1}\)
\(\displaystyle{ T(n) = 2T(n-1) -4}\)
Rozwiązywanie równania rekurencyjnego metodą f. tworzących
-
- Użytkownik
- Posty: 5
- Rejestracja: 16 kwie 2018, o 19:01
- Płeć: Kobieta
- Lokalizacja: Katowice
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Rozwiązywanie równania rekurencyjnego metodą f. tworzący
\(\displaystyle{ \sum_{n=2}^{+\infty}T(n)x^n=2 \sum_{n=2}^{+\infty}T(n-1)x^n-4 \sum_{n=2}^{+\infty}x^n\\G(x)-xT(1)=2xG(x)- \frac{4x^2}{1-x}\\ G(x)(1-2x)=x-\frac{4x^2}{1-x}\\ G(x)= \frac{x}{1-2x}- \frac{4x^2}{(1-x)(1-2x)}\\}\)
Teraz (nie chce mi się rozwiązywać układów równań) zauważmy, że
\(\displaystyle{ x=(1-x)-(1-2x)\\ \frac{x}{(1-x)(1-2x)}= \frac{1-x-(1-2x)}{(1-x)(1-2x)} =\frac{1}{1-2x}-\frac{1}{1-x}\\ \frac{4x^2}{(1-x)(1-2x)}= \frac{4x}{1-2x}-\frac{4x}{1-x}}\)
i dalej już łatwo:
\(\displaystyle{ \frac{x}{1-2x}-\frac{4x}{1-2x}+\frac{4x}{1-x}=\frac{-3x}{1-2x}+\frac{4x}{1-x}=\\= \sum_{n=0}^{+\infty}-3x(2x)^n+ \sum_{n=0}^{+\infty}4x\cdot x^n=\\= \sum_{n=1}^{+\infty} \left(-3\cdot 2^{n-1}+4 \right) x^n}\)
czyli
\(\displaystyle{ T(n)=4-3\cdot 2^{n-1}}\)
Teraz (nie chce mi się rozwiązywać układów równań) zauważmy, że
\(\displaystyle{ x=(1-x)-(1-2x)\\ \frac{x}{(1-x)(1-2x)}= \frac{1-x-(1-2x)}{(1-x)(1-2x)} =\frac{1}{1-2x}-\frac{1}{1-x}\\ \frac{4x^2}{(1-x)(1-2x)}= \frac{4x}{1-2x}-\frac{4x}{1-x}}\)
i dalej już łatwo:
\(\displaystyle{ \frac{x}{1-2x}-\frac{4x}{1-2x}+\frac{4x}{1-x}=\frac{-3x}{1-2x}+\frac{4x}{1-x}=\\= \sum_{n=0}^{+\infty}-3x(2x)^n+ \sum_{n=0}^{+\infty}4x\cdot x^n=\\= \sum_{n=1}^{+\infty} \left(-3\cdot 2^{n-1}+4 \right) x^n}\)
czyli
\(\displaystyle{ T(n)=4-3\cdot 2^{n-1}}\)
-
- Użytkownik
- Posty: 5
- Rejestracja: 1 maja 2015, o 16:14
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
Rozwiązywanie równania rekurencyjnego metodą f. tworzących
Można prosić o rozwinięcie i wytłumaczenie tego?Premislav pisze: Teraz (nie chce mi się rozwiązywać układów równań) zauważmy, że
\(\displaystyle{ x=(1-x)-(1-2x)\\ \frac{x}{(1-x)(1-2x)}= \frac{1-x-(1-2x)}{(1-x)(1-2x)} =\frac{1}{1-2x}-\frac{1}{1-x}\\ \frac{4x^2}{(1-x)(1-2x)}= \frac{4x}{1-2x}-\frac{4x}{1-x}}\)
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Rozwiązywanie równania rekurencyjnego metodą f. tworzący
A co tu tłumaczyć? Po prostu zamiast wykonywać dzielenie wielomianów, skróciłem sobie robotę.
Chyba zgodzisz się, że prawdą jest
\(\displaystyle{ x=(1-x)-(1-2x)}\)
Wobec tego, jak napisałem, mamy
\(\displaystyle{ frac{x}{(1-x)(1-2x)}= frac{1-x-(1-2x)}{(1-x)(1-2x)} =frac{1}{1-2x}-frac{1}{1-x}}\)
Ta druga równość wynika z czegoś takiego:
\(\displaystyle{ frac{a-b}{ab}=frac{a}{ab}-frac{b}{ab}=frac 1 b-frac 1 a}\)
Tutaj \(\displaystyle{ a=1-x, b=1-2x}\).
No to jak się pomnoży stronami równość
\(\displaystyle{ frac{x}{(1-x)(1-2x)}= frac{1}{1-2x}-frac{1}{1-x}}\)
przez \(\displaystyle{ 4x}\) (oczywiście normalnie powinniśmy tam zakładać \(\displaystyle{ x
eq 0}\), żeby to zrobić, ale to jest akurat tuaj nieistotne),
to ujrzymy coś takiego:
\(\displaystyle{ frac{4xcdot x}{(1-x)(1-2x)}= frac{4x}{1-2x}-frac{4x}{1-x}}\)
czyli właśnie
\(\displaystyle{ frac{4x^2}{(1-x)(1-2x)}= frac{4x}{1-2x}-frac{4x}{1-x}}\)
Jak ktoś nie chce zgadywać rzeczy typu \(\displaystyle{ x=(1-x)-(1-2x)}\), no to najpierw trzeba podzielić z resztą wielomian (właściwie to jednomian) \(\displaystyle{ 4x^2}\) przez \(\displaystyle{ (1-x)(1-2x)}\), a potem zastosować rozkład na ułamki proste: 298450.htm
Chyba zgodzisz się, że prawdą jest
\(\displaystyle{ x=(1-x)-(1-2x)}\)
Wobec tego, jak napisałem, mamy
\(\displaystyle{ frac{x}{(1-x)(1-2x)}= frac{1-x-(1-2x)}{(1-x)(1-2x)} =frac{1}{1-2x}-frac{1}{1-x}}\)
Ta druga równość wynika z czegoś takiego:
\(\displaystyle{ frac{a-b}{ab}=frac{a}{ab}-frac{b}{ab}=frac 1 b-frac 1 a}\)
Tutaj \(\displaystyle{ a=1-x, b=1-2x}\).
No to jak się pomnoży stronami równość
\(\displaystyle{ frac{x}{(1-x)(1-2x)}= frac{1}{1-2x}-frac{1}{1-x}}\)
przez \(\displaystyle{ 4x}\) (oczywiście normalnie powinniśmy tam zakładać \(\displaystyle{ x
eq 0}\), żeby to zrobić, ale to jest akurat tuaj nieistotne),
to ujrzymy coś takiego:
\(\displaystyle{ frac{4xcdot x}{(1-x)(1-2x)}= frac{4x}{1-2x}-frac{4x}{1-x}}\)
czyli właśnie
\(\displaystyle{ frac{4x^2}{(1-x)(1-2x)}= frac{4x}{1-2x}-frac{4x}{1-x}}\)
Jak ktoś nie chce zgadywać rzeczy typu \(\displaystyle{ x=(1-x)-(1-2x)}\), no to najpierw trzeba podzielić z resztą wielomian (właściwie to jednomian) \(\displaystyle{ 4x^2}\) przez \(\displaystyle{ (1-x)(1-2x)}\), a potem zastosować rozkład na ułamki proste: 298450.htm