| |
| Autor |
 Vollständige Induktion mit Problemen |
|
Moana
Aktiv 
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 
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
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
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 
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 
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
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
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.
- Zu jedem \(y\in\mathbb{N}\) gibt es genau eine größte Dreieckszahl \(d\in\mathbb{N}\) mit \(d\leqslant y\).
- 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
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
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
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
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
|
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
