proszę o rozwiązanie anna: oblicz n =3 wyrazu ciągu opisanego rekurecyjnie

⎧	f0 = −1
⎩	fn=−3fn−1 + 1

anna: czy ten zapis to jest

⎧	a1 = −1
⎩	an = −3an−1 + 1

wredulus_pospolitus: a₃ = −3a₂ + 1 = −3(−3a₁ + 1) + 1 = −3(−3(−3a₀+1) +1) + 1 = −3(−3(−3*(−1) + 1)+1)+1 = ...

anna: dziękuję

anna: oblicz n=4 wyrazu ciągu rekurencyjnie

⎧	a0= 3
⎩	an = 3*an−1 + 4

a₄ = 3*a₃ +4= 3*(3a₂ +4)+4 = 3*(3*(3a₁ +4)+4)+4 = 3*(3*(3*(3a₀ +4)+4)+4)+4= = 3*(3*(3*(3*4 +4)+4)+4)+4 = 3*(3*(3*16+4)+4 )+4) = 3*(3*52+4 ) +4 = = 3*160 +4 = 484 proszę o sprawdzenie czy to jest dobrze

Mila: 1) Ja liczę po kolei. a₁=3a₀+4=3*3+4=13 a₂=3a₁+4=3*13+4=39+4=43 a₃=3a₂+4=3*43+4=133 a₄=3a₃+4=3*133+4=403 2) Mogłaś liczyć tak: a₄=3a₃+4=3*(3*a₂+4)+4=9a₂+12+4=9a₂+16= =9(3a₁+4)+16=27a₁+36+16=27a₁+52=27(3a₀+4)+52=81a₀+108+52= =81*3+108+52==243+108+52=403 3) Mogłaś ustalić wzór jawny ciągu, o ile to już miałaś na wykładzie.

anna: dziękuję

Mariusz: Co do wzoru ogólnego to ja proponuję funkcję tworzącą albo przekształcenie Z A(x)=∑_n=0^∞a_nxⁿ Pierwszym wyrazem ciągu jest a₀ więc definiując funkcję tworzącą zaczynamy indeksować szereg od zera ∑_n=1^∞a_nxⁿ=∑_n=1^∞3a_n−1xⁿ+∑_n=1^∞4xⁿ Tutaj rekurencja zachodzi dla n≥1 więc wstawiając funkcję tworzącą do równania zaczynamy indeksować szereg od n=1 ∑_n=1^∞a_nxⁿ=∑_n=1^∞3a_n−1xⁿ+∑_n=1^∞4xⁿ

	4x
∑n=1∞anxn=3x(∑n=1∞an−1xn−1)+
	1−x

	4x
∑n=1∞anxn=3x(∑n=0∞anxn)+
	1−x

	4x
∑n=0∞anxn−3=3x(∑n=0∞anxn)+
	1−x

	4x
(∑n=0∞anxn)−3x(∑n=0∞anxn)=3+
	1−x

	4x
(1−3x)(∑n=0∞anxn) = 3+
	1−x

	3		4x
∑n=0∞anxn =		+
	1−3x		(1−3x)(1−x)

	3		(1−x)−(1−3x)
A(x) =		+2
	1−3x		(1−3x)(1−x)

	3		2		2
A(x) =		+		−
	1−3x		1−3x		(1−x)

	5		2
A(x) =		−
	1−3x		1−x

A(x) = 5(∑_n=0^∞3ⁿxⁿ)−2(∑_n=0^∞xⁿ) A(x) = ∑_n=0^∞((5*3ⁿ−2)xⁿ) a_n=5*3ⁿ−2

Aruseq: Mógłbyś wyjasnic skąd taki sposób rozwiązania? Albo podesłać link, gdzie jest wytłumaczone czemu tak robimy i jakie są kolejne kroki?

Mariusz: To są funkcje tworzące Definiujemy sobie funkcję której współczynniki rozwinięcia w szereg potęgowy są wyrazami danego ciągu a następnie po wstawieniu tego szeregu do równania rekurencyjnego rozwiązujemy równanie aby dostać tę funkcję tworzącą Po otrzymaniu funkcji tworzącej rozwijamy ją w szereg potęgowy Dla równania rekurencyjnego liniowego o stałych współczynnikach będzie to suma szeregów geometrycznych lub ich pochodnych Ale funkcjami tworzącymi można rozwiązywać także inne równania np równanie na liczby Catalana czy równania liniowe o zmiennych współczynnikach Aby rozwinąć funkcje tworzące w szereg czasami trzeba obliczyć n. pochodną Czasami zastosowanie funkcji tworzącej prowadzi do równania różniczkowego

chichi: równanie charakterystyczne równania jednorodnego: xⁿ = 3xⁿ⁻¹ / : xⁿ⁻¹ ⇔ x = 3 a_n⁽¹⁾ = c3ⁿ, a_n⁽²⁾ = A (bo f(n) − jest stopnia 0), zatem: A = 3A + 4 ⇔ A = −2, stąd mamy wzór: a_n = a_n⁽¹⁾ + a_n⁽²⁾ = c3ⁿ − 2, korzystając teraz z warunku początkowego mamy, że: 3 = c3⁰ − 2 ⇔ c = 5, zatem ostatecznie: a_n = 5*3ⁿ − 2

Mariusz: Ja tam wolę funkcje tworzące nie trzeba zgadywać i więcej równań można nimi rozwiązać

chichi: @Mariusz ja o tym wiem, ale tutaj dużo nie trzeba zgadywać, to jest tzw. metoda przewidywań mamy specjalne tabelki i po prostu dopasowujemy, tak samo jak w przypadku równań różniczkowych niejednorodnych, ja wolę tym sposobem, bo tego Twojego sposobu to szczerze powiedziawszy jeszcze nie poznałem , aczkolwiek mam go teraz w sylabusie na przedmiocie matematyka dyskretna, akurat przerabiamy ten temat i napisałem rozw. z użyciem wiedzy z ostatniego wykładu i ćwiczeń

Mariusz: Tak, jeżeli tak na to spojrzeć to i tak jest tu dość dużo zapamiętywania bez uzasadnienia a w przypadku funkcji tworzącej to definiujemy sobie funkcję której współczynniki rozwinięcia w szereg potęgowy są wyrazami danego ciągu , wstawiamy funkcję tworzącą do równania rekurencyjnego i równanie samo się rozwiązuje W przypadku równania liniowego o stałych współczynnikach dostajemy sumę szeregów geometrycznych lub ich pochodnych Czasem aby wydobyć współczynniki trzeba policzyć n. pochodną funkcji tworzącej Jeżeli chcemy rozwiązać równanie na liczby Catalana to korzystamy z funkcji tworzącej splotu a następnie otrzymujemy równanie kwadratowe na funkcję tworzącą ale tylko jedno rozwiązanie tego równania będzie pasować Ostatecznie rozwijamy funkcję tworzącą w szereg korzystając z uogólnionego dwumianu Newtona Czasami zastosowanie funkcji tworzącej prowadzi do równania różniczkowego Tak się dzieje gdy np zastosujemy zwykłą funkcję tworzącą do równania liniowego o zmiennych współczynnikach albo gdy zastosujemy wykładniczą funkcję tworzącą do równania liniowego o stałych współczynnikach Mamy kilka funkcji tworzących ale do rozwiązywania równań rekurencyjnych stosujemy głównie zwykłą funkcję tworzącą bądź wykładniczą funkcję tworzącą Jeżeli chodzi o przedział zbieżności to zwykle się nim tutaj nie zajmujemy choć funkcja tworząca powinna być na jakimś przedziale zbieżna Wykładniczą funkcję tworzącą stosuje się właśnie między innymi tam gdzie zwykła funkcja tworząca nie jest zbieżna Czasami zastosowanie wykładniczej funkcji tworzącej pozwala uniknąć równania różniczkowego Funkcję tworzącą można też wykorzystać do liczenia pewnych sum np suma sinusów czy suma cosinusów Wiemy że funkcja tworząca dla cosinusa to

	1
Re(		)
	1−eitx

a dla sinusa to

	1
Im(		)
	1−eitx

Funkcja tworząca ciągu sum częściowych to

	1
S(x)=		A(x)
	1−x

Zwykła funkcja tworząca dla ciągu a_n wygląda następująco A(x)=∑_n=0^∞a_nxⁿ przy czym zakładamy tutaj że pierwszym wyrazem ciągu jest a₀ Wykładnicza funkcja tworząca dla ciągu a_n wygląda następująco

	an
A(x)=∑n=0∞		xn
	n!

przy czym zakładamy tutaj że pierwszym wyrazem ciągu jest a₀

Mariusz: http://fizyka.umk.pl/~gniewko/didaktiki/MD2013-2014/wyk%C5%82ad3.pdf Mój brat miał z tym kolesiem zajęcia jednak przez ten covid mu funkcje tworzące wycięli Miał za to na innym przedmiocie przekształcenie Z więc aż tak dużo nie stracił Osobiście funkcje tworzące nieco lepiej mi pasują niż przekształcenie Z chichi a przekształcenie Z miałeś ? Z(a_n) = ∑_n=−∞^∞a_nz⁻ⁿ Jeżeli chcemy rozwiązywać równania rekurencyjne to można przyjąć że wyrazy o ujemnych indeksach są równe zero Jeżeli chodzi o odwracanie przekształcenia Z to tutaj metoda residuów jest wygodniejsza w użyciu niż rozkład na sumę ułamków prostych

Mila: Ja też wolę jak chichi Inny sposób: a₀= 3  , a₁=13 a_n = 3*a_n−1 + 4 a_n+1=3a_n+4 ================ (−) a_n+1−a_n=3a_n−3a_n−1 a_n+1−4a_n+3a_n−1=0 r. charakterystyczne: x²−4x+3=0 x=1 lub x=3 a_n=A+B*3ⁿ 3=A+B 13=A+3B ======== A=−2, B=5 a_n=5*3ⁿ−2 a₄=5*3⁴−2=403 =============

Mariusz: No to już chichi napisał

chichi: @Mariusz "chichi a przekształcenie Z miałeś ?" niestety jeszcze też nie miałem, ale jak coś się pojawi i wytworzę sobie jakąś opinię, to dam Ci znać. A brat co studiuje jeśli można wiedzieć, że ma taki przedmiot. Ale wydaje mi się, że te przedmioty są realizowane jedynie na kierunkach matematycznych i informatycznych

Mariusz: Teraz informatykę stosowaną na wydziale Fizyki UMK

chichi: czyli tak jak myślałem P.S. w tym wykładzie totalnie brakuje mi dowodów, bardziej mi to przypomina zapis z ćwiczeń

Mariusz: bo to są tylko slajdy Brat przesyłał mi video z wykładów (to było jeszcze z czasów zdalnego) i tam miał dowody tyle że akurat temat o funkcjach tworzących wycięli Teraz z takich przedmiotów matematycznych to ma metody numeryczne Do programowania przydają się głównie cztery działy matematyki Logika (konstruowanie i upraszczanie instrukcji warunkowych i iteracyjnych) Algebra liniowa z geometrią (np do grafiki) Analiza matematyczna (np oszacowanie złożoności algorytmu ) Matematyka dyskretna (o tutaj mamy i rekurencje i grafy)

Mariusz: chichi wspomniałeś równania różniczkowe Jeżeli chodzi o liniowe równania rekurencyjne to można je rozwiązywać w podobny sposób tj Równanie jednorodne przekształcić w układ równań − w przypadku równań różniczkowych liczyliśmy eksponentę macierzy x = e^Atx₀ a tutaj liczymy potęgę macierzy x = Aⁿx₀ Przydatne mogą być tutaj pewne rozkłady macierzy jak diagonalizacja czy rozkład Jordana Rozwiązanie szczególne równania niejednorodnego znajdujemy uzmienniając stałe tyle że zamiast wrońskianu mamy casoratian a zamiast całkować sumujemy Podobny zakres stosowania co przewidywania tyle że nie trzeba zapamiętywać tych przewidywań ani korzystać z tabelki

chichi: miałem na myśli równania różniczkowe wyższych rzędów rozwiązywane metodą przewidywań

Aruseq: Z jak zrobić to zadanie takim sposobem, jakim Mila to zrobił*, jeśli na przykład wyraz n+1 jest uzależniony od wyrazu n−tego, ale podniesionego do kwadratu? Na przykład: a_n+1 = a_n² +

	1
		? Miałem przy tego typu przykładzie wyliczyc granice, wiec chyba najprościej najpierw
	4

wyznaczyć wzór tego ciągu, chyba ze istnieje szybszy sposób?

Maciess: To wtedy nie jest rekurencja liniowa i takim spobem nie pójdzie.

Aruseq: To jak wtedy wyznaczyć wzór ciągu? Albo samą granice?

Maciess: No przede wszystkim to będzie zależało od warunku początkowego, którego nie podałeś. Bo np dla a₀=+− 1/2 to mamy ciąg (od pewnego miejsca) stały i granice od razu widać. Jak ogólnie dla a₀= c? Hmm na razie nie wiem, trzeba pomyśleć

Maciess: Nie wiem czy dobrze myśle ale twoj przyklad to tak. Założmy że ciąg a_n jest zbieżny i jego granica wynosi g. Jeśli a_n −> g to również a_n+1−>g. Jeśli a_n −>g to (a_n)² −> g². Mamy g=g²+1/4 ... g=1/2 Więc, o ile granica ma istnieć to będzie wynosić 1/2. Pytanie czy wartości a₀, które podalem wczesniej, to jedyne dla ktorych ciąg jest zbieżny

Aruseq: Podane jest a₀=0

Mariusz: Jeżeli chodzi o tę granicę to lepiej byłoby ją policzyć bez wyznaczania wzoru tego ciągu

	1
Przy wyznaczaniu wzoru jawnego problemem jest ta
	4

a podstawienia które nie pozwoliłoby wyrugować ten wyraz nie za bardzo widać

chichi: na następnych zajęciach za tydzień będę miał nieliniowe równania rekurencyjne, wtedy wrócę do tego wątku i postaram się wyznaczyć wzór jawny

Maciess: Do 11:25. Ciąg a_n jest rosnący dla wszystkich wyborów a₀ z wyjątkiem a₀ = +−1/2 (łatwo pokazać) Jeśli a_n∊(−1/2 , 1/2) to a_n+1 < 1/2 (łatwo pokazac). Jeśli a_n∊ R\<−1/2 , 1/2> to a_n+1 > 1/2. Wniosek? Ciąg zbieżny do 1/2 dla a₀∊<−1/2, 1/2>