wzór na n-ty wyraz ciągu,funkcje tworzące

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
wronek
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 27 sty 2021, o 15:05
Płeć: Kobieta
wiek: 25

wzór na n-ty wyraz ciągu,funkcje tworzące

Post autor: wronek »

Znaleść przy użyciu funkcji tworzących jawny wzór na \(\displaystyle{ n}\)-ty wyraz ciągu:
\(\displaystyle{ b_1=3, b_2=1, b_{n+2}=6b_{n+1}-9b_n}\)
Ostatnio zmieniony 19 maja 2021, o 21:35 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z https://matematyka.pl/viewtopic.php?t=178502 .
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Re: wzór na n-ty wyraz ciągu,funkcje tworzące

Post autor: Mariusz M »

Ciąg jest indeksowany od jedynki więc wygodniej będzie zdefiniować funkcję tworzącą jako szereg
w którym wyrazy także są indeksowane od jedynki zatem

\(\displaystyle{ B\left( x\right)= \sum_{n=1}^{ \infty }b_{n}x^{n} }\)

Ponieważ rekurencja zachodzi dla \(\displaystyle{ n \ge 1}\)
to wstawiając szereg do równania indeksujemy wyrazy tego szeregu począwszy od jedynki

\(\displaystyle{ \sum_{n=1}^{ \infty }b_{n+2}x^n= \sum_{n=1}^{ \infty }6b_{n+1}x^n+ \sum_{n=1}^{ \infty }\left( -9b_{n}x^n\right) }\)

Teraz przesuwamy wyrazy szeregu aby indeksy współczynników wyrazów szeregu były równy wykładnikom zmiennej \(\displaystyle{ x}\)

\(\displaystyle{ \frac{1}{x^2}\left( \sum_{n=1}^{ \infty }b_{n+2}x^{n+2}\right)=\frac{6}{x}\left( \sum_{n=1}^{ \infty }b_{n+1}x^{n+1}\right)- 9\left(\sum_{n=1}^{ \infty }b_{n}x^n\right) \\
\sum_{n=1}^{ \infty }b_{n+2}x^{n+2}=6x\left( \sum_{n=1}^{ \infty }b_{n+1}x^{n+1}\right)-9x^2\left(\sum_{n=1}^{ \infty }b_{n}x^n\right) \\
}\)


Teraz chcemy aby pierwszym wyrazem szeregów był \(\displaystyle{ b_{1}x}\) więc po dodaniu początkowych wyrazów do tych szeregów
musimy je później odjąć

\(\displaystyle{ \sum_{n=1}^{ \infty }b_{n}x^{n}-3x-x^2=6x\left(\sum_{n=1}^{ \infty }b_{n}x^n-3x\right)-9x^2\left(\sum_{n=1}^{ \infty }b_{n}x^n\right)\\
\sum_{n=1}^{ \infty }b_{n}x^{n}=6x\left( \sum_{n=1}^{ \infty }b_{n}x^n\right)-9x^2\left(\sum_{n=1}^{ \infty }b_{n}x^n\right) -17x^2+3x\\
B\left( x\right)\left( 1-6x+9x^2\right) =-17x^2+3x\\
B\left( x\right)=\frac{-17x^2+3x}{\left( 1-3x\right)^2}\\
}\)


Zauważmy że

\(\displaystyle{ \sum_{n=1}^{ \infty }3^nx^n = \frac{3x}{1-3x} }\)

po zróżniczkowaniu stronami otrzymamy

\(\displaystyle{ \frac{\mbox{d}}{\mbox{d}x} \left(\sum_{n=1}^{ \infty }3^nx^n\right) =\frac{\mbox{d}}{\mbox{d}x}\left( \frac{3x}{1-3x}\right)\\
\sum_{n=1}^{ \infty }n \cdot 3^nx^{n-1}=\frac{3 \cdot \left( 1-3x\right) -\left( -3\right) \cdot 3x }{\left( 1-3x\right)^2 }\\
\sum_{n=1}^{ \infty }n \cdot 3^nx^{n-1}=\frac{3-9x+9x}{\left( 1-3x\right)^2}\\
\sum_{n=1}^{ \infty }n \cdot 3^nx^{n-1}=\frac{3}{\left( 1-3x\right)^2}\\
\sum_{n=1}^{ \infty }n \cdot 3^nx^{n}=\frac{3x}{\left( 1-3x\right)^2}\\
}\)


Stąd pomysł na jaką sumę rozłożyć funkcję tworzącą

\(\displaystyle{ \frac{-17x^2+3x}{\left( 1-3x\right)^2 }=\frac{3Ax}{1-3x}+\frac{3Bx}{\left( 1-3x\right)^2 }\\
-17x^2+3x=3Ax\left(1-3x\right)+3Bx\\
-17x+3=3A\left(1-3x\right)+3B\\
-17x+3=-9Ax+\left( 3A+3B\right)\\
\begin{cases}-9A=-17\\3A+3B=3\end{cases} \\
\begin{cases}A=\frac{17}{9}\\A+B=1\end{cases} \\
\begin{cases}A=\frac{17}{9}\\B=-\frac{8}{9}\end{cases} \\
}\)


Funkcję tworzącą można zatem zapisać w postaci sumy

\(\displaystyle{ B\left( x\right)= \frac{17}{9} \cdot \frac{3x}{1-3x}- \frac{8}{9} \cdot \frac{3x}{\left( 1-3x\right)^2 } }\)

Rozwińmy teraz funkcję tworzącą w szereg

\(\displaystyle{ B\left( x\right)= \frac{17}{9} \cdot \left( \sum_{n=1}^{ \infty }3^nx^n \right) - \frac{8}{9} \cdot \left( \sum_{n=1}^{ \infty }n \cdot 3^nx^n \right) \\
B\left( x\right)= \sum_{n=1}^{ \infty }\left( \left(\frac{1}{9}\left( 17-8n\right) \cdot 3^n \right)x^n \right) }\)


zatem wzór jawny tego ciągu to

\(\displaystyle{ b_{n}=\frac{1}{9}\left( 17-8n\right) \cdot 3^n}\)
ODPOWIEDZ