Problem mit vollständiger Induktion



  • Hallo alle zusammen!

    Mein erstes Semester Informatik läuft. Super. Mehr oder weniger super finde ich ja Mathematik für Informatiker I, aber nützt ja nichts...;)
    Wir haben in der Vorlesung gerade die vollständige Induktion angeschnitten und ich sitze gerade an den Übungsaufgaben und komm da nicht so wirklich weiter.

    Also: Ich habe die Aussage A(n)

    nN:(n1)2+n+40isteinePrimzahl\forall n \in \mathbb N : ( n - 1 )^2 + n + 40 ist eine Primzahl

    gilt es zu beweisen oder zu widerlegen. Mir ist schon klar, dass das nicht stimmt, aber ich denke, das Argument wir der Übungsleiter nicht durchgehen lassen 😉

    Das wollte ich nun eigentlich mit Hilfe der vollst. Induktion machen... Der Infuktionsanfang ist ja auch nicht so das Problem:

    A(n)A(1)(1+1)2+1+40=41A(n)\Rightarrow A(1)\Rightarrow ( 1 + 1 )^2 + 1 + 40 = 41

    Sauber... 41 ist ne Primzahl... Um das zu erkennen reichen sogar meine bescheidenen Methematikkentnisse ^^
    Meine Induktionsvoraussetzung ist dann eben, dass A(n) eben eine Primzahl ist..
    Ich hatte mir nun gedacht, dass wenn die Aussage für A(n) richtig ist, sie ja auch für A(n+1) richtig sein muss... Erfolgserlebnis 😃
    Also setze ich im Induktionsschritt A(n+1)=A(n):

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

    So... Nun weiß ich aber nicht so wirklich, wie ich weiterrechnen soll bzw. ob der Induktionsschritt so überhaupt richtig ist. Wäre schön, wenn mir jemand weiterhelfen könnte 🙂

    Mfg,
    Matze

    PS: Vollständige Induktion muss nicht der Lösungsweg sein. Wenn jemand das anders lösen kann bin ich auch dankbar 😃



  • Moment mal, A(n) ist die Aussage, daß das eine Primzahl ist. Nicht die Terme selbst müssen gleich sein.

    Aber eigentlich liegt das Problem wo ganz anders: Du vermutest doch, daß das nicht stimmt. Mit vollständiger Induktion versuchst Du aber das zu beweisen. Das wird natürlich kaum funktionieren. Schließlich ist die Vermutung ja, daß es falsch ist. Widerlegen kann man eine solche Aussage ganz einfach indem man ein (nur ein einziges) Gegenbeispiel angibt.

    Such also ein n, sodaß (n-1)^2+n+40 keine Primzahl ist und Du bist fertig.



  • Hmm... Ja ok, das ist wohl ein Denkfehler ^^
    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 😉
    Ich könnte es ja auch anders rechnerisch beweisen, so mit nem indirekten Beweis oder so. Falls mit jemand nen Tipp geben könnte wie das läuft...?! 🙂



  • 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)=4n1 + ( 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??



  • 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.



  • 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.



  • 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 🙂



  • 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 😉



  • 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?



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



  • 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) - 1)^2 + (n + 1) + 40
    (n+1)2+1+(n+1)+40(n + 1)^2 + 1 + (n + 1) + 40
    n2+2n+2+(n+1)+40n^2 + 2n + 2 + (n + 1) + 40
    n2+2n+(n+1)+42n^2 + 2n + (n + 1) + 42

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



  • 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



  • 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...



  • 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 ...



  • 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.



  • 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:

    n2+n+1+40n^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((n + 1) - 1)^2 + (n + 1) + 40

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

    und von dort aus komm ich irdendwie nicht auf

    Walli schrieb:

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



  • 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.



  • 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.



  • Matze1984 schrieb:

    Walli schrieb:

    n2+n+1+40n^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((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.



  • 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 🙂


Anmelden zum Antworten