Liniowe równania rekurencyjne, wielonormowe w zal. od reszt

[Cutlass]

Witam, mam tutaj garść problemów związanych z rekurencją

1) Jakie jest rozwiązanie, zależne od \(\displaystyle{ n}\), poniższej rekurencji?
\(\displaystyle{ a_0=\sqrt{2},a_1=\frac{1}{\sqrt{2}+1}}\)
oraz dla \(\displaystyle{ n \geq 1}\)
\(\displaystyle{ a_{2n}=2a_n+\sqrt{2}}\)
\(\displaystyle{ a_{2n+1}=2a_n+\frac{1}{\sqrt{2}-1}}\)

2) Niech \(\displaystyle{ b_0=1, b_1=3, b_2=4, b_3=0, b_4=2}\)
oraz dla \(\displaystyle{ n\geq 1}\)
\(\displaystyle{ b_{5n}=21b_n+1}\)
\(\displaystyle{ b_{5n+1}=21b_n+3}\)
\(\displaystyle{ b_{5n+2}=21b_n+4}\)
\(\displaystyle{ b_{5n+3}=21b_n}\)
\(\displaystyle{ b_{5n+4}=21b_n+2}\)
Czy powyższy ciąg jest różnowartościowy? (Jeśli tak, to uzasadnić.)

3) Niech \(\displaystyle{ c_0=0, c_1=2, c_2=1}\)
oraz dla \(\displaystyle{ n \geq 1}\)
\(\displaystyle{ c_{3n}=2c_n}\)
\(\displaystyle{ c_{3n+1}=2c_n+2}\)
\(\displaystyle{ c_{3n+2}=2c_n+1}\)

Czy powyższy ciąg przyjmuje wartości postaci \(\displaystyle{ 2^k,}\) jeśli tak to wyznaczyć (z uzasadnieniem) wszystkie argumenty, dla których one są osiągane.

4) Podać rozwiązanie rekurencji:
\(\displaystyle{ d_0=1,d_1=-1,d_2=1,d_3=-1}\)
oraz dla \(\displaystyle{ n \geq 1}\)
\(\displaystyle{ d_{4n}=d_n}\)
\(\displaystyle{ d_{4n+1}=-d_n}\)
\(\displaystyle{ d_{4n+2}=d_n}\)
\(\displaystyle{ d_{4n+3}=-d_n}\)

Nie będę ukrywać, że pomocny może być mój blog. Ale ciekawią mnie też, a może nawet bardziej niezależne pomysły.

[arek1357]

W zadaniu np czwartym jak dodasz strony lewe i prawe otrzymasz:

\(\displaystyle{ d_{4n+3}+d_{4n+2}+d_{4n+1}+d_{4n}=0}\)

równanie charakterystyczne:

\(\displaystyle{ r^3+r^2+r+1=0}\)

pierwiastki:

\(\displaystyle{ -1, i ,-i}\)

czyli przewidujesz rozwiązanie w postaci:

\(\displaystyle{ d_{n}=a(-1)^n+bi^n+c(-i)^n}\)

a warunki brzegowe?

i teraz coś mi się nie bardzo widzi z tym całym początkiem jak masz w definicji ciągu:

dla: \(\displaystyle{ n>2}\)

to pierwszy wyraz , który otrzymasz to \(\displaystyle{ d_{4 \cdot 3}=d_{12}=d_{3}=-1}\)
A gdzie pozostałe?

i w ogóle te warunki początkowe w tych zadaniach są dla mnie nie za bardzo spójne!
W zadaniu np 1 nie wyznaczysz \(\displaystyle{ a_{2}}\) ,
itd...

W zadaniu pierwszym np układ spełnia zależność niejednorodną:

\(\displaystyle{ a_{2n+1}=a_{2n}+1}\)

[Cutlass]

Przepraszam, rzeczywiście źle to napisałem. Już poprawiłem. Chodziło oczywiście o to, że pewną ilość wyrazów początkowych osobno definiuję, a pozostałe wg podanej zależności.

-- 25 gru 2014, o 15:29 --

\(\displaystyle{ d_{n}=a(-1)^n+bi^n+c(-i)^n}\)

Jedno jest pewne. Rozwiązaniem tej rekurencji jest \(\displaystyle{ -1}\) do czegoś zależnego od \(\displaystyle{ n}\), ale to nie może mieć takiej reprezentacji. Bo wtedy
\(\displaystyle{ -1=d_1=d_4=a+b+c}\)
\(\displaystyle{ 1=-d_1=d_{4+1}=-a+bi-ci}\) stąd \(\displaystyle{ b=c}\)
\(\displaystyle{ -1=d_1=d_{4+2}=a-b-c=a-2b}\)
\(\displaystyle{ 1=-d_1=d_{4+3}=-a-bi+ci=-a}\) stąd \(\displaystyle{ a=-1}\)
to np. z 3. równania \(\displaystyle{ b=c=0}\) co implikuje, że \(\displaystyle{ d_n=-(-1)^n}\), ale np. \(\displaystyle{ -1=d_{4\cdot5}=d_5=d_{4+1}=-d_1=1}\) - sprzeczność.

[arek1357]

Można by się pokusić o ciut inne rozwiązanie np:

\(\displaystyle{ d_{4n+1}+ d_{4n+2}+ d_{4n+3} +d_{4n+4}=(-1)^n \cdot 2}\)

Bo rzeczywiście ten ciąg łamie się dopiero na granicy \(\displaystyle{ 4n,4n+1}\) - na przemian jedynki lub minus jedynki

[Cutlass]

To też nie. Wiemy, że \(\displaystyle{ d_n \in \{-1,1\}}\). Zatem równość
\(\displaystyle{ d_{n+1}-d_n=-d_n+d_n-d_n+d_{n+1}=d_{4n+1}+d_{4n+2}+d_{4n+3}+d_{4n+4}=2(-1)^n}\)
Oznacza, że \(\displaystyle{ d_{n+1}\neq d_n}\), a więc \(\displaystyle{ d_{n+1}=-d_n}\) a to by oznaczało \(\displaystyle{ d_n=(-1)^n}\), co z pewnością nie jest prawdziwe dla np. \(\displaystyle{ n=7}\).

Nie wspomniałem o tym, ale moje rozwiązanie jest postaci -1 do pewnej funkcji, której nie da się za bardzo wyrazić przy pomocy funkcji elementarnych. Oczywiście, nie oznacza to, że nie dałoby się znaleźć funkcji elementarnej, która przystaje do niej modulo 2, ale znając rozwiązanie wątpię, aby dało sie coś takiego zrobić.

Generalnie, tylko w pierwszym zadaniu da się znaleźć rozwiązanie wyrażone przez elementarne operacje (i część całkowitą).

[arek1357]

mam tam to tylko tak sobie głośno myślałem masz racje
i jak rozwiązałem to równanie niejednorodne to nic dobrego z tego nie wyszło!

ale zauważyłem , że to równanie można ładnie zwijać:
posiada okres:

\(\displaystyle{ 1,1,-1,1,-1,-1,1,-1, === ,1,1}\)

dziewiąty wyraz się już powtarza i wszystko idzie tak samo od nowa a więc równanie rekurencyjne powinno wyglądać tak:

\(\displaystyle{ d_{n+8}=d_{n}}\)

a więc równanie charakterystyczne powinno wyglądać tak:

\(\displaystyle{ r^8=1}\)

z warunkami brzegowymi:

\(\displaystyle{ d_{1}=1,d_{2}=1,d_{3}=-1,d_{4}=1,d_{5}=-1,d_{6}=-1,d_{7}=1,d_{8}=-1}\)

pomijając już jak to się zaczyna czy od jeden czy od minus jeden i dlatego uprościłem żeby ujednolicić


I zamiast od - \(\displaystyle{ d_{0}}\) zacząłem od - \(\displaystyle{ d_{1}}\)


Ale szukanie pierwiastków stopnia osiem z jedynki potem znajdywanie współczynników raczej nie należy
to do rzeczy łatwych i przyjemnych.Może w wolframie da się to zrobić.


Zauważyłem jeszcze coś mianowicie:

\(\displaystyle{ d_{n}=-d_{n+4}}\)

co by uprościło nasz układ.

[Cutlass]

Powinienem powiedzieć jeszcze jedną rzecz, ja nie znam żadnych standardowych metod rozwiązywania równań rekurencyjnych. Jednak mimo tego, wymyśliłem metodę (wzór na rozwiązanie)
dla tego typu równań jak te, które są zaprezentowane w zadaniach. Właśnie z powodu tej niewiedzy chciałem zobaczyć jak standardowe metody sobie radzą z takimi równaniami. Dlatego potrzebny mi jest wynik, który bedę mógł sobie już jakoś zweryfilkować.

Poniżej zamieszczam odpowiedź do zadania 4., jeśli nie masz ochoty więcej się z tym bawić. Tak czy owak dzięki za zainteresowanie.

Ukryta treść:    

\(\displaystyle{ d_n=(-1)^{\displaystyle s_4(n)}}\) gdzie \(\displaystyle{ s_4(n)}\) to suma cyfr liczby \(\displaystyle{ n}\) przedstawionej w systemie czwórkowym.
Tak czy owak, gdzie
\(\displaystyle{ s_4(4n+i)=s_4(n)+i}\), oraz \(\displaystyle{ s_4(i)=i}\) dla \(\displaystyle{ i=0,1,2,3, n>0}\)

[arek1357]

No ciekawe ale chyba nasze metody są w tym wypadku równoważne
Dla mnie w tym momencie zadanie się rozświetliło jak zobaczyłem, że w końcu liczby zaczynają się powtarzać! A moja metoda to metoda równania charakterystycznego dla ciągu jednorodnego.


Tylko nie rozumiem co masz na myśli przez sumę cyfr liczby zespolonej w postaci czwórkowej?

rozwiązujesz równanie postaci:

\(\displaystyle{ r^4=-1}\)

i przewidujesz ciąg postaci:

\(\displaystyle{ d_{n}=ar_{1}^n+br_{2}^n+cr_{3}^n+dr_{4}^n}\)

gdzie \(\displaystyle{ a,b,c,d}\) - wyznaczasz z warunków początkowych a \(\displaystyle{ r_{i}}\)

to pierwiastki czwartego stopnia z minus jedynki co nie należy do przyjemności ich liczenie

[Cutlass]

Napisałem "przedstawionej", a nie "zespolonej". Chodziło o zwykłe rozwinięcie w systemie czwórkowym. Nie do końca jeszcze widzę jak dochodzisz do tego samego rozwiązania jak ja.

[arek1357]

Nie o to chodzi że ja tak samo rozwiązałem jak ty tylko, że nasze rozwiązania powinny być równoważne!
Ale rozumiem idee twojego rozumowania sorki w twoim zapisie \(\displaystyle{ i}\) wziąłem jako zespolone i dlatego to zamieszanie nie popatrzyłem dobrze.

[yorgin]

\(\displaystyle{ d_{4n+3}+d_{4n+2}+d_{4n+1}+d_{4n}=0}\)

równanie charakterystyczne:

\(\displaystyle{ r^3+r^2+r+1=0}\)

Nie można stosować metody równań charakterystycznych w takim przypadku.

ale zauważyłem , że to równanie można ładnie zwijać:
posiada okres:

\(\displaystyle{ 1,1,-1,1,-1,-1,1,-1, === ,1,1}\)

dziewiąty wyraz się już powtarza i wszystko idzie tak samo od nowa a więc równanie rekurencyjne powinno wyglądać tak:

\(\displaystyle{ d_{n+8}=d_{n}}\)

Zauważyłeś, czy udowodniłeś? To są dwie różne rzeczy. Jeżeli tego nie dowiodłeś, to dalsze rachunki są bezzasadne.

Tylko nie rozumiem co masz na myśli przez sumę cyfr liczby zespolonej w postaci czwórkowej?

Nie jest to pytanie do mnie, ale jego zadanie świadczy o pewnym niezrozumieniu. Rekurencje rzeczywiste mogą mieć bazowe rozwiązania zespolone, ale jawna postać dowolnego wyrazu ciągu odczytana z ogólnego rozwiązania rekurencji zawsze będzie liczbą rzeczywistą nawet jeżeli wzór ogólny zawiera człony zespolone.

to pierwiastki czwartego stopnia z minus jedynki co nie należy do przyjemności ich liczenie

Hmm to są pierwiastki czwartego stopnia z \(\displaystyle{ 1}\) razy \(\displaystyle{ e^{i\frac{\pi}{4}}}\). Proste, jeżeli spojrzy się na to geometrycznie.

arek1357, widzę dużo "machania rękami", niestety.

Poniżej zamieszczam odpowiedź do zadania 4., jeśli nie masz ochoty więcej się z tym bawić. Tak czy owak dzięki za zainteresowanie.

Ukryta treść:    

\(\displaystyle{ d_n=(-1)^{\displaystyle s_4(n)}}\) gdzie \(\displaystyle{ s_4(n)}\) to suma cyfr liczby \(\displaystyle{ n}\) przedstawionej w systemie czwórkowym.
Tak czy owak, gdzie
\(\displaystyle{ s_4(4n+i)=s_4(n)+i}\), oraz \(\displaystyle{ s_4(i)=i}\) dla \(\displaystyle{ i=0,1,2,3, n>0}\)

Czy to jest wynik, który uzyskałeś sam z obliczeń, czy przepisałeś znane Ci ze źródła rozwiązanie? Jeżeli to pierwsze, chętnie zobaczyłbym sposób.

[arek1357]

Co do pierwszego cytatu sprawa jest zamknięta. tu się zgadzam i mój błąd!

Ale że równanie od dziewiątego miejsca się powtarza to już nie jest machanie rękami i sprawa jest oczywista!
Pewne rzeczy się udowadnia a pewne wystarczy zaobserwować oczywiście, że na początku machałem rękami i z tym się zgodzę jednak tę zależność można nawet udowodnić indukcyjnie i po sprawie nie sądzę że muszę udowadniać rzeczy oczywistych i wszystkich swoich przemyśleń!

Cyt Yorgina:
Nie jest to pytanie do mnie, ale jego zadanie świadczy o pewnym niezrozumieniu. Rekurencje rzeczywiste mogą mieć bazowe rozwiązania zespolone, ale jawna postać dowolnego wyrazu ciągu odczytana z ogólnego rozwiązania rekurencji zawsze będzie liczbą rzeczywistą nawet jeżeli wzór ogólny zawiera człony zespolone.

A co ty myślisz, że ja o tym nie wiem a ty się wymądrzasz trzeba było napisać rozwiązanie a nie
grać rolę mędrca.Jakbyś czytał ze zrozumieniem co pisałem, to miałem zupełnie co inne na myśli.

I jeszcze jedno skoro jak słusznie zauważyłeś że pytanie było nie do Ciebie to łaskawie mogłeś nie
zajmować "wątpliwego" stanowiska!
Chyba że chciałeś nas maluczkich forumowiczów oświecić swoją elokwencją i wiedzą!

Hmm to są pierwiastki czwartego stopnia z 1 razy \(\displaystyle{ e^{i\frac{\pi}{4}}}\). Proste, jeżeli spojrzy się na to geometrycznie.

Tyle to też wiem ale miałem na myśli postać typu \(\displaystyle{ a+bi}\)

Też kolejna próba mędrkowania.

A po trzecie forum jest miejscem wymiany myśli i pewnych doświadczeń więc skoro jak piszesz
że machałem rękami(głośno może myślałem ...może i na początku błędnie)!
to masz racje bo czasem nim coś rozwiążę to sporo się namacham ponieważ nie należę do grona mędrców jak np Ty.
Z poważaniem!

Jeden post z gatunku: "Machając rękami i nogami" prawie usunąłem, drugi tzn. pierwszy raportowałem bo jego wartość merytoryczna jest do bani ja słusznie zresztą zauważył Yorgin!

[yorgin]

Ale że równanie od dziewiątego miejsca się powtarza to już nie jest machanie rękami i sprawa jest oczywista!
Pewne rzeczy się udowadnia a pewne wystarczy zaobserwować oczywiście, (...) nie sądzę że muszę udowadniać rzeczy oczywistych i wszystkich swoich przemyśleń!

Fakty nawet oczywiste wymagają formalnego uzasadnienia. Rzecz oczywista dla Ciebie nie musi być oczywista dla kogoś innego.

A co ty myślisz, że ja o tym nie wiem a ty się wymądrzasz trzeba było napisać rozwiązanie a nie
grać rolę mędrca.Jakbyś czytał ze zrozumieniem co pisałem, to miałem zupełnie co inne na myśli.

Czytałem i znalazłem sumowanie cyfr liczby zespolonej.

I jeszcze jedno skoro jak słusznie zauważyłeś że pytanie było nie do Ciebie to łaskawie mogłeś nie
zajmować "wątpliwego" stanowiska!
Chyba że chciałeś nas maluczkich forumowiczów oświecić swoją elokwencją i wiedzą!

Ja nie odpowiadałem na pytanie, tylko komentowałem sam fakt jego zadania. Jak widać z Twojego komentarza, nie doceniłem Twojej wiedzy, której nie wyeksponowałeś wystarczająco. Mea culpa.

Tyle to też wiem ale miałem na myśli postać typu \(\displaystyle{ a+bi}\)

Ja nie widzę problemu - wzory są, wystarczy podstawić i żadnych trudnych obliczeń nie widzę.

A po trzecie forum jest miejscem wymiany myśli i pewnych doświadczeń więc skoro jak piszesz
że machałem rękami(głośno może myślałem ...może i na początku błędnie)!
to masz racje bo czasem nim coś rozwiążę to sporo się namacham ponieważ nie należę do grona mędrców jak np Ty.

Ja nie tytułuję się mędrcem ani nikim podobnym.

Wymiana myśli ok, ale i ja również chciałem wymienić swoje spostrzeżenia z tego tematu, w szczególności zwrócić uwagę na Twoje wypowiedzi, które nie są do końca jasne i szczegółowe. Przynajmniej nie są dla mnie i może przy okazji chciałem wyjaśnić swoje wątpliwości.

Jeden post z gatunku: "Machając rękami i nogami" prawie usunąłem, drugi tzn. pierwszy raportowałem bo jego wartość merytoryczna jest do bani ja słusznie zresztą zauważył Yorgin!

Raportowanie swoich postów jest "dziwne", a usuwanie zawartości co niektórych jest zabronione.

[arek1357]

Raportowanie swoich postów jest "dziwne", a usuwanie zawartości co niektórych jest zabronione.

Co w tym dziwnego , że raportowałem coś co obydwoje uznaliśmy za niedorzeczność ,kilka razy już na forum raportowałem niektóre posty , które uznałem za głupie a mój nie miał wielkiej wartości dydaktycznej

A usuwanie zawartości "co niektórych" jak piszesz jest zabronione. I teraz wnioskuję z tego, że mój post
należał do tych "co niektórych" choć jasno tego nie sprecyzowałeś, i wnioskuję dalej, że pewnie za to, że mój post należał do tych "co niektórych" dostałem ostrzeżenie co raczej jest żałosne!
Moja rada na przyszłość najpierw doprecyzuj pojęcie "co niektórych" a potem banuj lub wstawiaj ostrzeżenie bo jak na Ciebie to mało profesjonalne stać Cię na więcej...

[Cutlass]

Czy to jest wynik, który uzyskałeś sam z obliczeń, czy przepisałeś znane Ci ze źródła rozwiązanie? Jeżeli to pierwsze, chętnie zobaczyłbym sposób.

Zadania wymyśliłem specjalnie pod wzór, który prezentuję na swoim blogu (i do którego doszedłem samodzielnie).
Powiedzmy, żeby nie zepsuć zabawy z pozostałymi zadaniami, udowodnię wzór obejmujący tylko nieco ogólniejszą sytuację z zadania 4.
Rozważmy równanie
\(\displaystyle{ d_{4n+r}=\alpha(r)d_n}\) dla \(\displaystyle{ n>0, r=0,1,2,3}\) z dowolnymi \(\displaystyle{ d_r, \alpha(r)\neq 0}\).
Wtedy dla dowolnego \(\displaystyle{ n=\sum_{i=0}^N c_i 4^i=c_N\dots c_1 c_0}\), gdzie \(\displaystyle{ c_i \in \{0,1,2,3\}}\) oraz gdzie potęga \(\displaystyle{ N}\) jest minimalną, potrzebną do zapisania \(\displaystyle{ n}\) w systemie czwórkowym,
zachodzi:
\(\displaystyle{ d_{c_N\dots c_1 c_0}n=d_{c_N}\prod_{j=0}^{N-1}\alpha(c_j)}\)
Dowód.
Oznaczmy przez \(\displaystyle{ z}\) kandydata na rozwiązanie z tezy. Zauważmy, że \(\displaystyle{ z(c_0)=d_{c_0} \prod_{j=0}^{-1}\alpha(c_j)=d_{c_0} \prod_{j\in \emptyset} \alpha_{c_j}=d_{c_0}}\).
Zatem zgadzają się wyrazy początkowe. To teraz wystarczy pokazać, że \(\displaystyle{ z}\) definiuje ta sama zależność rekurencyjna. Weźmy dowolne \(\displaystyle{ 4n+r=\sum_{i=0}^N c_i 4^i}\). Wtedy \(\displaystyle{ r=c_0}\) oraz \(\displaystyle{ n=\sum_{i=1}^N c_i 4^{i-1}=\sum_{j=0} ^{N-1}c_{j+1}4^j}\),
co daje, że
\(\displaystyle{ z(n)=z(c_{(N-1)+1})\prod_{j=0}^{N-2}c_{j+1}=z(c_N)\prod_{i=1}^{N-1}\alpha(c_i)}\)
a także
\(\displaystyle{ z(4n+r)=z(c_N)\prod_{j=0}^{N-1} \alpha(c_j)=\alpha(r) z(c_N)\prod_{j=1}^{N-1} \alpha(c_j)=\alpha(r)z(n)}\).
Koniec dowodu.

Teraz wystarczy tylko zauważyć, że dla \(\displaystyle{ d}\) zdefiniowanego w zadaniu 4. zachodzi \(\displaystyle{ d_r=\alpha_r=(-1)^r}\).
A więc stosując wzór dla \(\displaystyle{ n=\sum_{i=0}^Nc_i4^i}\) zachodzi
\(\displaystyle{ d_n=\prod_{j=0}^N (-1)^{c_j}=(-1)^{\displaystyle \sum_{i=0}^Nc_i}}\).

Generalnie, idea jest taka, żeby szukać rozwiązania zależnego od rozwinięć w systemie pozycyjnym o odpowiedniej podstawie. Jeśli we wzorze schodzimy z \(\displaystyle{ m=Ln+r}\)do \(\displaystyle{ n}\) itd. to de facto obliczając wartości ciągu, po drodze wyznaczamy rozwinięcie wyjściowego \(\displaystyle{ m}\) przy podstawie \(\displaystyle{ L}\).