Problem mit vollständiger Induktion

[Matze1984]

Was mir gerade einfällt: wenn ich nun bei der vollständigen Induktion am Ende einach Blödsinn rausbekomme müsste das ja ein Hinweis dafür sein, dass es eben nicht für alle n gilt!
Wenn ich z.B. die Gleichung, die ich oben angegeben habe, einfach so weit es geht auflöse, bekomme ich raus:

$1 + ( n + 1 ) = -4n$

Und das ist ja nun nicht wirklich das gleiche... Also würde ich folgern, dass A(n+1) nicht für alle n gilt... Oder funktioniert das so nicht??

[Walli]

Matze1984 schrieb:

Also klar kann ich mir ne Zahl suchen, mit der es nicht klappt, aber ich möchte/muss es ja rechnerisch beweisen. Raten gäbe in der Klausur verhältnismäßig wenige Punkte

Wieso? Wenn da steht "Zeigen oder widerlegen sie..." dann reicht es ein Gegenbeispiel anzugeben.

[Daniel E.]

Da kann er bei der Aussage aber lang suchen, die ist nämlich richtig

Matze: Du sollst nicht A(n)=A(n+1) setzen, sondern aus A(n) auf A(n+1) schließen.

[Matze1984]

Naja gut. Trotzdem würde ich gerne wissen, wie ich das ganz rechnerisch beweisen kann. Schließlich wird mich so etwas spätestens in der Klausur wieder einholen... Und da hab ich dann ja nicht unbedingt sofort die Vermutung, dass die Sache so nicht hinhaut. Wäre also schön, wenn jemand rechnerisch eine Lösung oder Idee oder was auch immer hat

[Matze1984]

AH super, schon wieder ne Antwort
Ok, aber wie mache ich das? Meine Induktionsvorraussetzung ist eben (n-1)^2 + n + 40.
Aber wenn ich die Terme nicht gleichsetzen soll, was ist dann der erste Induktionsschritt? Da haperts dann gerade etwas

[Walli]

Mal überlegen... ich bin da momentan etwas eingerostet:
IV: (n-1)^2 + n + 40 sei prim für ein n

n -> n+1:

n^2 + n + 1 + 40 nun eine 0 addieren
= n^2 - 2n + 1 + 2n + n + 40
= ((n-1)^2 + n + 40) + 2n

der linke Teil vor dem + 2n ist also per I.V. prim. Nun müsstest du zeigen, dass der ganze Ausdruck auch prim ist.

Aber mal was anderes... die suchen doch immer nach größeren Primzahlen. Wenn die Aussage wirklich richtig ist, dann müsste man doch nur was beliebig großes da einsetzen. Oder liegt die Herausforderung dabei möglichst große Primzahlen einer bestimmten Gattung (z.B. Mersenne) zu finden?

[Daniel E.]

Ups, ich hab mich vertan, sorry. Natürlich ist der Ausdruck nicht für alle n prim ...

[Matze1984]

Genau, z.B. nicht für 567

Aber nun mal ganz langsam... Ein alter Grundkursler kommt bei sowas nicht so schnell mit ^^

Also ich setze erstmal n->n+1

$((n + 1) - 1)^2 + (n + 1) + 40$
$(n + 1)^2 + 1 + (n + 1) + 40$
$n^2 + 2n + 2 + (n + 1) + 40$
$n^2 + 2n + (n + 1) + 42$

Und dann? Eine 0 addieren? Das ist mir irgendwie neu...

[Jester]

Daniel E. schrieb:

Da kann er bei der Aussage aber lang suchen, die ist nämlich richtig

Matze: Du sollst nicht A(n)=A(n+1) setzen, sondern aus A(n) auf A(n+1) schließen.

Hast Du das empirisch durch Betrachtung der ersten 4 paar Zahlen ermittelt?

Generell stellt sich die Frage, wie man Primalität einer größeren auf die einer kleineren zurückführen soll... aber hier wird wirklich nur ein Gegenbeispiel benötigt. Man muß allerdings schon etwas weiter hinten in der Folge suchen. Für eine Klausur ist das sicher nicht geeignet (und auch etwas zu einfach).

@Matze: Wenn eine Aussage falsch ist und Du willst zeigen, daß sie falsch ist, dann ist das Gegenbeispiel ein Beweis für die Falschheit der Aussage. Wenn die Aussage nämlich wahr wäre dürfte es ja kein Gegenbeispiel geben.

MfG Jester

[Matze1984]

Das Problem ist ja, dass ich erst mal nicht weiß, ob die Aussage falsch oder wahr ist. Vielleicht sollte ich einfach den Gedanken abhaken, dass ganze per vollständiger Induktion beweisen/widerlegen zu wollen und mit ner anderen Methode an die Sache herangehen...

[Daniel E.]

Jester schrieb:

Daniel E. schrieb:

Da kann er bei der Aussage aber lang suchen, die ist nämlich richtig

Hast Du das empirisch durch Betrachtung der ersten 4 paar Zahlen ermittelt?

Hab mich an den Dirichlet-Satz falsch erinnert ...

[Walli]

Matze1984 schrieb:

Und dann? Eine 0 addieren? Das ist mir irgendwie neu...

Quadratische Ergänzung sagt dir sicher was. Da wird auch eine 0 addiert. Eine 0 addieren ist einfach ein Mittel um bestimmte Ausdrücke einfacher zusammenfassen zu können. Wenn ich z.B. irgendwo + x - x dazu addiere, dann habe ich nichts verändert, kann aber u.U. etwas vereinfachen.

[Matze1984]

Hmm.. Ich komm aber erst gar nicht so weit wie du:

IV: (n-1)^2 + n + 40 sei prim für ein n

n -> n+1:

Walli schrieb:

$n^2 + n + 1 + 40$ nun eine 0 addieren

Also wenn ich n durch n+1 ersetze wird das bei mir zu
$((n + 1) - 1)^2 + (n + 1) + 40$

Wenn ich da dann lustig Klammern auflöse, bleibt
$n^2 + 2n + 1 + 1 + (n + 1) + 40$
$= n^2 + 2n + (n + 1) +42$

und von dort aus komm ich irdendwie nicht auf

Walli schrieb:

$= n^2 - 2n + 1 + 2n + n + 40$
$((n-1)^2 + n + 40) + 2n$

[Jester]

Walli schrieb:

Oder liegt die Herausforderung dabei möglichst große Primzahlen einer bestimmten Gattung (z.B. Mersenne) zu finden?

Ne, Mersenne-Primzahlen lassen sich afaik besonders einfach nachweisen. Deshalb sind die so beliebt.

[Blue-Tiger]

Also wenns heisst "Beweise oder Wiederlege" und du "siehst" schon, dass das Ganze falsch ist, dann reicht wie schon gesagt ein Gegenbeispiel zum wiederlegen (tatsaechlich ist das ein sehr ueblicher Weg!). Also stress dich nicht mit dem Beweis. Du wirst im Semester noch genug andere Beweise sehen und machen, und langsam ein Gefuehl dafuer bekommen. Das hier nicht durch irgend welche logischen Ableitungen, sondern durch ein Gegenbeispiel zu beweisen ist das einzig sinnvolle (IMO). Und auch bei einer Klausur solltest du so und nicht anders rangehen!

Und besonders wenn du eh Informatik studierst sollte es doch echt kein Problem sein ein Gegenbeispiel zu finden

tom@(none):~$ python

>>> def isPrime(x):
...     for i in range(2, math.sqrt(x) + 1):
...             if x % i == 0:
...                     return False
...     return True

>>> def f(x):
...     return (x-1)**2 + x + 40

>>> for x in range(1, 100):
...     if not isPrime(f(x)):
...             print x
...             break
...
41

Ausserdem solltest du dir nochmal Induktionsbeweise anschauen. Weil damit zeigt man nur, dass wenn eine Aussage fuer ein n stimmt, es auch fuer das darauffolgende n stimmt.

[Walli]

Matze1984 schrieb:

Walli schrieb:

$n^2 + n + 1 + 40$ nun eine 0 addieren

Also wenn ich n durch n+1 ersetze wird das bei mir zu
$((n + 1) - 1)^2 + (n + 1) + 40$

So, und jetzt schau dir mal die erste Klammer an . (n+1-1)^2 ist n^2. Dann steht da das, was ich geschrieben habe.

[Matze1984]

Oh... Naja, es ist ja auch Wochenende...
ABer mit der quadratischen Ergänzung kann ich mich immer noch nicht so recht anfreunden... Kannst du mir dass mit dem addieren der 0 noch mal genauer aufschreiben/erläutern? Wäre 1a

[Walli]

Matze1984 schrieb:

Oh... Naja, es ist ja auch Wochenende...
ABer mit der quadratischen Ergänzung kann ich mich immer noch nicht so recht anfreunden... Kannst du mir dass mit dem addieren der 0 noch mal genauer aufschreiben/erläutern? Wäre 1a

Klar, also das ist im Prinzip recht einfach: wir haben

n^2 + n + 1 + 40

und wollen normalerweise irgendwie immer im Induktionsschritt die Induktionsvoraussetung einsetzen. Wir haben einmal die "+ 40" und das "+ n". Fehlt also nur noch ein (n-1)^2. Da können wir uns aber reinholen indem wir das n^2, die 1 anschauen und uns überlegen was noch fehlt um die 2. binomische Formel zu benutzen. Ein "- 2n" wäre nett. Also subtrahieren wir 2n und addieren es sofort wieder. Im Prinzip haben wir also nichts gemacht, nur eine 0 addiert (-2n+2n=0, klar). Nun steht da also:

n^2 + n + 1 + 40 - 2n + 2n

das ordnen wir etwas um und schon sieht man wo die 2. binomische Formel angewandt werden kann

(n^2 - 2n + 1) + 2n + n + 40
= (n-1)^2 + n + 40 + 2n

von dem Term vor dem "+ 2n" wissen wir aus der I.V., dass er prim ist. Allerdings ist der gesamte Ausdruck im Allgemeinen nicht prim. Also reicht es in dem Beispiel die Aussage durch Gegenbeispiel zum Widerspruch zu führen. Für andere Induktionsbeweise kann die Addition der 0 dennoch hilfreich sein. Es geht natürlich auch ohne. Die dazugedachte 0 ist einfach ein Hilfskonstrukt, damit man sich bei solchen Umformungen nicht unnötig verhaspelt.

[Matze1984]

Boa.. Wie billig ^^
Auf jeden Fall sehr nett von dir! Bekommst nen virtuellen Schmatzer
Wo ich mir das jetzt so durhcgelesen habe, glaube ich sorgar mich wieder daran zu erinnern... "Künstlerische 0" sagte mein Lehrer glaube ich immer dazu.
Auf jeden Fall vielen Dank für die zahlreichen Antworten!