4. vollständige induktion

vollständige induktion

  • P

    .filmor schrieb:

    Warum? Das wäre der Beweis der Aussage (der hier bereits korrekt erbracht wurde). Wenn es dir nur um die Anschauung geht, dann schau dir die Faktoren von n^n und n! an.

    n^n = n *  n    * ... * n
n!  = n * (n-1) * ... * 1

    Also sind alle Faktoren bis auf den ersten bei n! kleiner als bei n^n, die Funktion n*_ ist streng monoton, damit auch ihre Verknüpfungen. Es läuft aber immer auf Induktion hinaus.

    Wir haben bereits in den ersten drei Posts festgestellt, dass das keine saubere mathematische Formulierung ist.

    0
  • D

    Es ist, wie bereits gesagt wurde, eine Abschätzung.

    Eine "saubere Formulierung" gabs auch schon, nur willst du sie nicht akzeptieren.

    0
  • W

    n=1: 1! = 1 <= 1^1 = 1
    n=2: 2! = 2 < 2^2 = 4
    es gibt also ein n für das n! < n^n
    (n+1)! = (n+1)*n! < (n+1)*n^n < (n+1)*(n+1)^n = (n+1)^(n+1) #

    also n! < n^n für alle n > 1
    es folgt auch, dass n! <= n^n für alle n aus |N

    Aber das zählt bestimmt nicht weil ich ja nicht gezeigt habe, dass n^n < (n+1)^n 🙄 .

    0
  • T

    Walli schrieb:

    Aber das zählt bestimmt nicht...

    Nö... das gleiche habe ich schon ein paar Seiten vorher geschrieben, da hats auch nicht gezählt... 🙄

    0
  • P

    Induktionsannahme (IA): für n>=4 gilt 2^n < n! < n^n
    Induktionsbeginn: n=4: 2^4 = 16; 4! = 24; 4^4 = 256;
    => 2^4 < 4! < 4^4 (OK)

    Induktionsschritt: n -> (n+1)
    zu zeigen: 2^(n+1) < (n+1)! < (n+1)^(n+1) f. n>=4

    2 ^(n+1) = 2 * 2^(n) | 2 < (n+1), da n >=4
    < (n+1) * 2^(n) | IA: 2^n < n!
    < (n+1) * n!
    = (n+1)! (erster Teil bewiesen)

    (n+1)! = (n+1) * (n!) | IA: n! < n^n
    < (n+1) * n^n | einfach was dazuaddieren tut nicht weh...
    < (n+1) * [ n^n + ∑ {k=0..(n-1)} binom(n,k)*n^k ] | binom(n,n) = 1 ,1^x = 1
    = (n+1) * [ ∑ {k=0..n} binom(n,k)*n^k * 1^(n-k) ] | binomische Formel
    = (n+1) * (n+1)^n
    = (n+1) ^ (n+1) (zweiter Teil bewiesen)

    mit binom(n,k) ist der Binomialkoeffizient gemeint, also (n! * k!)/(n-k)!
    mit Σ {k=0..n} ist die Summer über alle k von 0 bis n gemeint
    leider geht latex scheinbar nicht...

    0
  • W

    Taurin schrieb:

    Walli schrieb:

    Aber das zählt bestimmt nicht...

    Nö... das gleiche habe ich schon ein paar Seiten vorher geschrieben, da hats auch nicht gezählt... 🙄

    Habe ich wohl beim ersten Mal überlesen. Also noch elementarer kann man das ja wohl kaum beweisen. Wieso geht dann überhaupt noch jemand auf Prof84s getrolle ein?

    @pumuckl: Du hast vergessen vorher die binomische Formel zu beweisen 😃 .

    0
  • P

    @pumuckl:
    *Klapp*, *klapp*, *klapp*!
    Na wenigstens Einer. 👍

    Nach 66 Posts haben wir jemanden gefunden dessen Formulierung ich akzeptiren kann, weil er die Ungleichung durch die rechtsseitige Annäherung im Induktionsschritt (s. mein Post) plausibel gemacht hat!

    An binom. Koef. habe ich auch schon gedacht, war aber zu blöd es über n-1 zu formulieren. 💡

    Wenn ich das richtig realisiere muss man nur n -> n+1 substituieren und hat die gültige plausible Forumlierung der Induktionsannahme!(letzte vier Zeilen)

    Gut, gut ...

    0
  • W

    Ja, hätte man nur vor 66 Post schon gewusst, dass Du die binomische Formel nicht kennst... Die braucht man aber nichtmal zu kennen um einzusehen dass n^n < (n+1)^n 🙄

    0
  • .

    Das ist's nicht ernsthaft, oder? Selbst Mathematiker können gewisse Sachen als gegeben annehmen (z.B. dass (n+1)^n > n^n, wenn ich jeden Faktor vergrößere dann wird auch das Ergebnis größer) oder zumindest sehen, dass das nicht der essentielle Teil des Beweises ist. Hier die Binomialentwicklung anzuwenden ist so ein bisschen wie mit Kanonen auf Spatzen zu werfen ;).

    Und nochmal (ein letztes mal), die Induktionsannahme muss /nicht/ begründet sein. Das ist die Bedeutung des Wortes Annahme. Du beweist, dass es für ein bestimmtes n gilt (hier 2). Dann zeigst du, dass aus der Induktionsannahme (nämlich die Gültigkeit des zu Beweisenden für eine beliebige natürliche Zahl) folgt, dass es auch für die nachfolgende natürliche Zahl gilt. Nur das muss bewiesen (oder „plausibel gemacht“) werden.

    0
  • ?

    .filmor schrieb:

    Das ist's nicht ernsthaft, oder? Selbst Mathematiker können gewisse Sachen als gegeben annehmen (z.B. dass (n+1)^n > n^n, wenn ich jeden Faktor vergrößere dann wird auch das Ergebnis größer) oder zumindest sehen, dass das nicht der essentielle Teil des Beweises ist. Hier die Binomialentwicklung anzuwenden ist so ein bisschen wie mit Kanonen auf Spatzen zu werfen ;).

    Und nochmal (ein letztes mal), die Induktionsannahme muss /nicht/ begründet sein. Das ist die Bedeutung des Wortes Annahme. Du beweist, dass es für ein bestimmtes n gilt (hier 2). Dann zeigst du, dass aus der Induktionsannahme (nämlich die Gültigkeit des zu Beweisenden für eine beliebige natürliche Zahl) folgt, dass es auch für die nachfolgende natürliche Zahl gilt. Nur das muss bewiesen (oder „plausibel gemacht“) werden.

    Spar dir deinen Atem, das ist es nicht wert 🤡

    0
Anmelden zum Antworten