Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Induktion » Vollständige Induktion mit Problemen
Autor
Universität/Hochschule Vollständige Induktion mit Problemen
Moana
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 18.10.2007
Mitteilungen: 264
Wohnort: Berlin
  Themenstart: 2022-12-07

Hallo ihr Lieben, ich poste meine Frage mal an dieser Stelle, da wir es im Thema "Beweistechniken" durchnehmen, sry, wenn es woanders hin sollte. Leider ist es mal wieder so weit und ich brauche eure Hilfe. Ich soll diese Aufgabe lösen: Den Anfang habe ich wie folgt gemacht: IA: n=0 0 = (a_0;2) + (b_0;1) = (a_0^2 - a_0)/2 + b_0 mit a_0 = 1 und b_0 = 0 geht die Gleichung auf: 0 = (1^2 - 1)/2 + 0 = 0 Ich habe diese Rechnung auch bis \(n = 10\) durchgeführt für ein Muster und erhalte dadurch diese Auflistung für \(a_n\) und \(b_n\): \showon n | a_n | b_n 0 | 1 | 0 1 | 2 | 0 2 | 2 | 1 3 | 3 | 0 4 | 3 | 1 5 | 3 | 2 6 | 4 | 0 7 | 4 | 1 8 | 4 | 2 9 | 4 | 3 10 | 5 | 0 \showoff Die Induktionsvoraussetzung ist ja dann die Bedingung aus der Aufgabe und der Induktionsschritt ist nun der Punkt, bei dem ich nicht weiter komme: IS: n |-> n+1 => n+1 = (a_(n+1);2) + (b_(n+1);1) | aufgelöst => n+1 = (a_(n+1)^2-a_(n+1))/2 + b_(n+1) => ... Ab dem Punkt weiß ich leider nicht mehr weiter. Kann mir da vielleicht jemand auf die Sprünge helfen? Ach ja, wie ich die Eindeutigkeit von \(a_n\) und \(b_n\) zeige, weiß ich leider auch noch nicht 🙁 LG Moana


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1302
Wohnort: Kiel, Deutschland
  Beitrag No.1, eingetragen 2022-12-07

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Hallo Moana, ist der Hinweis 2 so zu verstehen, dass der Beweis der Existenz auf Biegen und Brechen mit Induktion geführt werden muss? Deine Idee, eine Gleichung aufzustellen und zu lösen, finde ich nämlich schöner. Die Aussage, dass es für alle \(y\in\mathbb{N}\) zwei natürliche Zahlen \(m,\,n\) gibt mit \[ y=\dbinom{n}{2}+\dbinom{m}{1} \] ist, wie du schon erkannt hast, äquivent dazu, dass es für alle \(y\in\mathbb{N}\) zwei natürliche Zahlen \(m,\,n\) gibt mit \[ y=\dfrac{n\,(n-1)}{2}+m\quad. \] Zeige also, dass die Funktion \[ \varphi:\left\{ \begin{array}{ll} \mathbb{N}\times\mathbb{N} &\to&\mathbb{N}\\ (m,\,n)&\mapsto&\dfrac{n\,(n-1)}{2}+m \end{array} \right. \] surjektiv ist, und du bist dann mit der Existenzaussage fertig. Dabei wird es hilfreich sein, zu unterscheiden, ob \(y\) eine Dreieckszahl ist oder nicht. Induktion ist hier nicht nötig. mfg thureduehrsen\(\endgroup\)


   Profil
Moana
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 18.10.2007
Mitteilungen: 264
Wohnort: Berlin
  Beitrag No.2, vom Themenstarter, eingetragen 2022-12-07

Hallo thureduehrsen, ja, leider ist der Hinweis 2 so zu verstehen. Wir müssen Induktion verwenden. Das mit der surjektiven Funktion für die Existenzaussage ist sehr schön und elegant. Vielleicht mache ich das noch zusätzlich in die Abgabe mit rein ^^ LG Moana


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1302
Wohnort: Kiel, Deutschland
  Beitrag No.3, eingetragen 2022-12-07

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Hallo Moana, ich wurde darauf hingewiesen, dass mir die Bedingung, dass \[m\(\endgroup\)


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3676
  Beitrag No.4, eingetragen 2022-12-07

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Hallo, Tipp zur Induktion: Kannst Du Muster erkennen, wann $a_{n+1} = a_n +1$ bzw. wann $b_{n+1}=b_n+1$ gilt? Versuche eine Rekursionsformel für $a_n,b_n$ aufzuschreiben und beweise damit die Existenz per Induktion.\(\endgroup\)


   Profil
Moana
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 18.10.2007
Mitteilungen: 264
Wohnort: Berlin
  Beitrag No.5, vom Themenstarter, eingetragen 2022-12-07

\quoteon(2022-12-07 20:49 - thureduehrsen in Beitrag No. 3) Hallo Moana, ich wurde darauf hingewiesen, dass mir die Bedingung, dass \[m


   Profil
Moana
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 18.10.2007
Mitteilungen: 264
Wohnort: Berlin
  Beitrag No.6, vom Themenstarter, eingetragen 2022-12-08

\quoteon(2022-12-07 21:17 - Nuramon in Beitrag No. 4) Hallo, Tipp zur Induktion: Kannst Du Muster erkennen, wann $a_{n+1} = a_n +1$ bzw. wann $b_{n+1}=b_n+1$ gilt? Versuche eine Rekursionsformel für $a_n,b_n$ aufzuschreiben und beweise damit die Existenz per Induktion. \quoteoff Hi, ich muss ja dann eine Fallunterscheidung machen. \[\text{Fall 1: } a_n - b_n = 1 \Rightarrow a_{n+1} = a_n + 1\; , \quad b_{n+1} = 0\] \[\text{Fall 2: } a_n - b_n > 1 \Rightarrow a_{n+1} = a_n\; , \quad b_{n+1} = b_n + 1\] Heißt das dann, dass ich auch bei der Induktion eine Fallunterscheidung machen kann? LG Moana


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1302
Wohnort: Kiel, Deutschland
  Beitrag No.7, eingetragen 2022-12-08

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Hallo Moana, ich möchte noch etwas zu dem Ansatz mit \[ y=\dbinom{n}{2}+\dbinom{m}{1}=\dfrac{n\,(n-1)}{2}+m \] schreiben. Also wo ich die Liste, aus der du die Vermutung mit der Fallunterscheidung gewonnen hast, nicht brauche. Zunächst ist es nicht vollständig trivial, dass die Gleichung \[ \dbinom{n}{2} = \dfrac{n\,(n-1)}{2} \] auch für \(n\in\{0,\,1\}\) gilt. Wenn du dies aber gezeigt hast, dann ist der Kern der Argumentation Folgendes: \showon Sei \(y\in\mathbb{N}\). Finde die größte Dreieckszahl \(d\in\mathbb{N}\), für die \(d\leqslant y\) gilt. Schreibe \(d=\displaystyle\sum_{k=0}^{n-1}k\) für ein passendes \(n\in\mathbb{N}\), es gibt genau ein solches \(n\). Setze dann.... \showon \(m:=y-d\). Dann folgt \[ \dbinom{m}{1}+\dbinom{n}{2}=y \] durch simples Nachrechnen. \showon \[ \begin{array}{rcllll} \dbinom{m}{1}+\dbinom{n}{2} &=& \dbinom{y-d}{1}+\dbinom{n}{2} &&& m=y-d\\[3mm] &=& y-d+\dbinom{n}{2}&&& \dbinom{y-d}{1}=y-d\\[3mm] &=& y-d+\dfrac{n\,(n-1)}{2}&&& \dbinom{n}{2}=\dfrac{n\,(n-1)}{2}\\[3mm] &=&y-d+\displaystyle\sum_{k=0}^{n-1}k&&& \dfrac{n\,(n-1)}{2}=\displaystyle\sum_{k=0}^{n-1}k\\[3mm] &=& y-d+d&&& \left(\displaystyle\sum_{k=0}^{n-1}k\right)=d\\[3mm] &=& y \end{array} \] \showoff \showoff \showoff In meiner Rechnung habe ich ein paar Aussagen hervorgehoben, die noch zu zeigen sind.
  1. Zu jedem \(y\in\mathbb{N}\) gibt es genau eine größte Dreieckszahl \(d\in\mathbb{N}\) mit \(d\leqslant y\).
  2. Zu jeder Dreieckszahl \(d\in\mathbb{N}\) gibt es genau ein \(n\in\mathbb{N}\) mit \(d=\displaystyle\sum_{k=0}^{n-1}k\).
Der Beweis für die zweite dieser Aussagen schreibt sich quasi von selbst hin; bei der ersten kannst du Induktion und das Maximalprinzip ("Jede endliche nichtleere Menge natürlicher Zahlen hat ein größtes Element") nutzen und das zum Beispiel mit Induktion nach der Anzahl der Elemente der Menge beweisen. Auch die Bedingung \(m\(\endgroup\)


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8113
Wohnort: Milchstraße
  Beitrag No.8, eingetragen 2022-12-08

Hallo, \quoteon(2022-12-08 10:20 - Moana in Beitrag No. 6) ich muss ja dann eine Fallunterscheidung machen. \[\text{Fall 1: } a_n - b_n = 1 \Rightarrow a_{n+1} = a_n + 1\; , \quad b_{n+1} = 0\] \[\text{Fall 2: } a_n - b_n > 1 \Rightarrow a_{n+1} = a_n\; , \quad b_{n+1} = b_n + 1\] \quoteoff Das ist genau der richtige Ansatz. Nach Induktionsvoraussetzung gilt \(\frac{a_n(a_n-1)}2+b_n=n\) mit \(a_n>b_n\) Fall 1: $a_n - b_n = 1$ Setze \(a_{n+1}=a_n+1\) und \(b_{n+1}=0\). Dann gilt \(a_{n+1}>b_{n+1}\) und \(\frac{a_{n+1}(a_{n+1}-1)}2+b_{n+1}=...=n+1\). Fall 2: $a_n - b_n > 1$ Setze \(a_{n+1}=a_n\) und \(b_{n+1}=b_n+1\). Dann gilt \(a_{n+1}>b_{n+1}\) und \(\frac{a_{n+1}(a_{n+1}-1)}2+b_{n+1}=...=n+1\). Ergänze jetzt noch die Pünktchen "...". Verwende dabei die Induktionsvoraussetzung.


   Profil
Moana
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 18.10.2007
Mitteilungen: 264
Wohnort: Berlin
  Beitrag No.9, vom Themenstarter, eingetragen 2022-12-08

Hallo thureduehrsen und StrgAltEntf, vielen lieben Dank für euren Input. Werde mir morgen alles in Ruhe zu Gemüte führen. Komme gerade erst von der Arbeit und bin erledigt. In diesem Sinne Gute Nacht 🤗 LG Moana


   Profil
Moana
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 18.10.2007
Mitteilungen: 264
Wohnort: Berlin
  Beitrag No.10, vom Themenstarter, eingetragen 2022-12-09

Hallo StrgAltEntf, danke, die Induktion hat nun gut geklappt, auch wenn ich noch mal um 2 Ecken denken musste, aber das hat noch funktioniert 😄 @thureduehrsen Wow, danke für deine Arbeit. Verwendest du hier die Dreieckszahlen, weil immer wenn \(n\) um eins erhöht wird und \(m\) auf Null zurückgesetzt wird \(y\) eine Dreieckszahl ist? Also bei \(0, 1, 3, 6, 10, \dots\)? Vielen Lieben Dank für eure Hilfe 🤗 LG Moana


   Profil
Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1302
Wohnort: Kiel, Deutschland
  Beitrag No.11, eingetragen 2022-12-09

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) \quoteon(2022-12-09 20:33 - Moana in Beitrag No. 10) Verwendest du hier die Dreieckszahlen, weil immer wenn \(n\) um eins erhöht wird und \(m\) auf Null zurückgesetzt wird \(y\) eine Dreieckszahl ist? Also bei \(0, 1, 3, 6, 10, \dots\)? \quoteoff Exakt deswegen tue ich das. 👍 Jetzt bin ich noch an deinem Beweis der Eindeutigkeit von \(m\) und \(n\) interessiert (bzw. von \(a_n\) und \(b_n\) in der Originalformulierung). mfg thureduehrsen \(\endgroup\)


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]