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

frage344 aktiv_icon

13:43 Uhr, 23.11.2022

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ß

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

Respon

14:11 Uhr, 23.11.2022

Verwende die Rekursionsvorschrift.( Zeige vorher, dass die Folge monoton wächst. )

f_{1001} = 2 \cdot f_{1000} + f_{999} < 3 \cdot f_{1000}

f_{999} < f_{1000} \Rightarrow

falsch

frage344 aktiv_icon

14:15 Uhr, 23.11.2022

Achsoo. Da hab ich viel zu kompliziert gedacht. Danke sehr.

HAL9000

14:22 Uhr, 23.11.2022

> Hab versucht eine Gleichung aufzustellen

f_{n} = \frac{1}{2} [{(1 + \sqrt{2})}^{n} + {(1 - \sqrt{2})}^{n}]

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

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

michaL aktiv_icon

14:33 Uhr, 23.11.2022

Hallo,

sei

V := {(g_{i})_{i \in ℕ} ∣ g_{i + 2} = 2 g_{i + 1} + g_{i} \forall i \in ℕ}

die Menge aller Folgen, die der gleichen Rekursionsgleichung gehorchen wie deine.

Vielleicht erkennt man, dass mit

(g_{i})_{i \in ℕ}, (h_{i})_{i \in ℕ} \in V

und

λ \in ℝ

auch

(g_{i})_{i \in ℕ} + (h_{i})_{i \in ℕ} \in V

und

λ \cdot (g_{i})_{i \in ℕ} \in V

gelten.
Mit anderen Worten: es handelt sich bei

(V, +, 0, -, \cdot, 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

(g_{i})_{i \in ℕ}

mit

g_{0} = 0

und

g_{1} = 1

bzw.

g_{0} = 1

und

g_{1} = 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

(q^{n})_{n \in ℕ}

sind.
Also muss

q^{n + 2} = 2 q^{n + 1} + q^{n} \overset{}{\Leftrightarrow} q^{2} - 2 q - 1 \overset{}{\Leftrightarrow} q = 1 \pm \sqrt{2}

gelten.
Klasse! Ein zweidimensionaler VR und wir bekommen zwei Werte für hoffentlich geeignete Basiselemente.

Seien also

q_{1} := 1 - \sqrt{2}

und

q_{2} := 1 + \sqrt{2}

, sowie

(q_{1})^{n}_n \in n

und

(q_{2})^{n}_n \in n

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 := {(q_{1})^{n}_n \in n

eine Basis von

V

ist.
Nun braucht man nur noch die Koordinaten deiner Folge

(f_{n})_{n \in n}

bzgl. der Basis

B

.

Notwendig ist, dass

λ q_{1}^{0} + μ q_{2}^{0} = λ + μ = f_{0} = 1

und

λ q_{1}^{1} + μ q_{2}^{1} = λ (1 - \sqrt{2}) + μ (1 + \sqrt{2}) = f_{1} = 1

gelten.

Damit erhält man die Koordinaten von der Folge bzgl.

B

.
Wenn du nachrechnen willst: Ich habe

λ = μ = \frac{1}{2}

heraus.

Damit kann deine Folge explizit berechnet werden:

f_{n} = \frac{1}{2} {(1 - \sqrt{2})}^{n} + \frac{1}{2} {(1 + \sqrt{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.

frage344 aktiv_icon

14:53 Uhr, 23.11.2022

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 ....

frage344 aktiv_icon

14:55 Uhr, 23.11.2022

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?

HAL9000

15:07 Uhr, 23.11.2022

> Bitte posting ignorieren.

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

michaL aktiv_icon

17:33 Uhr, 23.11.2022

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

(\begin{array}{rr} 0 & 1 \\ 1 & 2 \end{array}) \cdot (\begin{array}{r} f_{n} \\ f_{n + 1} \end{array}) = (\begin{array}{r} f_{n + 1} \\ f_{n} + 2 f_{n + 1} \end{array}) = (\begin{array}{r} f_{n + 1} \\ f_{n + 2} \end{array})

und damit

{(\begin{array}{rr} 0 & 1 \\ 1 & 2 \end{array})}^{n} \cdot (\begin{array}{r} 1 \\ 1 \end{array}) = (\begin{array}{r} f_{n} \\ f_{n + 1} \end{array})

.

Das Gute ist, dass

A := (\begin{array}{rr} 0 & 1 \\ 1 & 2 \end{array})

wegen

χ_{A} (x) = x^{2} - 2 x - 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

HAL9000

10:06 Uhr, 24.11.2022

(Leicht) Off-topic:

Mich faszinieren an diesen Lucasfolgen spezielle zahlentheoretische Eigenschaften: So gilt z.B. für

a_{n} = p a_{n - 1} + q a_{n - 2}

mit

p \in ℤ

sowie

∣ q ∣ = 1

sowie den Startwerten

a_{0} = 0, a_{1} = 1

die verblüffende Eigenschaft

ggT (a_{n}, a_{m}) = a_{ggT (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

f_{0} = 1, f_{1} = 1

nicht die Anfangswerte. ;-)

frage344 aktiv_icon

17:17 Uhr, 24.11.2022

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

1563918

1563800

	Status: nicht eingeloggt	Noch nicht registriert?