matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenFolgen und ReihenInduktionsbeweis Folge
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Folgen und Reihen" - Induktionsbeweis Folge
Induktionsbeweis Folge < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Induktionsbeweis Folge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:14 Sa 06.01.2018
Autor: TrickyDinkle

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.

        
Bezug
Induktionsbeweis Folge: Kurze Rückfrage
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Induktionsbeweis Folge: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:42 So 07.01.2018
Autor: TrickyDinkle

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.

Bezug
        
Bezug
Induktionsbeweis Folge: Antwort
Status: (Antwort) fertig Status 
Datum: 17:25 So 07.01.2018
Autor: angela.h.b.

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




Bezug
                
Bezug
Induktionsbeweis Folge: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Induktionsbeweis Folge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:08 So 07.01.2018
Autor: TrickyDinkle

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.

Bezug
                        
Bezug
Induktionsbeweis Folge: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:14 So 07.01.2018
Autor: angela.h.b.


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


Bezug
                        
Bezug
Induktionsbeweis Folge: Antwort
Status: (Antwort) fertig Status 
Datum: 07:45 Mo 08.01.2018
Autor: angela.h.b.

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]