Induktionsbeweis Folge < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Wir definieren zwei Zahlenfolgen r, s: [mm] \IN \mapsto \IN
[/mm]
r(n) :=
1, falls n = 0, 1
2, falls n = 2, 3
3, falls n = 4
4, falls n = 5
2r(n/2-2)r(n/2-1) + [mm] (r(n/2-3))^2, [/mm] falls n > 5 und n ist gerade
[mm] (r((n-1)/2-2))^2 [/mm] + [mm] (r((n-1)/2-1)^2 [/mm] + 2r((n-1)/2-2)r((n-1)/2-3), falls n > 5 und n ist ungerade
s(n) :=
1, falls n = 0, 1
2, falls n = 2
s(n - 2) + s(n - 3), falls n>= 3
1. Beweisen Sie (vorschlagsweise per Induktion), dass r = s gilt. |
(Die Formelanzeige scheint gerade nicht richtig zu funktionieren, deshalb die Aufgabenstellung unschön, aber zumindest halbwegs lesbar)
Mir fehlt irgendwie ein Ansatz, wo ich anfangen soll. Habe die beiden Folgen nachprogrammiert und festgestellt, dass sie gleich sind. Für n = 0 bis 5 kann man es ja auch noch ganz einfach von Hand ausrechnen.
Wenn ich n = n+1 in s(n) einsetze komme ich auf das nächste Element, wenn ich es in r(n) einsetze komme ich schon nicht mehr weiter. Aber das soll ich ja beides nicht zeigen, schließlich sind die Folgen nun mal so definiert.
Wenn ich r = s setze, dann habe ich eine Gleichung mit 2 Seiten die nun mal gar nicht zusammen passen: Potenzen, die ich nicht ausmultiplizieren oder zusammenfassen kann und eine unterschiedliche Zahl von Summanden.
Induktionsbeweise mit Rekursionsformel = Term bekommen ich irgendwie noch auf die Beine, aber bei Rekursionsformel1 = Rekursionsformel2 fehlt mir irgendwie der Ansatz.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:48 So 07.01.2018 | | Autor: | Diophant |
Hallo,
mal zunächst eine kurze Rückfrage:
Den Rekursionsterm für die Folge r(n) ab n=5 habe ich dabei folgendermaßen interpretiert:
[mm] r(n)=\begin{cases} 2r\left(\frac{n}{2}-2\right)*r\left(\frac{n}{2}-1\right)+\left(r\left(\frac{n}{2}-3\right)\right)^2, & \textrm{für } n\ \textrm{ gerade} \\ \left(r\left(\frac{n-1}{2}-2\right)\right)^2+\left(r\left(\frac{n-1}{2}-1\right)\right)^2+2r\left(\frac{n-1}{2}-2\right)*r\left(\frac{n-1}{2}-3\right), & \textrm{für } n \textrm{ ungerade} \end{cases}
[/mm]
Ist das korrekt?
> (Die Formelanzeige scheint gerade nicht richtig zu
> funktionieren, deshalb die Aufgabenstellung unschön, aber
> zumindest halbwegs lesbar)
Ja, das kann ich bestätigen. Am heutigen Sonntag morgen funktioniert es auch noch nicht richtig.
> Mir fehlt irgendwie ein Ansatz, wo ich anfangen soll. Habe
> die beiden Folgen nachprogrammiert und festgestellt, dass
> sie gleich sind. Für n = 0 bis 5 kann man es ja auch noch
> ganz einfach von Hand ausrechnen.
>
> Wenn ich n = n+1 in s(n) einsetze komme ich auf das
> nächste Element, wenn ich es in r(n) einsetze komme ich
> schon nicht mehr weiter. Aber das soll ich ja beides nicht
> zeigen, schließlich sind die Folgen nun mal so definiert.
>
> Wenn ich r = s setze, dann habe ich eine Gleichung mit 2
> Seiten die nun mal gar nicht zusammen passen: Potenzen, die
> ich nicht ausmultiplizieren oder zusammenfassen kann und
> eine unterschiedliche Zahl von Summanden.
>
> Induktionsbeweise mit Rekursionsformel = Term bekommen ich
> irgendwie noch auf die Beine, aber bei Rekursionsformel1 =
> Rekursionsformel2 fehlt mir irgendwie der Ansatz.
Ich hatte gerade schon mit einer Antwort begonnen, ich hätte vorher anfangen sollen zu rechnen. Die Folge s(n) ist ja durch eine lineare Rekursion gegeben, da ist man versucht, per charakteristischem Polynom eine explizite Darstellung zu gewinnen. Die gibt es, aber sie ist grausam (zumindest in meinem CAS). Dieser Weg ist also nicht praktikabel.
Ich denke mal weiter darüber nach, du könntest mir ja (falls die Formel-Darstellung wieder funktioniert) die Richtigkeit meiner Version von r(n) bestätigen bzw. diese noch korrigieren.
Gruß, Diophant
|
|
|
| |
|
Formeln sind so richtig für n > 5. Für den Fall n = 5 ist ja der Wert 4 noch vorgegeben.
Ich habe noch immer keinen Ansatz wie man anfangen soll. Wie mache ich das denn überhaupt prinzipiell? Einfach gleichsetzen und losrechnen wird ja schiefgehen.
Wenn ich als Induktionsbeweis ja n+1 einsetze, dann komme ich bei r(n) ja sofort auf die andere Formel, weil gerade/ungerade wechselt.
Die anderen Aufgabenteile (Grenzwerte, Bedeutung der Werte, ...) konnte ich mir schon herleiten, nur fehlt mir immer noch der erste Teil, der Beweis dass beide Folgen gleich sind.
|
|
|
| |
|
Hallo,
durchgerechnet habe ich es noch nicht,
aber s und r haben dieselben Startwerte, und ich würde nun durch Induktion versuchen zu zeigen, daß r demselben Bildungsprinzip wie s folgt, daß also
r(n)=r(n-2)+r(n-3) für alle n>2
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:05 So 07.01.2018 | | Autor: | Gonozal_IX |
Hiho,
> durchgerechnet habe ich es noch nicht,
> aber s und r haben dieselben Startwerte, und ich würde nun
> durch Induktion versuchen zu zeigen, daß r demselben
> Bildungsprinzip wie s folgt, daß also
> r(n)=r(n-2)+r(n-3) für alle n>2
das war auch mein Ansatz… ist aber gar nicht so einfach ^^
Und noch ein kleiner Tipp: Es ist vllt. auch hilfreich statt r(n) lieber r(2n) bzw r(2n+1) zu untersuchen… dadurch vereinfachen sich viele Dinge.
Gruß,
Gono
|
|
|
| |
|
Wie würde ich denn da anfangen? Gefühlsmäßig müsste ich ja eine Zweiteilung machen "angenommen n ist gerade/ungerade" und dann irgendetwas rechnen.
Aber ich kann ja nichts aus den Funktionsparametern ausklammern und die Potenzen werde ich auch nicht los. Bei r(n) kommt auch überall das n/2 vor, also scheint die Rekursion ja definitiv nicht auf n-2 bzw. n-3 zurückzugreifen wie in s(n) der Fall.
Ich habe z. B. herausgefunden, dass ein t(n) = t(n-1) + t(n-5) ebenfalls die gleiche Folge beschreiben würde, wenn man die ersten 5 Werte vorgibt.
|
|
|
| |
|
> Wie würde ich denn da anfangen? Gefühlsmäßig müsste
> ich ja eine Zweiteilung machen "angenommen n ist
> gerade/ungerade" und dann irgendetwas rechnen.
Ja, so habe ich mir das gedacht.
Und dann, wie Gonozal sagt, für n gerade n=2k,
für n ungerade n=2k+1.
Dann sind zumindest die Halben weg.
Ich habe gerade nicht die Muße, es mit Stift und Papier durchzurechnen - und ohne kriege ich das nicht hin.
Evtl. versuche ich es später.
LG Angela
>
> Aber ich kann ja nichts aus den Funktionsparametern
> ausklammern und die Potenzen werde ich auch nicht los. Bei
> r(n) kommt auch überall das n/2 vor, also scheint die
> Rekursion ja definitiv nicht auf n-2 bzw. n-3
> zurückzugreifen wie in s(n) der Fall.
>
> Ich habe z. B. herausgefunden, dass ein t(n) = t(n-1) +
> t(n-5) ebenfalls die gleiche Folge beschreiben würde, wenn
> man die ersten 5 Werte vorgibt.
|
|
|
| |
|
Hallo,
ich habe jetzt mal gerechnet:
I.A: ...
I.V.: es gelte r(m)=r(m-2)+r(m-3) für alle [mm] ...\le m\le [/mm] n
I.S.:
1.Fall n+1 ungerade, also gibt es ein k mit n+1=2k+1
r(n+1)=r(2k+1)
[mm] =[r(k-2)]^2+[r(k-1)]^2+2r(k-2)r(k-3)
[/mm]
(Induktionsveraussetzung verwenden:)
[mm] =[r(k-2)]^2+[r(k-3)+r(k-4)]^2+2r(k-2)r(k-3)
[/mm]
und jetzt zielstrebig weiterrechnen.
Dann noch für n+1 gerade.
LG Angela
|
|
|
|
