Matroids Matheplanet Forum Index
Forumbereich moderiert von: mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Induktion » Alternativer Lösungsansatz für Induktionsbeispiel.
Druckversion
Druckversion
Antworten
Antworten
Universität/Hochschule Alternativer Lösungsansatz für Induktionsbeispiel.
Spedex Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 19.03.2020, Mitteilungen: 381, aus: f(x=0)=1/x
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-10-19

Hallo, es soll bewiesen werden, dass für \(n\geq4\) gilt \(n!>2^n\).

Dabei bin ich beim Tüfteln beim Induktionsschritt auf folgenden möglichen Beweis gekommen.
Induktionsannahme:
\[n!>2^n\] Induktionsschritt:
\[z.z.:\left(n+1\right)!>2^{n+1}\] \[z.z.:n!\cdot\left(n+1\right)>2^n\cdot2\] Aus der Annahme wissen wir ja, dass \(n!>2^n\), daher muss gelten:
\[n!\cdot\left(n+1\right)>2^n\cdot\left(n+1\right)\] \[z.z.:2^n\cdot\left(n+1\right)>2^n\cdot2\] \[z.z.:n+1>2\] Da \(n\geq4\) gilt \(5>2\).

Nun frage ich mich, ob das so zulässig ist?

Nachträglich habe ich im Internet geschaut und folgende Lösung gefunden:
\[n!>2^n|\cdot\left(n+1\right)\] \[n!\cdot\left(n+1\right)>\left(n+1\right)\cdot2^n\] Da \(n\geq4\)
\[n!\cdot\left(n+1\right)>5\cdot2^n>2\cdot2^n\] \[\left(n+1\right)!>2^{n+1}\]
LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 18.01.2019, Mitteilungen: 5320, aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-10-19

Hallo Spedex,

hast du gut gemacht. 👍

Der Beweis aus dem Internet ist der gleiche wie deiner, nur zielführender aufgebschrieben (in dem Sinn, dass unnötiges vermieden wurde).

Das ist ja auch etwas von den Dingen, die man erst lernen muss. D.h., unter anderem bearbeitest du diese Aufgaben ja, um so etwas zu lernen, vielleicht auch mit der Zeit so etwas wie einen eigenen "Stil" beim Verfassen von Beweisen zu finden.


Gruß, Diophant



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Spedex Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 19.03.2020, Mitteilungen: 381, aus: f(x=0)=1/x
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, vom Themenstarter, eingetragen 2020-10-19

Top. Danke dir.
LG



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kuestenkind Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 12.04.2016, Mitteilungen: 1853
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, eingetragen 2020-10-19

Huhu,

ich finde das nicht so schön zu lesen und präferiere immer eine Kette:

\(\displaystyle (n+1)!=n!(n+1)\stackrel{IV}{>}2^n(n+1)>2^n\cdot 2=2^{n+1}\quad \checkmark\)

Gruß,

Küstenkind



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 09.06.2019, Mitteilungen: 538, aus: Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, eingetragen 2020-10-19

Hallo Spedex,

Dein Tüfteln hat zum gewünschten Ziel geführt, könnte Dir jedoch in der Form und bei Bewertung im Hinblick auf "formal korrekte vollständige Induktion" Punktabzüge einbringen ;)

Zunächst hast für keinen konkreten "Induktionsanfang"  \(n_0\)  die Richtigkeit der Aussage gezeigt!

\(n\,\geqq\,4\:\Rightarrow\: n_0\, =\,4\) :
\(n_0!\: =\:4!\: =\:24 \: >\:16\: =\:2^4\: =\:2^{n_0}\)
\(\Rightarrow\) Die Aussage stimmt für Induktionsanfang  \(n_0\, =\,4\) !

Den ersten Induktionsschritt hast Du dann genau richtig gemacht, nämlich in die bestehende, "formeltechnische" Aussage  \((n+1)\)  statt  \(n\)  einzusetzen und dann[!] durch Umwandlung die Richtigkeit zu zeigen!
Da finde ich das, was Du im Internet gefunden hast, weniger geradlinig, weil dort "zum Wunsch hin" und nicht "vom Wunsch her" umgewandelt wird.
Ist wohl eine Geschmacksfrage...

Aber:
Für Deinen Schritt  "\(2^n\,\cdot\,(n+1)\: >\:2^n\,\cdot\,2
\)"  hätte man uns seinerzeit im Studium wohl mindestens einen halben Punkt für "mangelnde Sorgfalt" abgezogen, denn  "\(2^n\,\cdot\,(n+1)\: \geqq\:2^n\,\cdot\,2\)"  würde ausreichen! Genau wie dann  "\((n+1)\:\geqq\:2\)"  im abschließenden nächsten Schritt.
Mag sich nach "Korinthenkackerei" anhören... Im strengen Sinn ist es jedoch nicht von der Hand zu weisen, denn es genügt ja für die Gesamtabschätzung, dass an einer Stelle ein "\(>\)" (ohne Einschränkung) steht, irgendwo[!] links davon das "\((n+1)!\)", und irgendwo[!] rechts davon das "\(2^{(n+1)}\)".
Bei abschätzenden Vergleichsketten etwa im Rahmen von Grenzwertbetrachtungen kann das sehr wohl bedeutsam sein - stets so "vorsichtig" wie möglich abschätzen!

Ich würde es so machen:
\((n+1)!\: =\: n!\,\cdot\, (n+1)\:\geqq\: n!\,\cdot\, (n_0+1)\: =\: n!\,\cdot\,5\: >\:2^n\,\cdot\,5\: >\:2^n\,\cdot\,2\: =\:2^{(n+1)}\)


-----------------

ODERINT DUM NERVOS NE VEXENT!




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kezer Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 04.10.2013, Mitteilungen: 1041
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, eingetragen 2020-10-19

2020-10-19 18:57 - cramilu in Beitrag No. 4 schreibt:
Für Deinen Schritt  "\(2^n\,\cdot\,(n+1)\: >\:2^n\,\cdot\,2
\)"  hätte man uns seinerzeit im Studium wohl mindestens einen halben Punkt für "mangelnde Sorgfalt" abgezogen, denn  "\(2^n\,\cdot\,(n+1)\: \geqq\:2^n\,\cdot\,2\)"  würde ausreichen!

Dann hättest du dich damals gerne beschweren können, denn offenbar ist die Aussage $2^n (n+1) > 2^n \cdot 2$ stärker als die Aussage $2^n (n+1) \geq 2^n \cdot 2$. Das hat nichts mit mangelnder Sorgfalt zu tun.


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Spedex Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 19.03.2020, Mitteilungen: 381, aus: f(x=0)=1/x
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, vom Themenstarter, eingetragen 2020-10-19

Hey, bezüglich des Induktionsanfangs:
Den habe ich natürlich schon gemacht, nur nicht hier rein geschrieben, um Zeit zu sparen. Am DIN A4 Blatt steht er auf jeden Fall.

Das mit den größer-gleich und größer verstehe ich. Reicht ja aus, wenn es einmal da steht, danach passt auch größer-gleich.
Darauf habe ich nicht geachtet, bereitet mir als Leihe aber auch nicht allzu große Bauchschmerzen.

Zu dem Beweis vom Internet: Mir kam das so vor, als hätte die Person davor das "vom Wunsch her" gemacht, nach dem Finden der Lösung dann so umgestellt / umgeschrieben / umüberlegt, dass es schlussendlich nach "zum Wunsch hin" ausschaut.
"Zum Wunsch hin" kommt man allerdings meiner Meinung nach deutlich schlechter drauf, wenn man noch nichts in der Hand hat, aber ich bin ja auch kein Profi.

Danke für den Hinweis.
LG

[Die Antwort wurde nach Beitrag No.4 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.04.2016, Mitteilungen: 4989, aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.7, eingetragen 2020-10-23

Hier ein Beweis, der ohne Induktion auskommt und die Ungleichung zugleich herleitet. Man startet mit

$n! = n \cdot (n-1) \cdots \cdot 5 \cdot 4 \cdot 3 \cdot 2$

und klammert die $4$ aus (beachte $n \geq 4$). Es verbleiben $n-2$ Zahlen ($n,n-1,\dotsc,5,3,2$), die jeweils $\geq 2$ sind, und mindestens eine ist $>2$. Also ist

$n! > 4 \cdot 2^{n-2} = 2^n.$

PS: Siehe article.php?sid=1737 für mehr Beispiele dieser Art.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Red_ Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.09.2016, Mitteilungen: 823, aus: Erde
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.8, eingetragen 2020-10-23

2020-10-19 19:04 - Kezer in Beitrag No. 5 schreibt:
2020-10-19 18:57 - cramilu in Beitrag No. 4 schreibt:
Für Deinen Schritt  "\(2^n\,\cdot\,(n+1)\: >\:2^n\,\cdot\,2
\)"  hätte man uns seinerzeit im Studium wohl mindestens einen halben Punkt für "mangelnde Sorgfalt" abgezogen, denn  "\(2^n\,\cdot\,(n+1)\: \geqq\:2^n\,\cdot\,2\)"  würde ausreichen!

Dann hättest du dich damals gerne beschweren können, denn offenbar ist die Aussage $2^n (n+1) > 2^n \cdot 2$ stärker als die Aussage $2^n (n+1) \geq 2^n \cdot 2$. Das hat nichts mit mangelnder Sorgfalt zu tun.

Das erinnert mich an einen Korrektor (Numeriker), der mir angestrichen hat, dass eine bestimmte Ungleichung \(X \geq Y\) falsch sei. Dann hat er es durch \(X > Y\) ersetzt. Das blieb natürlich nicht unbeantwortet von mir...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 09.06.2019, Mitteilungen: 538, aus: Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.9, eingetragen 2020-10-24

@Triceratops:
Deine Beweisführung ist fraglos eleganter als per "vollständiger Induktion", und dem Tenor des zitierten Artikels stimme ich voll und ganz zu!
Zu "meiner Zeit" durften wir auch in Klausuren noch geschweifte Klammern unter Teiltermen anbringen und dort Eigenschaften vermerken... Keine Ahnung, ob solches heute auch noch akzeptiert wird.

Demnach:

\(n!\: =\: n\, ×\, (n-1)\, ×\, (n-2)\, ×\: ...\: ×\,5\, ×\,4\, ×\,3\, ×\,2\: =\: ...\)   [Kommutativgesetz]
\(...\: = \: n\, ×\, (n-1)\, ×\, (n-2)\, ×\: ...\: ×\,5\, ×\,3\: ×\,4\, ×\,2\: =\: ...\)
[unter dem linken Teil bis "...×3" denken wir uns ab da eine
geschweifte Klammer mit Eigenschaftskommentar "(n-3) Faktoren"]

\(...\: = \: n\, ×\, (n-1)\, ×\, (n-2)\, ×\: ...\: ×\,5\, ×\,3\: ×\,8\: =\: ...\)
\(...\: = \: n\, ×\, (n-1)\, ×\, (n-2)\, ×\: ...\: ×\,5\, ×\,3\: ×\,2^3\: >\: ...\)   [\(n\geq 4\)]
\(...\: > \: 2×2×2×...×2\: ×\,2^3\: =\: 2^{(n-3)}\: ×\,2^3\: =\: 2^n\)
Hattest Du Dir das so gedacht? Finde ich todschick ;)


-----------------

ODERINT DUM NERVOS NE VEXENT!




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 02.12.2013, Mitteilungen: 231
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.10, eingetragen 2020-10-25

2020-10-23 22:39 - Triceratops in Beitrag No. 7 schreibt:
Hier ein Beweis, der ohne Induktion auskommt und die Ungleichung zugleich herleitet. Man startet mit

$n! = n \cdot (n-1) \cdots \cdot 5 \cdot 4 \cdot 3 \cdot 2$


Das ist auch ein Induktionsbeweis, die Induktion bzw. Rekursion ist nur in der ...-Schreibweise versteckt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 05.04.2020, Mitteilungen: 192
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.11, eingetragen 2020-10-25

2020-10-25 17:48 - Zwerg_Allwissend in Beitrag No. 10 schreibt:
Das ist auch ein Induktionsbeweis, die Induktion bzw. Rekursion ist nur in der ...-Schreibweise versteckt.

Nein, hier ist kein Induktionsschritt der Form A(n) --> A(n+1) vorhanden; es handelt sich um einen einfachen direkten Beweis.

Gern auch formal:

$n!=\prod_{k=1}^n k=n \cdot \prod_{k=2}^{n-1} k \geq 4 \cdot \prod_{k=2}^{n-1} 2 =4 \cdot 2^{n-2}=2^n.$



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 02.12.2013, Mitteilungen: 231
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.12, eingetragen 2020-10-25

2020-10-25 17:57 - Ixx in Beitrag No. 11 schreibt:
2020-10-25 17:48 - Zwerg_Allwissend in Beitrag No. 10 schreibt:
Das ist auch ein Induktionsbeweis, die Induktion bzw. Rekursion ist nur in der ...-Schreibweise versteckt.

Nein, hier ist kein Induktionsschritt der Form A(n) --> A(n+1) vorhanden; es handelt sich um einen einfachen direkten Beweis.

Gern auch formal:

$n!=\prod_{k=1}^n k=n \cdot \prod_{k=2}^{n-1} k \geq 4 \cdot \prod_{k=2}^{n-1} 2 =4 \cdot 2^{n-2}=2^n.$

Der Beweis ist völlig OK, einfach und problemlos nachvollziehbar. Es geht nur um die Behauptung "ohne Induktion". Um diese Behauptung zu beweisen wäre ein formaler Beweis ohne Induktion notwendig. Allein die Behauptung $\prod_{k=1}^n k=n \cdot \prod_{k=2}^{n-1} k$ (obwohl einleuchtend) kann ohne Induktion nicht bewiesen werden. Man scheitert schon an der Definition von $\prod_{k=1}^n k$ (mangels Rekursionsprinzip). Man sieht die Erfordernis von Induktion, wenn man den Beweis in einem formalen Kalkül nachvollziehen will. Nun ist das oft ein formaler Overkill, und so führt man einen umgangssprachlichen Beweis bei dem die Induktion (scheinbar) verschwunden ist.  

Wer das bezweifelt möge einen Beweis von $\prod_{k=1}^n k=n \cdot \prod_{k=2}^{n-1} k$ in (irgendeinem) Kalkül 1. Stufe angeben.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.04.2016, Mitteilungen: 4989, aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.13, eingetragen 2020-10-25

@Zwerg_Allwissend: Das ist klar, dass man die Grundrechenregeln erst einmal per Induktion bewiesen haben muss. Danach kann man sie aber benutzen und muss nicht "jedes mal erneut" sich einen Induktionsschritt überlegen, sondern kann einfach intuitiv rechnen. Insofern ist keine Induktion mehr nötig. Ich verweise für die Details auf den bereits verlinkten Artikel article.php?sid=1737 . Dort wird das Missverständnis sehr genau aufgelöst.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend Aktiv Letzter Besuch: im letzten Monat
Mitglied seit: 02.12.2013, Mitteilungen: 231
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.14, eingetragen 2020-10-25

2020-10-25 20:02 - Triceratops in Beitrag No. 13 schreibt:
@Zwerg_Allwissend: Das ist klar, dass man die Grundrechenregeln erst einmal per Induktion bewiesen haben muss. Danach kann man sie aber benutzen und muss nicht "jedes mal erneut" sich einen Induktionsschritt überlegen, sondern kann einfach intuitiv rechnen. Insofern ist keine Induktion mehr nötig.

Dem stimme ich sofort zu. Ich denke nur, daß die Behauptung "ohne Induktion" für viele Anfänger (die wir ja auch mal waren) verwirrend sein kann. Und zu dem Mißverständnis führen kann, daß solch ein Beweis allein mit Mitteln 1. Stufe geführt werden kann.  



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Spedex hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2020 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]