Beweis n² > n (u.a.) direkt (Induktion)

03.09.2015, 17:49

Sascharrr

Beweis n² > n (u.a.) direkt (Induktion)

Edit (mY+): Titel modifiziert.

Meine Frage:
Ich hänge derzeit vor einer Aufgabe in der ich beweisen soll (mittels eines direkten Beweises), dass n² > n ist. Ich habe mir schon tausende Skripte und Videos zum Thema angeschaut, aber es hat noch nicht richtig Klick gemacht. Ich bin auch nicht der Meinung, dass meine Ansätze die Behauptung beweisen. Daher möchte ich euch um Hilfe bitten.

Die Aufgabe Lautet: Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n, n > 1, gilt: n² > n.

Gruß
Sascha

Meine Ideen:
Mein derzeitiger Lösungsweg sieht folgendermaßen aus:
Voraussetzung: n?N ^ n > 1
Behauptung: n² > n

n² > n =>
=> n > n/n =>
=> n > 1

Ein weiterer Gedanke (das habe ich mir aus Beispielaufgaben, zum Thema, im Internet abgeschaut):
Voraussetzung: n?N ^ n > 1 => n = k+1
Behauptung: n² > n

(k+1)² > k+1 =>
k²+2k+1 > k+1 =>
k(k+2) > k =>
k+2 > 1

03.09.2015, 18:05

Gast11022013

Auf diesen Beitrag antworten »

Das was du da versucht anzuwenden ist die sogenannte vollständige Induktion.

Wenn du dir zu dem Thema bisher nicht explizit etwas durchgelesen hast, dann solltest du das nachholen.
Danach ist es wahrscheinlich kein Problem mehr diese Aufgabe zu lösen.

Aber warum machst du auch sonst diesen Schritt mit n=k+1

Stelle um

n^2-n>0

nun begründe warum das was auf der linken Seite steht,stets positiv ist.
Stelle es als Produkt dar.

03.09.2015, 18:30

Sascharrr

Auf diesen Beitrag antworten »

Ich habe im Zusammenhang mit direkten Beweisen gesehen, dass n mit 2k gleichgesetzt wurde, da n immer eine gerade Zahl sein sollte. Dann wurde umgestellt. Das habe ich mir so abgeschaut und versucht auf es auf diese Aufgabe anzuwenden. - Da n immer größer als 1 sein sollte habe ich mir gedacht n ist jetzt gleich k+1, mit k als Element aller natürlichen Zahlen.

n² > n => n²-n > 0 => n(n-1) > 0
Da vorausgesetzt wird, dass n immer größer als 1 ist, ist ausgeschlossen, dass einer der beiden Terme 0 wird, also auch niemals deren Produkt.

Hätte ich nicht theoretisch auch sagen können, dass eine Zahl mit sich selbst multipliziert niemals =< die Zahl selbst ist? Mit Ausnahme bei der 1, welche jedoch ausgeschlossen wurde.

Danke für die schnelle Hilfe smile

Gruß
Sascha

03.09.2015, 18:41

Gast11022013

Auf diesen Beitrag antworten »

Zitat:

n² > n => n²-n > 0 => n(n-1) > 0
Da vorausgesetzt wird, dass n immer größer als 1 ist, ist ausgeschlossen, dass einer der beiden Terme 0 wird, also auch niemals deren Produkt.

Besser ist wenn du sagst, dass beide Faktoren also n und (n-1) immer positiv sind.
Daher ist dann auch das Produkt immer positiv.
Das n-1>0 liegt daran, dass n>1 ist.

Zitat:

Hätte ich nicht theoretisch auch sagen können, dass eine Zahl mit sich selbst multipliziert niemals =< die Zahl selbst ist? Mit Ausnahme bei der 1, welche jedoch ausgeschlossen wurde.

Naja, das wäre halt kein Beweis, weil du ja gerade das hier zeigen möchtest.
Das was du theoretisch sagen möchtest ist zwar richtig, aber dann kannst du ja auch theoretisch was falsches sagen und mit der gleichen "Argumentation" ankommen.
$\begin{eqnarray*} n\leq n^2 \end{eqnarray*}$ gilt übrigens auch für n=1. Für die strikte Ungleichung $\begin{eqnarray*} n<n^2 \end{eqnarray*}$ ist das anders.

Zitat:

Natürlich kannst du n umschreiben, wenn es dir hilft.
Dann ist n=k+1 mit k>0

Wenn es dir hilft kannst du es gerne machen. Es ist aber nicht notwendig.
Aufpassen müsstest du hier, dass für manche die kleinste natürliche Zahl die Null ist und für andere wiederum die Null keine natürliche Zahl ist.

Wenn du schreibst, dass n=k+1 für alle natürliche Zahlen gilt, dann müsstest du vielleicht vorher sagen, dass die Null für dich keine natürliche Zahl ist.

Edit:

Übrigens hast du oben nicht versucht die vollständige Induktion anzuwenden.
Das habe ich beim ersten durchlesen falsch interpretiert.
Du kannst dir die vollständige Induktion aber trotzdem mal ansehen und versuchen die Aufgabe damit zu lösen.

03.09.2015, 19:32

URL

Auf diesen Beitrag antworten »

Verwende $\begin{eqnarray*} kn=\underbrace{n+n+\ldots +n}_{\mbox{k Summanden}} \end{eqnarray*}$

03.09.2015, 19:41

Sascharrr

Auf diesen Beitrag antworten »

Das n = k+1 war nur ein gequälter Versuch, irgendwie auf ein vernünftiges Ergebnis zu kommen. Die Vorgehensweise scheint hier ja nicht so toll zu funktionieren und hat mich auch eher verwirrt.

Die vollständige Induktion werde ich mir auch direkt nach den indirekten Beweisen anschauen, doch hänge ich jetzt erst dort fest.
Ich habe mir ein Video angeschaut und meine es sogar verstanden zu haben, doch kann ich auch hier wieder das gelernte nicht auf die Aufgabe anwenden, die vor mir liegt.

Kannst du mir einen Tipp geben, für die folgende Aufgabe?:
Ich soll beweisen/widerlegen, dass für jede natürliche Zahl 𝑛 die Zahl 𝑛²+𝑛+41 eine Primzahl ist. Ich weiß, dass es bei n=41 nicht der Fall ist, wie auch bei jedem Vielfachen von 41. Ich habe nur keine Ahnung, wie ich es über den indirekten Weg beweise.

Mein Ansatz:
Voraussetzung: n∈N
Behauptung: n²+n+41 = Primzahl

Ab hier weiß ich nicht mal mehr weiter und habe auch keine Ahnung ob ich die Behauptung richtig ist.

Kennt jemand eine gute Lektüre zur Mengenlehre und Beweismethoden, am besten mit vielen Aufgaben, samt Lösung und Erklärung. Das würde mir echt helfen, da ich selbst bisher nichts gefunden habe, was mir gefiel.

@URL
Leider kann ich damit nichts anfangen, kannst du mir auf die Sprünge helfen?

03.09.2015, 19:47

Gast11022013

Auf diesen Beitrag antworten »

Du möchtest also beweisen oder wiederlegen, dass

n^2+n+41 immer eine Primzahl ist.

Naja, wenn du für n=41 keine Primzahl erhältst, dann hast du doch deine Lösung.

n^2+n+41 ist nicht immer eine Primzahl.

Du hast ein Gegenbeispiel angegeben. Und das reicht aus.

Zitat:

Ich habe mir ein Video angeschaut und meine es sogar verstanden zu haben, doch kann ich auch hier wieder das gelernte nicht auf die Aufgabe anwenden, die vor mir liegt.

Es ist bei solchen Sachen nicht mehr wie in der Schule wo man ein bestimmtes Muster hatte und dieses dann immer und immer wieder anwendet.
Viele Aufgaben brauchen verschiedene Lösungen.

03.09.2015, 20:14

Sascharrr

Auf diesen Beitrag antworten »

Also könnte ich schreiben:
Für mindestens ein n, als Element von N, gilt: n²+n+41 = k, k als kein Element von P
daraus folgt: n=41: n²+n+41 = 1763
Das Gegenbeispiel ist wahr, denn 1763 ist keine Primzahl. Folglich ist die Behauptung, dass für jedes n als Element von N: n²+n+41 eine Primzahl ist, falsch.
(Ich habe hier auf die Zeichen verzichtet, da ich im Formeleditor das "nicht Element von"-Zeichen nicht gefunden habe und nicht wieder wirres Zeugs anstelle der Zeichen stehen haben will)

Ich hatte drüber nachgedacht, war mir aber sicher, dass es zu einfach ist und nicht als indirekter Beweis zählt.

Wenn ich die erste Aufgabe auf indirektem Wege beweisen/widerlegen will, ist dann folgendes richtig?:

Voraussetzung: n als Element von N, n > 1
Behauptung: n²> n

n als Element von N, n > 1: -(n ²> n) => (n² =< n) => (n(n-1) =< 0)
Da n>1 als Voraussetzung dient, sind die Faktoren n und (n-1) stets positiv. Daraus folgt, dass das Produkt auch stets positiv ist.

Wäre das richtig?

03.09.2015, 20:50

mYthos

Auf diesen Beitrag antworten »

Das ist nicht die Vorgangsweise für eine vollständige Induktion.
Du musst die Richtigkeit der Behauptung erst für n = 2 (die erste natürliche Zahl größer als 1) abtesten:

$\begin{eqnarray*} 2^2 > 2 \end{eqnarray*}$

Dies ist offenbar richtig.

Nun kommt der Schluss von n auf (n + 1):
Induktionsannahme, die Behauptung sei richtig für n: $\begin{eqnarray*} n^2 > n \end{eqnarray*}$
Daraus ist dann die Richtigkeit für n+1 zu beweisen, also

$\begin{eqnarray*} (n+1)^2 > n + 1 \end{eqnarray*}$

Kannst du dies nun - unter Verwendung der Induktionsannahme $\begin{eqnarray*} n^2 > n \end{eqnarray*}$ - zeigen?

mY+

03.09.2015, 21:07

Sascharrr

Auf diesen Beitrag antworten »

Voraussetzung: n als Element von N, n > 1
Behauptung: n² > n

n² > n => n²-n > 0 => n(n-1) > 0
Da n eine natürliche Zahl und stets größer 1 ist, ist es ausgeschlossen, dass einer der Faktoren (n v (n-1)) negativ oder 0 ist, weshalb auch das Produkt der beiden Faktoren stets größer als 0 sein wird.

(n+1)² > n+1 => n²+2n+1 > n+1 => n(n+1) > 0
Da n eine natürliche Zahl ist, ist ausgeschlossen, dass einer der Faktoren negativ oder 0 ist, weshalb auch das Produkt der beiden Faktoren größer als 0 ist.

Korrekt so?

Weil ich an den ersten beiden Vorkursen nicht teilgenommen habe und mir das Skript nicht besonders viel Aufschluss über die genaue Vorgehensweise gibt, bin ich immer unsicher, ob ich das ganze richtig formuliert habe. Freue mich daher über jede Kritik.

Wie sieht das eigentlich mit meinem letzten Beitrag aus, ist das alles korrekt?

03.09.2015, 21:26

mYthos

Auf diesen Beitrag antworten »

Ja, so passt es.
Du warst eigentlich schon am Ziel, mit:

$\begin{eqnarray*} n^2 + 2n + 1 > n + 1 \end{eqnarray*}$

$\begin{eqnarray*} \to \end{eqnarray*}$

$\begin{eqnarray*} n^2 + n > 0 \end{eqnarray*}$

und das ist - offensichtlich wegen n > 0 - für alle natürlichen Zahlen erfüllt (mittels der Positivität der Faktoren stimmt das natürlich ebenfalls)

mY+

P.S.:
Welcher anderer Beitrag? Die Frage über die Primzahlenmenge ist unleserlich (wegen gedankenlosem cut 'n' paste)
Indirekter Beweis: Man zeigt, dass das Gegenteil wahr ist. Bereits ein einziges Gegenbeispiel macht die Behauptung zunichte.

03.09.2015, 22:03

Dopap

Auf diesen Beitrag antworten »

@sascharr: wenn \in bekannt ist, was könnte dann \notin bedeuten ?

03.09.2015, 22:30

URL

Auf diesen Beitrag antworten »

Mir ist nicht klar, warum hier ein Induktionsbeweis bemüht werden soll. Im ursprünglichen Threadtitel stand nur etwas von direktem Beweis verwirrt

Mit $\begin{eqnarray*} n^2=nn=\underbrace{n+n+\ldots +n}_{\mbox{n Summanden}}\geq n+n>n+1>n \end{eqnarray*}$ ist schon alles erledigt.
Bin weg.

03.09.2015, 22:32

Sascharrr

Auf diesen Beitrag antworten »

Super, danke für eure Hilfe smile

. Das hat mir schon einiges gebracht, jetzt muss ich es nur noch etwas vertiefen.

Diese Aufgaben meinte ich:

1. Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n, n > 1, gilt: n² > n.
Voraussetzung: $\begin{eqnarray*} \forall n\in N, n > 1 \end{eqnarray*}$
Behauptung: $\begin{eqnarray*} n² > n \end{eqnarray*}$

Mittels direktem Beweis:
$\begin{eqnarray*} n\in N,n > 1: n²>n => n²-n>0 => n(n-1)>0 \end{eqnarray*}$
Da für alle n gilt, dass sie natürliche Zahlen und größer als 1 sind, sind beide Faktoren immer positiv, sowie das daraus folgende Produkt. Die Behauptung ist deshalb wahr.

Mittels indirektem Beweis:
$\begin{eqnarray*} n\in N,n > 1: n² \leq n => n²-n \leq 0 => n(n-1) \leq 0 \end{eqnarray*}$
Da für alle n gilt, dass sie natürliche Zahlen und größer als 1 sind, sind beide Faktoren immer positiv, sowie das daraus folgende Produkt. Da das Gegenbeispiel falsch ist, ist die Behauptung wahr.

Beim indirekten Weg frage ich mich, ob das $\begin{eqnarray*} \forall \end{eqnarray*}$ auch negiert werden muss. Währe nur ziemlich schwer zu beweisen, oder?

2. Beweisen oder widerlegen Sie, das für jede natürliche Zahl n die Zahl n²+n+41 eine Primzahl ist.
Voraussetzung: $\begin{eqnarray*} \forall n\in N \end{eqnarray*}$
Behauptung: $\begin{eqnarray*} k = n²+n+41, k\in P \end{eqnarray*}$

Mittels indirektem Beweis:
$\begin{eqnarray*} \exists n\in \mathbb N, n=41: k=n^{2}+n+41, k \notin P => k=41^{2}+41+41 => k=1763 \end{eqnarray*}$
Das Gegenbeispiel ist wahr, da für n=41 das Ergebnis k=1763 keine Primzahl ist. Folglich ist die Behauptung falsch

Edit (mY+): Ich habe für dich den Fehler 42 -> 41 editiert!

Hier negiere ich das $\begin{eqnarray*} \forall \end{eqnarray*}$ ja auch, obwohl ich es der Voraussetzung zugeordnet habe. Ist das vielleicht falsch?

03.09.2015, 22:47

mYthos

Auf diesen Beitrag antworten »

Der Beweis mittels Induktion war als Option zu betrachten, welche Sascha ja auch in seinen Ideen versucht hat. Freilich geht es auf direktem Wege noch einfacher.

Der Zwischenschritt $\begin{eqnarray*} .. \geq n + n > n + 1 > .. \end{eqnarray*}$ kann auch entfallen, denn es ist offensichtlich, dass gilt

$\begin{eqnarray*} n + n + n + \ ... + n > n \ [\forall n \geq 2] \end{eqnarray*}$

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

@Sascha, wo kommen plötzlich die 42 her?

Die Teilbarkeit durch 41 ist offensichtlich, weil 41 überall als Faktor enthalten ist, da brauchst du nicht auf 1763 aufzumultiplizieren!

mY+

03.09.2015, 22:50

Sascharrr

Auf diesen Beitrag antworten »

Zitat:

Original von mYthos
@Sascha, wo kommen plötzlich die 42 her?

Die Teilbarkeit durch 41 ist offensichtlich, weil 41 überall als Faktor enthalten ist, da brauchst du nicht auf 1763 aufzumultiplizieren!

mY+

Das sollte 41 sein, ich ändere es sofort.

EDIT: Kann ich nicht mehr ändern, weil der Beitrag schon 15min alt ist

Zitat:

Original von Dopap
@sascharr: wenn \in bekannt ist, was könnte dann \notin bedeuten ?

Danke, habs.

03.09.2015, 22:54

mYthos

Auf diesen Beitrag antworten »

OK, dann stimmt es.
Durch das Gegenbeispiel ist die Behauptung (, dass sie für ALLE n gilt, ) widerlegt.
------
Den direkten Beweis der ersten Frage hast du nun auch verstanden?

P.S.: Den Schreibfehler in deinem Beitrag habe ich editiert.

mY+

03.09.2015, 23:04

Dopap

Auf diesen Beitrag antworten »

formal etwa so :

Behauptung : $\begin{eqnarray*} \mathop{\bigwedge}\limits_{ n \in N}n^2+n+41 \in P \end{eqnarray*}$

Negation: $\begin{eqnarray*} \mathop{\bigvee}\limits_{ n \in N}n^2+n+41 \notin P \end{eqnarray*}$

ist für n=41 wahr, demnach ist...

03.09.2015, 23:20

Sascharrr

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Mir ist nicht klar, warum hier ein Induktionsbeweis bemüht werden soll. Im ursprünglichen Threadtitel stand nur etwas von direktem Beweis verwirrt

Mit $\begin{eqnarray*} n^2=nn=\underbrace{n+n+\ldots +n}_{\mbox{n Summanden}}\geq n+n>n+1>n \end{eqnarray*}$ ist schon alles erledigt.
Bin weg.

Okay, jetzt habe ich es verstanden. Da ärgert man sich, nicht von selbst drauf gekommen zu sein. Danke dafür und gute Nacht.

Zitat:

Original von mYthos
OK, dann stimmt es.
Durch das Gegenbeispiel ist die Behauptung (, dass sie für ALLE n gilt, ) widerlegt.
------
Den direkten Beweis der ersten Frage hast du nun auch verstanden?

mY+

Ja das habe ich verstanden und die Formulierung scheint ja auch richtig zu sein.
Muss halt nur noch ein paar Aufgaben mehr machen

Das Einzige, was mir noch nicht klar ist, ob ich $\begin{eqnarray*} \forall und \exists \end{eqnarray*}$ nun auch negieren muss.

Zitat:

Original von Dopap
formal etwa so :

Behauptung : $\begin{eqnarray*} \mathop{\bigwedge}\limits_{ n \in N}n^2+n+41 \in P \end{eqnarray*}$

Negation: $\begin{eqnarray*} \mathop{\bigvee}\limits_{ n \in N}n^2+n+41 \notin P \end{eqnarray*}$

ist für n=41 wahr, demnach ist...

Die beiden "Dächer" kenne ich noch nicht, gelten die auch als eine Negierung oder was sagen die beiden aus?

03.09.2015, 23:54

Dopap

Auf diesen Beitrag antworten »

ja, das ist die saubere math. Darstellung, die jeweilige Menge steht unten

ersteres hat breite Basis = forall
letzteres eine Spitze nach unten = exists

gut lesbare Darstellung , vor allem bei etwas komplizierteren Aussagen.

" muss ich $\begin{eqnarray*} \forall \quad \text{und} \quad \exists \end{eqnarray*}$ negieren" :

versteh ich nicht. Es heisst doch : für alle ... gilt.

04.09.2015, 00:22

mYthos

Auf diesen Beitrag antworten »

Zitat:

Original von Sascharrr
...
Das Einzige, was mir noch nicht klar ist, ob ich $\begin{eqnarray*} \forall und \exists \end{eqnarray*}$ nun auch negieren muss.
...

Beim indirekten Beweis ist die Aussage zu negieren, bzw. deren Gegenteil als wahr zu beweisen. Das kann zwangsläufig auch eine Änderung der Quantoren zur Folge haben.
Das Gegenteil von 'für alle ... gilt' wird wohl als 'nicht für alle .. gilt' oder möglicherweise auch 'für alle .. gilt nicht' interpretiert werden können.
Wenn behauptet wird, eine Aussage gilt für alle natürlichen n und vermutet wird, sie ist unzutreffend, ist in einem Gegenbeispiel ein n zu finden, für das die Aussage nicht bzw. die negierte Aussage gilt.
Das Gegenbeispiel muss nicht für alle n gelten, es genügt bereits ein einziges.

Existenz und Nichtexistenz schliessen ebenfalls einander aus.

mY+

04.09.2015, 00:29

Sascharrr

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
ja, das ist die saubere math. Darstellung, die jeweilige Menge steht unten

ersteres hat breite Basis = forall
letzteres eine Spitze nach unten = exists

gut lesbare Darstellung , vor allem bei etwas komplizierteren Aussagen.

" muss ich $\begin{eqnarray*} \forall \quad \text{und} \quad \exists \end{eqnarray*}$ negieren" :

versteh ich nicht. Es heisst doch : für alle ... gilt.

So wie ich das verstanden habe negiert man die Behauptung beim indirekten Beweis. Ich meine aber beim Lernen gesehen zu haben, dass jemand $\begin{eqnarray*} \forall ... \end{eqnarray*}$ in der Voraussetzung stehen hatte, in seinem Gegenbeispiel aber $\begin{eqnarray*} \exists ... \end{eqnarray*}$ .

So, wie ich das auch in der Aufgabe mit den Primzahlen gemacht habe.

04.09.2015, 00:50

mYthos

Auf diesen Beitrag antworten »

Ich habe meinen vorigen Beitrag entsprechend editiert, du kannst dies nochmals durchlesen.
Die Quantoren "für alle" (ALL) und "es gibt" (EXIST) schließen einander NICHT aus, also das eine ist nicht Gegenteil des anderen.

mY+

04.09.2015, 01:26

Dopap

Auf diesen Beitrag antworten »

@sascharrr: das stimmt so.

bei meiner Negation wird ja auch aus forall ein exists.

schauen wir nochmals deine post an:

Zitat:

Mittels indirektem Beweis:
$\begin{eqnarray*} \exists n\in \mathbb N, n=41: k=n^{2}+n+41, k \notin P => k=41^{2}+41+41 => k=1763 \end{eqnarray*}$
Das Gegenbeispiel ist wahr, da für n=41 das Ergebnis k=1763 keine Primzahl ist. Folglich ist die Behauptung falsch

das ist ein wenig durcheinander, die Behauptung fehlt ( soll man sich wohl dazu denken ) k ist nicht notwendig, die Voraussetzung steht in der Behauptung integriert. Ich würde es mit den anderen Symbolen wiefolgt notieren:

Behauptung:
$\begin{eqnarray*} \forall n \in \mathbb N : n^2+n+41 \in P \end{eqnarray*}$

Negation : $\begin{eqnarray*} \exists n \in \mathbb N : n^2+n+41 \notin P \end{eqnarray*}$

was z.B. mit n=41 richtig ist. Demnach ( nach dem Satz des ausgeschlossenem Dritten ) ist die Behauptung wahr. q.e.d

gewöhne dir gleich etwas Formalismus an, das ist für später nie verkehrt.

Bemerkung: das \exists bedeutet "mindestens ein" und nicht "genau ein"

Neue Frage »

Antworten »

Beweis n² > n (u.a.) direkt (Induktion)

Verwandte Themen