Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Rekursionsgleichung lösen

Rekursionsgleichung lösen

Universität / Fachhochschule

Rekursives Zählen

Tags: Rekursives Zählen

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
frage344

frage344 aktiv_icon

13:43 Uhr, 23.11.2022

Antworten
Hi, also ich komme bei dieser Aufgabe nicht weiter:
->siehe Anhang
Mein Ansatz ist die ersten Werte der Rekursiven aufzuschreiben :
1,1,3,7,17,51,119.....
Als erstes hatte ich mir überlegt ob es irgendwas mit 2°n zu tun hat, da 2^n für die ersten n lautet:
1,2,4,8,16,32 ..... bis n = 5 ähnelt es sehr aber dann ist ein großer Sprung mit Differenz 19 . Hab versucht eine Gleichung aufzustellen , aber ist mir nicht gelungen.
Was einem direkt auffällt , dass die rekursionsgleichung fn sehr den fibonaccizahlen ähnelt. Aber diese lauten ja 1,1,2,3,5,8,13,21... Hier wird ab n = 4 die Differenz wieder sehr groß.
Ich weiß nicht wie ich weiter machen soll.
Gruß

Screenshot 2022-11-23 at 13.43.03

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Antwort
Respon

Respon

14:11 Uhr, 23.11.2022

Antworten
Verwende die Rekursionsvorschrift.( Zeige vorher, dass die Folge monoton wächst. )
f1001=2f1000+f999<3f1000   da f999<f1000 falsch
Frage beantwortet
frage344

frage344 aktiv_icon

14:15 Uhr, 23.11.2022

Antworten
Achsoo. Da hab ich viel zu kompliziert gedacht. Danke sehr.
Antwort
HAL9000

HAL9000 aktiv_icon

14:22 Uhr, 23.11.2022

Antworten
> Hab versucht eine Gleichung aufzustellen

fn=12[(1+2)n+(1-2)n]

> 1,1,3,7,17,51,119..

Fehler an Index 5: Richtig ist > 1,1,3,7,17,41,99..
Antwort
michaL

michaL aktiv_icon

14:33 Uhr, 23.11.2022

Antworten
Hallo,

sei V:={(gi)igi+2=2gi+1+gii} die Menge aller Folgen, die der gleichen Rekursionsgleichung gehorchen wie deine.

Vielleicht erkennt man, dass mit (gi)i,(hi)iV und λ auch (gi)i+(hi)iV und λ(gi)iV gelten.
Mit anderen Worten: es handelt sich bei (V,+,0,-,,1) um einen (reellen) Vektorraum.
Dieser hat offensichtlich die Dimension 2. (Früher hat man auch gern mal Freiheitsgrade gesagt. Ich kann die ersten beiden Elemente frei wählen.)
Damit geht es also darum, eine geeignete Basis zu finden. Die naheliegende Folgen (gi)i mit g0=0 und g1=1 bzw. g0=1 und g1=0 erweisen sich nicht als so geeignet, da ich deren n-tes Folgeglied auch nicht so einfach berechnen kann.
Da wählen wir lieber Folgen, die gleichzeitig (zu ihrer Zugehörigkeit zu V) geometrische Folgen (qn)n sind.
Also muss qn+2=2qn+1+qnq2-2q-1q=1±2 gelten.
Klasse! Ein zweidimensionaler VR und wir bekommen zwei Werte für hoffentlich geeignete Basiselemente.

Seien also q1:=1-2 und q2:=1+2, sowie (q1)n_nn und (q2)n_nn die zwei hoffentlich geeigneten Folgen aus V.
Zuerst kann man nachrechnen, dass diese Folgen linear unabhängig sind. (Kannst du das alleine?)
Wenn man dass hat, weiß man, das B:={(q1)n_nn eine Basis von V ist.
Nun braucht man nur noch die Koordinaten deiner Folge (fn)nn bzgl. der Basis B.

Notwendig ist, dass λq10+μq20=λ+μ=f0=1 und λq11+μq21=λ(1-2)+μ(1+2)=f1=1 gelten.

Damit erhält man die Koordinaten von der Folge bzgl. B.
Wenn du nachrechnen willst: Ich habe λ=μ=12 heraus.

Damit kann deine Folge explizit berechnet werden: fn=12(1-2)n+12(1+2)n

Damit lassen sich die Aussagen sicher leicht verifizieren. (Allerdings hege ich Zweifel daran, dass erwartet wird, dass ihr es auf diese Weise löst...)

Mfg Michael


EDIT: Mist, schon wieder zu langsam...
Bitte posting ignorieren.
Frage beantwortet
frage344

frage344 aktiv_icon

14:53 Uhr, 23.11.2022

Antworten
Erstmal Vielen Danke für die sehr ausführliche Antwort. Also konnte deinen Rechenweg soweit nachvollziehen. Ist doch nicht so einfach wie ich gedacht habe ....
Frage beantwortet
frage344

frage344 aktiv_icon

14:55 Uhr, 23.11.2022

Antworten
Wie bist du auf den Gedanken gekommen:

Da wählen wir lieber Folgen, die gleichzeitig (zu ihrer Zugehörigkeit zu V) geometrische Folgen (qn)n∈ℕ sind. also blöd gefragt , warum genau geometrische Folgen?
Antwort
HAL9000

HAL9000 aktiv_icon

15:07 Uhr, 23.11.2022

Antworten
> Bitte posting ignorieren.

Nein, wieso? Ich hab die Formel nur hingeknallt, du hingegen deren Zustandekommen erklärt. Dafür ein Dankeschön.
Antwort
michaL

michaL aktiv_icon

17:33 Uhr, 23.11.2022

Antworten
Hallo,

> warum genau geometrische Folgen?

Nun, im Grunde könnte es auch eine andere Art von Folge sein.
Zwei Voraussetzungen müssen die Basiselemente aber erfüllen:
* Sie müssen die Rekursionsgleichung erfüllen.
* Deren hintere Glieder müssen explizit berechenbar sein.

Klar: Wenn die erste Bedingung nicht erfüllt ist, dann können sie überhaupt nicht als Basiselemente dienen.
Wenn die zweite Bedingung nicht erfüllt ist, dann gewinne ich doch schließlich wieder keine explizite Formel für deinen speziellen Kandidaten.
Davon ab könnten auch andere Kandidaten infrage kommen. Allerdings schließen sich wohl arithmetische Folgen aus. Wenn du sonst noch einfache Folgen kennst, die sowohl die Rekursionsgleichung erfüllen als auch explizite Bildungsgesetze haben, dann her damit. :-)

@HAL9000: Man kann die Formel auch über Matrizen herleiten.
Es gilt konkret (0112)(fnfn+1)=(fn+1fn+2fn+1)=(fn+1fn+2) und damit (0112)n(11)=(fnfn+1).

Das Gute ist, dass A:=(0112) wegen χA(x)=x2-2x-1 diagonalisierbar ist. Dass das char. Polynom über die Rekursionsgleichung mit den Kandidaten für die Basiselemente zusammenhängt, ist kein Zufall.

Da also A diagonalisierbar ist, kann man darüber die gesuchte Formel gewinnen.

Mfg Michael
Antwort
HAL9000

HAL9000 aktiv_icon

10:06 Uhr, 24.11.2022

Antworten
(Leicht) Off-topic:

Mich faszinieren an diesen Lucasfolgen spezielle zahlentheoretische Eigenschaften: So gilt z.B. für an=pan-1+qan-2 mit p sowie q=1 sowie den Startwerten a0=0,a1=1 die verblüffende Eigenschaft

ggT(an,am)=aggT(n,m),

sehr gut beobachtbar an der Fibonacci-Folge (dort ist ja p=q=1).

Die Folge hier passt leider nicht ganz rein: Zwar gehört p=2,q=1 ins Schema, aber mit f0=1,f1=1 nicht die Anfangswerte. ;-)

Frage beantwortet
frage344

frage344 aktiv_icon

17:17 Uhr, 24.11.2022

Antworten
Ahh, super. Vielen Dank für die ausführliche Antwort.