vollständige induktion

    • denyo7788
      denyo7788
      Bronze
      Dabei seit: 06.05.2007 Beiträge: 264
      hab hier eine aufgabe mit der ich nicht klar komme... weiß nicht was ich mit dem 2^n-1 anfangen soll.. mit dem abschätzen hab ich auch noch probleme...


      die aufgabe:

      n/2 < Sigma(unten: k = 1; oben: (2^n )-1) 1/k < n
      für alle n >= 2...

      also Das Summenzeichen nochmal: für 1/k ; von k = 1 bis (2^n)-1


      wär cool wenns jemand mit kurzer erläuterung zeigen würde... thx!!
  • 9 Antworten
    • larseda
      larseda
      Bronze
      Dabei seit: 06.08.2006 Beiträge: 9.299
      Ind.Anfang

      n= 2

      2/2 < Sigma(unten: k = 1; oben: (2^2 )-1) 1/k < 2

      1 < 1,5 < 2 //


      Ind.-Schritt (die formal ist gültig für jeden beliebigen nachfolger)

      n+1/2 < Sigma(unten: k = 1; oben: (2^n+1 )-1) 1/k < n+1

      ...
      Sigma(unten: k = 1; oben: (2^n+1 )-1) 1/k = Sigma(unten: k = 1; oben: (2^n )-1) 1/k + 1/(2^n+1)

      und für Sigma(unten: k = 1; oben: (2^n )-1) 1/k setzt jetzt die Ind.Voraussetzung ein

      dabei sollte du das getrennt zeigen ... also einmal, dass die summe < ... ist und einmal, dass sie > ... ist.


      PS
      nein ich schreib es extra nicht so hin, dass du es nur abschreiben musst :)
      aber sollten alle wesentlichen schritte drin sein
    • denyo7788
      denyo7788
      Bronze
      Dabei seit: 06.05.2007 Beiträge: 264
      danke erstmal für die antwort!! aber das ist mein problem... bei ner gleichung würd ich wissen was ich einzetze aber nicht bei einer ungleichung?!? weiß nicht durch was ich das sigma ersetzen soll... und ist das nen fehler das da steht oben 1,5... bei mir kommt 11/6 raus....; und unten 1/ 2^(n+1)... muss da nicht
      1/ (2^(n+1) -1) hin?
    • franziskus
      franziskus
      Bronze
      Dabei seit: 06.05.2006 Beiträge: 153
      Original von denyo7788
      danke erstmal für die antwort!! aber das ist mein problem... bei ner gleichung würd ich wissen was ich einzetze aber nicht bei einer ungleichung?!? weiß nicht durch was ich das sigma ersetzen soll... und ist das nen fehler das da steht oben 1,5... bei mir kommt 11/6 raus....; und unten 1/ 2^(n+1)... muss da nicht
      1/ (2^(n+1) -1) hin?
      Du hast recht:
      Beim Ind.Anfang ist der mittlere WErt 11/6 und auch
      die Summe beim Ind.Schritt ist bei larseda nicht korrekt.

      Für den Beweis des Ind. Schrittes musst du die "zweite Hälfte" der Summe, d.h. die Summenglieder ab k = 2^n einmal nach unten und einmal nach oben abschätzen. Für die "erste Hälfte" verwendest Du die Ind.Vorausetzung (gültigkeit der Ungleichung für n)
    • denyo7788
      denyo7788
      Bronze
      Dabei seit: 06.05.2007 Beiträge: 264
      ... ich weiß ja nicht was da zulässig ist.. kann mir nichts genaueres unter abschätzen vorstellen. ... könntst dus bitte konkretisieren damit ich ein beispiel hab für folgende aufgaben... evt noch kurz erläutern wie man abschätzt bzw wie die abschätzung zustande kommt?...
    • franziskus
      franziskus
      Bronze
      Dabei seit: 06.05.2006 Beiträge: 153
      die "zweite Hälfte" der Summe beginnt mit dem Summanden 1/2^n, der letzte Summand ist 1/(2^(n+1)-1).
      Das sind insgesamt 2^n Summanden, wobei der erste der wertmäßig größte ist und der letzte der wertmäßig kleinste.
      Damit schätzt du die Summe nach unten ab durch 2^n mal den kleinsten, was größer als 1/2 ist und du schätzt die Summe nach oben ab durch 2^n mal den größten ab, was genau 1 ist.
    • larseda
      larseda
      Bronze
      Dabei seit: 06.08.2006 Beiträge: 9.299
      dann sollte sowas halt doch nicht nebenbei und mit unleserlicher formatierung machen :D

      das geilste is ja, dass ich nicht mal die summe richtig ausgerechnet hab :f_mad:
    • Django1980
      Django1980
      Bronze
      Dabei seit: 15.02.2006 Beiträge: 2.022
      habs mal für die erste richtung gelöst, 2te sollte analog gehen. du musst die summe (k=1 bis 2^(n+1)-1) geschickt umschreiben, so dass man die Induktionsvoraussetzung benutzen kann:

      summe (k=1 bis 2^(n+1)-1) 1/k = summe (k=1 bis 2^n) 1/k + summe (k=2^(n) +1 bis 2^(n+1)) 1/k -1/((2^(n+1)-1)

      edit: die anschließende rechnung hatte nen kleinen fehler, mach ich nochmal flott, sollte aber kein prob sein.

      die andere Seite geht analog
    • Django1980
      Django1980
      Bronze
      Dabei seit: 15.02.2006 Beiträge: 2.022
      für die <n ist mir jetzt ne abschätzung gelungen:

      summe (k=2^n+1…2^(n+1)) 1/k = 1/(2^n+1)+…+1/(2^(n+1)< 2^n*(1/2^n+1) = (2^n)/(2^n+1) <1



      Man muss da ja eigentlich zeigen summe ….<n+1, das n fliegt ja nach IV weg und man muss noch zeigen, ……..<1

      Die andere Seite ist was schwieriger, viel Glück ;)
    • denyo7788
      denyo7788
      Bronze
      Dabei seit: 06.05.2007 Beiträge: 264
      ... ja habs en bischen undeutlich hingeshriben^^... aber danke für die antworten... komme langsam dahinter!!!