Ciag zadany rekurencyjnie, pokazac, ze... :)

[Tomasz Rużycki]

Rozwazamy ciag zdefiniowany rekurencyjnie:

\(\displaystyle{ \begin{cases} a_0 = 3 \\ a_1 = 0 \\ a_2 = 2 \\ a_n = a_{n-2} + a_{n-3}\end{cases}}\)

Pokazac, ze jesli \(\displaystyle{ p}\) jest liczba pierwsza, to \(\displaystyle{ p|a_p}\).

Dosc ciekawe zadanie, chetnie zobacze jakies ciekawe rozwiazania.

[Marcin88]

Powinno być chyba dobrze:
Zauważamy na początku, że:
\(\displaystyle{ a_n=\epsilon_1^n+\epsilon_2^n+\epsilon_3^n}\)
gdzie epsilony to różne pierwiastki wielomianu:
\(\displaystyle{ x^3-x-1=0}\)
(pomijam prosty dowód indukcyjny).
Zauważmy teraz, że:
\(\displaystyle{ a_p=\epsilon_1^p+\epsilon_2^p+\epsilon_3^p=\epsilon_1^p+\epsilon_2^p+\epsilon_3^p-(\epsilon_1+\epsilon_2+\epsilon_3)^p=-\sum\limits_{0< k+l< p}^{}{p\choose k+l}{k+l \choose k}\epsilon_1^k \epsilon_2^l \epsilon_3^{p-k-l}}\)
Pozostaje teraz zauważyć, że:
\(\displaystyle{ p|{p\choose k+l}}\) (znana własność)
oraz że dla każdej trójki naturalnych liczb u, v, w, mamy (sumowanie odbywa się po wszystkich, zazwyczaj sześciu, permutacjach):
\(\displaystyle{ \sum\epsilon_1^u \epsilon_2^v \epsilon_3^w\in \mathbb{Z}}\)
Istotnie, ponieważ ze wzorów Viete'a: \(\displaystyle{ \epsilon_1\epsilon_2\epsilon_3=1}\) zatem trzeba tylko udowodnić, że:
\(\displaystyle{ \sum\epsilon_1^{u'} \epsilon_2^{v'} \epsilon_3^0\in \mathbb{Z}}\)
ale to już jest prawda, bo:
\(\displaystyle{ \sum\epsilon_1^{u'} \epsilon_2^{v'} \epsilon_3^0=(\epsilon_1^{u'}+\epsilon_2^{u'}+\epsilon_3^{u'})(\epsilon_1^{v'}+\epsilon_2^{v'}+\epsilon_3^{v'})-(\epsilon_1^{u'+v'}+\epsilon_2^{u'+v'}+\epsilon_3^{u'+v'})=a_{u'}a_{v'}-a_{u'+v'}\in \mathbb{Z}}\)
co kończy dowód.

[arek1357]

bardzo ładne rozwiązanie ale za nic nie mogę zrozumieć

tego przejścia pierwszego:

\(\displaystyle{ a_{p}=e_{1}^{p}+...=e_{1}^{p}+...-(e_{1}+...)^{p}}\)

[palazi]

Ze wzorów Viete'a tamten powyzszy wielomian ma współczynnik równy zero przy "x^2" a więc suma wszystich jego pierwiastków wnosi zero...
btw. sam dowód jest pierwsza klasa i b. mi sie podoba gratsy

[arek1357]

NNo tak że też to przeoczyłem hihi dobre!!!

[Tomasz Rużycki]

Ladny, ladny, dokladnie taki dowod zostal przedstawiony na cwiczeniach.

[TomciO]

Po uzyskaniu jawnej postaci \(\displaystyle{ a_n}\) zadanie mozna zakonczyc natychmiast jezeli sie wykorzysta:
-fakt, ze liczby algebraiczne calkowite tworza pierscien
-fakt, ze liczba wymierna jest algebraiczna calkowita wtedy i tylko wtedy gdy jest calkowita
-fakt, ze w takim pierscieniu zachodzi kongruencja \(\displaystyle{ (x+y)^p \equiv x^p + y^p \mod{p}}\) dla kazdej pierwszej \(\displaystyle{ p}\) (i ze w ogole mozna normalnie rozpatrywac kongruencje ale to tez nietrudno stwierdzic).

(liczba calkowita algebraiczna to taka, ktora jest pierwiastkiem wielomianu o wspolczynnikach calkowitych ze wspolczynnikiem przy najwyzszej potedze rownym 1). O ile dowod pierwszego faktu jest troche techniczny to juz pozostale 2 sa dosyc proste do dowiedzenia.

[Kostek]

ja mam pytanie:
Jak znalezc wzor ogolny takiego ciagu rekurencyjnego??
porobowalem Z-transformacja ale cos mi nie wychodzi;/

[TomciO]

Wiadomo, ze taki ciag na pewno bedzie mial postac \(\displaystyle{ \alpha (\epsilon_1)^n + \beta (\epsilon_2)^n + \gamma (\epsilon_3)^n}\) (bo epsilony sa pierwiastkami rownania charakterystycznego dla tego ciagu). Cala sprawa tkwi wiec w tym, zeby tak dobrac \(\displaystyle{ \alpha, \beta, \gamma}\) zeby zgadzalo sie dla pierwszych wyrazow - no i to jest akurat dosc nasuwajacy sie pomysl, ze \(\displaystyle{ \alpha=\beta=\gamma=1}\). A zweryfikowac to wiadomo jak - za pomoca wzorow Viete'a.