{"id":16455,"date":"2020-08-28T15:18:20","date_gmt":"2020-08-28T13:18:20","guid":{"rendered":"https:\/\/www.studyhelp.de\/online-lernen\/?page_id=16455"},"modified":"2020-11-09T13:53:46","modified_gmt":"2020-11-09T12:53:46","slug":"vollstaendige-induktion","status":"publish","type":"page","link":"https:\/\/www.studyhelp.de\/online-lernen\/mathe\/vollstaendige-induktion\/","title":{"rendered":"Vollst\u00e4ndige Induktion"},"content":{"rendered":"

In diesem Artikel besch\u00e4ftigen wir uns mit einer eigenen Beweisstrategie, der sogenannten vollst\u00e4ndigen Induktion<\/strong>. Diese Art des Beweisens ist immer dann hilfreich, wenn eine Aussage $A(n)$ f\u00fcr alle nat\u00fcrlichen Zahlen oder alle nat\u00fcrlichen Zahlen ab einer bestimmen Zahl bewiesen werden soll. Die Beweistechnik beruht auf der namensgebenden Induktivit\u00e4t<\/strong> der nat\u00fcrlichen Zahlen und orientiert sich an den folgenden drei Schritten:<\/p>\n

Vorgehen der vollst\u00e4ndigen Induktion:<\/strong><\/p>\n

    \n
  1. Induktionsanfang<\/strong>
    \nHier wird die G\u00fcltigkeit der zu beweisenden Aussage f\u00fcr einen Startwert nachgerechnet. Oft wird hier beispielsweise die G\u00fcltigkeit $A(1)$ gezeigt.<\/li>\n
  2. Induktionsvoraussetzung<\/strong>
    \nDiese wird hin und wieder weggelassen, sollte der Vollst\u00e4ndigkeit halber allerdings stets aufgef\u00fchrt werden. Die Induktionsvoraussetzung ist dabei reine Schreibarbeit und bedarf keiner Rechnung. Hier empfiehlt es sich einen Satz auswendig zu lernen und diesen an diese Stelle zu schreiben. Ein Beispiel w\u00e4re Die zu beweisende Aussage $A(n)$ gelte f\u00fcr ein $n\\in\\mathbb{N}$ beliebig.<\/li>\n
  3. Induktionsschritt<\/strong>
    \nDer letzte Schritt der Induktion beweist die G\u00fcltigkeit f\u00fcr $A(n+1)$ indem bereits angenommen wird, dass $A(n)$ g\u00fcltig ist. Es sollte beim Induktionsschritt also stets versucht werden, die eigentliche Aussage, also die Induktionsvoraussetzung, zu verwenden.<\/li>\n

    Anschaulich l\u00e4sst sich die Induktion wie eine Dominoreihe erkl\u00e4ren. Der Induktionsanfang sagt uns, dass beispielsweise der erste Dominostein umf\u00e4llt. Die Induktionsvoraussetzung in Verbindung mit dem Induktionsschritt stellt nun sicher, dass jeder Dominostein, der umf\u00e4llt, auch seinen Nachfolger zum Umfallen bringt. Dies resultiert nun darin, dass alle Dominosteine umfallen. Als N\u00e4chstes betrachten wir verschiedene Beispiele zu diesem Thema.<\/p>\n

    Beispiel<\/strong>
    \nWir m\u00f6chten den kleinen Gau\u00df mit Hilfe der Induktion beweisen. Unsere Aussage $A(n)$ lautet:<\/p>\n

    \\begin{align*}
    \n\\text{F\u00fcr alle }n\\in\\mathbb{N} \\text{ gilt: }\\sum_{k=0}^n k =\\frac{n\\cdot(n+1)}{2}
    \n\\end{align*}<\/p>\n

    Wir starten zun\u00e4chst mit dem Induktionsanfang, hier $n = 1$. Merke: Da die Aussage f\u00fcr wirklich alle nat\u00fcrlichen Zahlen gelten soll, muss als Induktionsanfang hier $n=1$ gew\u00e4hlt werden! Es gilt:<\/p>\n

    1. Induktionsanfang:<\/strong> $n=1$: $\\sum_{k=0}^1 k = 0 + 1 = 1$ und $\\frac{1\\cdot(1+1)}{2} = \\frac{2}{2} = 1$<\/p>\n

    2. Induktionsvoraussetzung:<\/strong> Die Aussage $A(n)$ gelte f\u00fcr ein $n\\in\\mathbb{N}$ beliebig.<\/p>\n

    3. Induktionsschritt<\/strong> $n \\rightarrow n+1$:<\/p>\n

    \\begin{align*}
    \n\\displaystyle\\sum_{k=0}^{n+1} k &= (n+1)+\\displaystyle\\sum_{k=0}^n k = (n+1)+\\frac{n\\cdot(n+1)}{2} \\quad \\text{(I.V.)} \\\\
    \n &=\\frac{2\\cdot(n+1)}{2}+\\frac{n\\cdot(n+1)}{2} =\\frac{2\\cdot(n+1)+n\\cdot(n+1)}{2} =\\frac{(n+1)\\cdot(n+2)}{2}
    \n\\end{align*}<\/p>\n

    Dabei haben wir im ersten Schritt den letzten Summanden explizit au\u00dferhalb der Summe hingeschrieben, w\u00e4hrend wir die restlichen $n$ Summanden als Summe beschreiben. Dies ist bei solchen Aufgaben der vollst\u00e4ndigen Induktion mit Summen ein probates Mittel, um die Induktionsvoraussetzung anzuwenden, welches wir im zweiten Schritt gemacht haben. Im letzten Schritt erhalten wir $\\frac{(n+1)\\cdot(n+2)}{2}$, also genau den Wert der rechten Seite der Aussage $A(n+1)$. Damit ist der Beweis erbracht.<\/p>\n

    Beispiel<\/strong> In diesem Fall lautet die Aussage $A(n)$: $\\text{F\u00fcr alle }n\\in\\mathbb{N}\\text{ gilt: } n^3+2n \\text{ ist durch }3\\text{ teilbar.}$<\/p>\n

    Obwohl diese Aufgabe anders aussieht, gehen wir genau gleich vor:<\/p>\n

    1. Induktionsanfang<\/strong> $n=1$: $1^3+2\\cdot 1 = 3$ und damit durch 3 teilbar<\/p>\n

    2. Induktionsvoraussetzung:<\/strong> Die Aussage $A(n)$ gelte f\u00fcr ein $n\\in\\mathbb{N}$ beliebig.<\/p>\n

    3. Induktionsschritt<\/strong> $n \\rightarrow n+1$:<\/p>\n

    \\begin{align*}
    \n(n+1)^3+2\\cdot(n+1)&=(n+1)\\cdot((n+1)^2+2) =(n+1)\\cdot(n^2+2n+1+2)\\\\
    \n\t&=n^3+2n^2+3n+n^2+2n+3 =(n^3+2n)+(3n^2+3n+3)\\\\
    \n\t&=n^3+2n+3\\cdot(n^2+n+1)
    \n\\end{align*}<\/p>\n

    Nach der Induktionsvoraussetzung ist $n^3+2n$ durch 3 teilbar und da $3\\cdot(n^2+n+1)$ ein Vielfaches von 3 ist, ist der Term ebenfalls durch 3 teilbar. Da beide Summanden durch $3$ teilbar sind, ist auch die Summe durch $3$ teilbar. Damit gilt der Induktionsschritt und wir haben die Aussage bewiesen.<\/p>\n","protected":false},"excerpt":{"rendered":"

    In diesem Artikel besch\u00e4ftigen wir uns mit einer eigenen Beweisstrategie, der sogenannten vollst\u00e4ndigen Induktion. Diese Art des Beweisens ist immer dann hilfreich, wenn eine Aussage $A(n)$ f\u00fcr alle nat\u00fcrlichen Zahlen oder alle nat\u00fcrlichen Zahlen ab einer bestimmen Zahl bewiesen werden soll. Die Beweistechnik beruht auf der namensgebenden Induktivit\u00e4t der nat\u00fcrlichen Zahlen und orientiert sich an […]<\/p>\n","protected":false},"author":3,"featured_media":0,"parent":6291,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"categories":[74],"tags":[],"yoast_head":"\nVollst\u00e4ndige Induktion - StudyHelp Online-Lernen<\/title>\n<meta name=\"description\" content=\"Die Vollst\u00e4ndige Induktion ist hilfreich, wenn eine Aussage A(n) f\u00fcr alle nat\u00fcrlichen Zahlen (nat\u00fcrlichen Zahlen ab einer bestimmen Zahl) bewiesen werden soll.\" \/>\n<meta name=\"robots\" content=\"index, follow\" \/>\n<meta name=\"googlebot\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<meta name=\"bingbot\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.studyhelp.de\/online-lernen\/mathe\/vollstaendige-induktion\/\" \/>\n<meta property=\"og:locale\" content=\"de_DE\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Vollst\u00e4ndige Induktion - StudyHelp Online-Lernen\" \/>\n<meta property=\"og:description\" content=\"Die Vollst\u00e4ndige Induktion ist hilfreich, wenn eine Aussage A(n) f\u00fcr alle nat\u00fcrlichen Zahlen (nat\u00fcrlichen Zahlen ab einer bestimmen Zahl) bewiesen werden soll.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.studyhelp.de\/online-lernen\/mathe\/vollstaendige-induktion\/\" \/>\n<meta property=\"og:site_name\" content=\"StudyHelp Online-Lernen\" \/>\n<meta property=\"article:modified_time\" content=\"2020-11-09T12:53:46+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.studyhelp.de\/online-lernen\/#website\",\"url\":\"https:\/\/www.studyhelp.de\/online-lernen\/\",\"name\":\"StudyHelp Online-Lernen\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":\"https:\/\/www.studyhelp.de\/online-lernen\/?s={search_term_string}\",\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"de-DE\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.studyhelp.de\/online-lernen\/mathe\/vollstaendige-induktion\/#webpage\",\"url\":\"https:\/\/www.studyhelp.de\/online-lernen\/mathe\/vollstaendige-induktion\/\",\"name\":\"Vollst\\u00e4ndige Induktion - StudyHelp Online-Lernen\",\"isPartOf\":{\"@id\":\"https:\/\/www.studyhelp.de\/online-lernen\/#website\"},\"datePublished\":\"2020-08-28T13:18:20+00:00\",\"dateModified\":\"2020-11-09T12:53:46+00:00\",\"description\":\"Die Vollst\\u00e4ndige Induktion ist hilfreich, wenn eine Aussage A(n) f\\u00fcr alle nat\\u00fcrlichen Zahlen (nat\\u00fcrlichen Zahlen ab einer bestimmen Zahl) bewiesen werden soll.\",\"inLanguage\":\"de-DE\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.studyhelp.de\/online-lernen\/mathe\/vollstaendige-induktion\/\"]}]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","_links":{"self":[{"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/pages\/16455"}],"collection":[{"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/comments?post=16455"}],"version-history":[{"count":8,"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/pages\/16455\/revisions"}],"predecessor-version":[{"id":16463,"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/pages\/16455\/revisions\/16463"}],"up":[{"embeddable":true,"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/pages\/6291"}],"wp:attachment":[{"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/media?parent=16455"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/categories?post=16455"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.studyhelp.de\/online-lernen\/wp-json\/wp\/v2\/tags?post=16455"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}