Rekurencja Pytający: Cześć, mam niedługo zaliczenie z pewnego przedmiotu na studiach i potrzebuję pomocy. Chodzi o rozwiązanie równania rekurencyjnego. Podam może jeden przykład: T(0) = 1 T(n) = 2T(n − 1) + 1 Czy ktoś mógłby pomóc rozwiązać?

ABC: Zgadnij wzór i udowodnij indukcyjnie , to klasyczna rekurencja

a7: ten przykład jest szczegółowo rozwiązany na youtubie https://www.youtube.com/watch?v=JvcqtZk2mng

bałwan: T(0) = 1 = 2¹ − 1 T(1) = 2*1 + 1 = 3 = 2² − 1 T(2) + 2*3 + 1 = 7 = 2³ − 1 T(3) = 2*7 + 1 = 15 = 2⁴ − 1 itd.

wredulus_pospolitus: albo T(0) = 1 = 2⁰ T(1) = 3 = 2¹ + 2⁰ T(2) = 7 = 2² + 2¹ + 2⁰ T(3) = 15 = 2³ + 2² + 2¹ + 2⁰ jedno i drugi oznacza dokładnie to samo ... ja po prostu zapisuję to w formie sumy skończonego ciągu geometrycznego (którego sumę przestawia przedmówca)

wredulus_pospolitus: w sumie to lepiej było by to zapisać: T(0) = 1 T(1) = 2 + 1 T(2) = 4 + 2 + 1 T(3) = 8 + 4 + 2 + 1 ... itd. ... i stąd przejść do 22:04 ... a następnie do 22:01 (jeżeli się tego od razu nie widzi)

Pytający: No dobrze. Mam rozpisane, co dalej? Przepraszam, że zadaję takie pytania, ale nie miałem jeszcze matematyki indukcyjnej a przedmiot muszę zaliczyć.

wredulus_pospolitus: a co właściwie masz zrobić w zadaniu

Pytający: Rozwiązać równanie. Nic więcej nie wiem.

wredulus_pospolitus: jakie równanie?

Pytający: Chyba to co podałem. Z tego co udało mi się zrozumieć na zajęciach to trzeba zrobić coś z tymi danymi co podałem w pierwszym poście, a potem wykorzystać to do napisania wzoru na sumę ciągu.

wredulus_pospolitus: 'zrobić coś' de facto masz WYZNACZYĆ WZÓR OGÓLNY na n'ty wyraz tego ciągu czyli T(n) = 2ⁿ − 1 a dochodzisz do tego jak wcześniej napisałem, czyli: 1) 22:06 2) 22:04 3) 22:01 4) za pomocą indukcji matematycznej (winna być w szkole średniej) udowadniasz, że wzór działa (co nie jest niczym trudnym)

Mila: I sposób 1) t(0)=1, t(1)=2t(0)+1=3 wg rekurencji t(1)=3 t(n)=2t(n−1)+1 t(n+1)=2t(n)+1 ====== odejmuję stronami t(n+1)−t(n)=2t(n)−2t(n−1) mamy równanie jednorodne ⇔ 2) t(n+1)−3t(n)+2t(n−1)=0 x²−3x+2=0 − r. charakterystyczne x=1 lub =2 t(n)=A*2ⁿ+B*1ⁿ − ogólna postać jawnego wzoru 2) korzystamy z war. początkowych t(0)=1=A*2⁰+B⇔ A+B=1 3=A*2¹+B⇔2A+B=3 ================ A+B=1 2A+B=3 −−−−−−−−− −A=−2 A=2 i B=−1 t(n)=2*2ⁿ−1 t(n)=2ⁿ⁺¹−1 ==========

ABC: w szkole średniej to indukcja była za mojej kadencji jako ucznia , teraz wypieprzyli z programu, ale trzeba się samemu dokształcać albo na douczanie matematyczne na uczelni chodzić, wiele kierunków to organizuje

wredulus_pospolitus: @ABC ... żeby nie skłamać ... za moich czasów indukcja była w 1 klasie średniej (może nawet 8 podstawówki). Jeszcze parę lat i nasz system nauczania będzie wypluwał młodzież nie umiejącą nawet dodawać

Min. Edukacji: Niektóre "umiejętności" są zbędne.

Pytający: Bardzo dziękuję za pomoc. Teraz już mniej więcej wiem jak podjeść do tego zadania (największy problem to zgadnąć ten wzór).

Mariusz: Niech T(x)=∑_n=0^∞t_nxⁿ ∑_n=1^∞t_nxⁿ=∑_n=1^∞2t_n−1xⁿ+∑_n=1^∞xⁿ

	x
∑n=1∞tnxn=2∑n=1∞tn−1xn+
	1−x

	x
∑n=1∞tnxn=2x(∑n=1∞tn−1xn−1)+
	1−x

	x
∑n=1∞tnxn=2x(∑n=0∞tnxn)+
	1−x

	x
∑n=0∞tnxn − 1=2x(∑n=0∞tnxn)+
	1−x

	x
T(x)(1−2x)=1+
	1−x

	1
T(x)(1−2x)=
	1−x

	1
T(x)=
	(1−2x)(1−x)

	2(1−x)−(1−2x)
T(x)=
	(1−2x)(1−x)

	2		1
T(x)=		−
	1−2x		1−x

T(x)=2(∑_n=0^∞2ⁿxⁿ)−(∑_n=0^∞xⁿ) T(x)=∑_n=0^∞(2*2ⁿ−1)xⁿ T_n = 2 * 2ⁿ − 1 Funkcje tworzące są wygodniejsze w użyciu i więcej równań można nimi rozwiązać