Podaj wzór jawny na S(n) i udowodnij indukcyjnie jego poprawność Monika: Podaj wzór jawny na S(n) i udowodnij indukcyjnie jego poprawność s(0) = 1, s(1) = 2 s(n) = 3 * s(n−2) dla n >= 2

kerajs:

	3+2√3		3−2√3
s(n)=		(√3)n+		(−√3)n
	6		6

Mariusz: A co z indukcją mądralo

Monika: Jak dojść do tej postaci? Z pomocą wielomianu charakterystycznego jest to możliwe?

kerajs: ''Monika: Jak dojść do tej postaci? Z pomocą wielomianu charakterystycznego jest to możliwe?'' Owszem. r³=3 ⇒ r₁=√3 ∨ r₂=−√3 S(n)=A(√3 )ⁿ+B(−√3 )ⁿ Współczynniki A, B dostajesz z warunków początkowych ''Mariusz: A co z indukcją mądralo'' To zbyt trywialne żeby sądzić, że Monika tego nie zrobi. Ale, skoro potrzebujesz, to zamieszczam clou dowodu:

	3+2√3		3−2√3
S(n)=		(√3 )n+		(−√3 )n=
	6		6

	3+2√3		3−2√3
=		*3*(√3 )n−2+		*3*(−√3 )n−2=
	6		6

	3+2√3		3−2√3
=3(		(√3 )n−2+		(−√3 )n−2)=3S(n−2)
	6		6

Mariusz: "Clou" dowodu Za bardzo byś się przepracował gdybyś napisał normalną odpowiedz No właśnie "clou" tego może być takie że tu są dwa warunki początkowe i samo założenie poprawności tylko dla n=k może nie wystarczyć do wykazania poprawności dla n=k+1 r³ = 3 taa mądralo "Jak dojść do tej postaci? Z pomocą wielomianu charakterystycznego jest to możliwe?" Tak, choć ja wolę funkcje tworzące bo nie dość że więcej równań nimi rozwiążesz to jeszcze są wygodniejsze w użyciu

kerajs: ''Mariusz: Za bardzo byś się przepracował gdybyś napisał normalną odpowiedz'' Dla mnie to normalna odpowiedź, skoro pokazuje jedyne problematyczne miejsce. Powody dla których nie zamieszczam pełnych i wyczerpujących rozwiązań podawałem wielokrotnie, lecz mogę to zrobić jeszcze raz. Obiektywne: − tu większość pytaczy nie jest zainteresowana odpowiedzią − ci nieliczni zainteresowani zawsze mogą dopytać lub poprosić o rozwinięcie podanych wskazówek − tu zadania tworzą wielki stos, więc poszukiwanie interesujących tematów jest problematyczne Subiektywne: − jestem leniwy − prymitywizm tutejszego edytora zniechęca mnie do pisania − a karykaturalny wygląd wyrażeń matematycznych drażni moje poczucie estetyki ''Mariusz: No właśnie "clou" tego może być takie że tu są dwa warunki początkowe i samo założenie poprawności tylko dla n=k może nie wystarczyć do wykazania poprawności dla n=k+1'' Lecz tu tak nie jest. To co napisałem powyżej jest dowodem dla n−ów o tej samej parzystości, a wyliczenie S(0) i S(1) , i porównanie ich z podanymi warunkami początkowymi udowadniają poprawność wzoru dla liczb naturalnych. ''Mariusz: r3 = 3 taa mądralo '' To literówka. Potwierdza fragment z dwoma pierwiastkami który pominąłeś. ''Mariusz: ja wolę funkcje tworzące bo nie dość że więcej równań nimi rozwiążesz to jeszcze są wygodniejsze w użyciu'' Nie mąć dziewczynie w głowie. Funkcje tworzące nie są wygodniejsze w użyciu.

Mariusz: "Clue" Jesteś jakieś 200 lat zacofany bo moda na francuszczyznę już minęła i nie musisz wtrącać tych słów do polszczyzny " Obiektywne: − tu większość pytaczy nie jest zainteresowana odpowiedzią − ci nieliczni zainteresowani zawsze mogą dopytać lub poprosić o rozwinięcie podanych wskazówek − tu zadania tworzą wielki stos, więc poszukiwanie interesujących tematów jest problematyczne Subiektywne: − jestem leniwy − prymitywizm tutejszego edytora zniechęca mnie do pisania − a karykaturalny wygląd wyrażeń matematycznych drażni moje poczucie estetyki " To po co w ogóle odpisujesz ? A jak cię blokują to narzekasz "Nie mąć dziewczynie w głowie. Funkcje tworzące nie są wygodniejsze w użyciu." No nie dość że są wygodniejsze to jeszcze więcej równań nimi rozwiąże np to że rozwiązaniem rekurencji liniowej jest funkcja wykładnicza ewentualne pomnożona przez czynnik wielomianowy wynika z tego że funkcja tworząca może być przedstawiona za pomocą szeregów geometrycznych i ich pochodnych Czynnik wielomianowy przy funkcji wykładniczej występuje wtedy gdy w rozkładzie funkcji tworzącej występują pochodne szeregów geometrycznych Funkcję tworzącą wystarczy wstawić do równania i rozwiązywać i nie trzeba ani zgadywać postaci rozwiązania ani oddzielnie rozpatrywać równania jednorodnego i niejednorodnego Twoja ulubiona metoda nie dość że jest bardziej ograniczona to jeszcze nie wiadomo skąd się bierze funkcja wykładnicza w rozwiązaniu, skąd się bierze czynnik wielomianowy przed funkcją wykładniczą ani nawet nie wiadomo dlaczego tak a nie inaczej należy zgadywać rozwiązanie szczególne równania niejednorodnego

Mariusz: s(0) = 1, s(1) = 2 s(n) = 3 * s(n−2) dla n >= 2 Zauważmy że pierwszym zdefiniowanym wyrazem ciągu jest wyraz o indeksie n=0 więc definiując funkcję tworzącą zaczynamy indeksować szereg od n=0 Funkcja tworząca to szereg potęgowy którego współczynnikami są wyrazy ciągu S(x)=∑_n=0^∞s_nxⁿ Zauważmy że rekurencja zachodzi dla n≥2 więc wstawiając funkcję tworzącą do równania rekurencyjnego zaczynamy indeksować szereg od n=2 ∑_n=2^∞s_nxⁿ=∑_n=2^∞3s_n−2xⁿ (∑_n=2^∞s_nxⁿ) = 3x²(∑_n=2^∞s_n−2xⁿ⁻²) (∑_n=2^∞s_nxⁿ) = 3x²(∑_n=0^∞s_nxⁿ) ∑_n=0^∞s_nxⁿ − 1 − 2x = 3x²(∑_n=0^∞s_nxⁿ) (1−3x²)(∑_n=0^∞s_nxⁿ )= 1+2x

	1+2x
∑n=0∞snxn =
	1−3x2

	1+2x
S(x) =
	1−3x2

Tutaj warto zauważyć że funkcja tworząca jest funkcją wymierną a mianownik nie posiada pierwiastków wielokrotnych więc nie wystąpią pochodne szeregów geometrycznych Rozkładamy funkcję tworzącą na sumę szeregów geometrycznych

1+2x		A		B
	=		+
1−3x2		1−√3x		1+√3x

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

	2
A−B =
	√3

A+B = 1

	2√3
A−B =
	3

	3+2√3
2A =
	3

	3−2√3
2B =
	3

	3+2√3		1		3−2√3		1
S(x) =		(		)+(		)(		)
	6		1−√3x		6		1+√3x

	3+2√3		3−2√3
S(x) =		(∑n=0∞(√3)nxn)+(		)(∑n=0∞(−√3)nxn)
	6		6

	3+2√3		3−2√3
S(x) =(∑n=0∞((		) (√3)n +(		)(−√3)n )xn)
	6		6

	3+2√3		3−2√3
sn = (		) (√3)n +(		)(−√3)n
	6		6

Jak widać nie dość że nie musimy zgadywać postaci rozwiązania , ani rozpatrywać oddzielnie równania jednorodnego i niejednorodnego to także stałe są obliczane już w trakcie rozwiązywania równania Mam jednak wątpliwości czy jeżeli przepisze to całe clou kerajsa to jej uznają ten dowód indukcyjny Co do indukcji to czy w pierwszym kroku powinniśmy sprawdzić dwie początkowe wartości Czy w drugim kroku (założenie indukcyjne) powinniśmy dać nierówność n ≤ k zamiast równości n = k i wtedy w trzecim kroku (kroku indukcyjnym) zastosować to całe clue kerajsa tylko z przesuniętymi indeksami

kerajs: Brawo! Po raz kolejny pokazałeś, że dzięki funkcji tworzącej dostanie się rozwiązanie kilka razy dłuższe niż z metody przewidywania. Teraz każdy widzi która z metod jest WYGODNIEJSZA i PROSTSZA . Nie będę komentował innych kwestii, gdyż najwyraźniej nie doczytałeś co o nich pisałem. Zaintrygował mnie inna rzecz. Napisałeś: ''A jak cię blokują to narzekasz ''. Wskaż choć jeden post w którym to robiłem.

Mariusz: Krótsza nie znaczy wygodniejsza ani nawet prostsza " Wskaż choć jeden post w którym to robiłem." Bardzo łatwo znaleźć kila takich wpisów o ile ich nie usunęli

Mariusz: "prymitywizm tutejszego edytora zniechęca mnie do pisania " Zgadza się edytor jest prymitywny ale Jakub nie zamierza nic z tym zrobić i w najbliższym czasie nic się nie zmieni

daras: Jakub już dawno zostawił to forum swojemu biegowi..

kerajs: Skoro tu nikt nie narzeka na edytor, a zaglądająca tu dzieciarnia go ogarnia, to mi nic do tego. ''Mariusz: Krótsza nie znaczy wygodniejsza ani nawet prostsza'' Fakt, nie znaczy, choć najczęściej tak jest, podobnie jak i w tym przypadku. Jest prostsza bo znacznie mniej trzeba umieć i pamiętać. Jest wygodniejsza gdyż wymaga znacznie mniej rachunków, które w dodatku są prostsze. I ogólnie jest lepsza gdyż jest szybsza i obarczona mniejszym prawdopodobieństwem zrobienia błędu. Jej jedyna wada to mniejsza uniwersalność, co i tak nie ma znaczenia skoro niemal wszystkie szkolne przykłady można nią rozwiązać. ''Mariusz: Twoja ulubiona metoda nie dość że jest bardziej ograniczona to jeszcze nie wiadomo skąd się bierze funkcja wykładnicza w rozwiązaniu'' A kogo obchodzi jak zbudowane jest narzędzie i jak działa skoro ważny jest tylko efekt jego działania i jak najprostsza obsługa? Dla przeciętnego studenta metoda przewidywania jest o niebo prostszym narzędziem niż funkcje tworzące. Sugeruję, abyś powstrzymał się przed twierdzeniami że coś lubię lub nie lubię, umiem lub nie umiem itp, gdyż nie tylko zwykle są nieprawdziwe, to jeszcze wprowadzasz postronnych czytelników w błąd. ''Mariusz: Bardzo łatwo znaleźć kila takich wpisów o ile ich nie usunęli'' Skoro to tak łatwe, to wskaż choć jeden w którym narzekam, że mnie zbanowano.