matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieVollständige Induktion
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Zahlentheorie" - Vollständige Induktion
Vollständige Induktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Vollständige Induktion: Idee
Status: (Frage) beantwortet Status 
Datum: 14:16 Mo 20.07.2015
Autor: m8sar6l1Uu

Aufgabe
Zeige, dass der Bruch [mm] \bruch{21n + 4}{14n + 3} [/mm] für alle n [mm] \in \IN [/mm] nicht kürzbar ist.


Wie kann man das mittels vollständiger Induktion beweisen?

Ich bin mir bewusst, dass andere Beweismethoden schneller und eleganter sind, um dieses Problem zu lösen. Ich bin mir aber nicht ganz sicher, wie man es mit Hilfer vollständiger Induktion löst.

Man zeigt es für n = 0 [mm] \Rightarrow [/mm] gcd(4, 3) = 1.
Man nimmt gcd(21n + 4, 14n + 3) = 1 an und zeigt, dass daraus

gcd(21(n+1) + 4, 14(n+1) + 3) = 1 folgt.

Wie macht man weiter?

        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 15:35 Mo 20.07.2015
Autor: abakus


> Zeige, dass der Bruch [mm]\bruch{21n + 4}{14n + 3}[/mm] für alle n
> [mm]\in \IN[/mm] nicht kürzbar ist.

>

> Wie kann man das mittels vollständiger Induktion
> beweisen?

>

> Ich bin mir bewusst, dass andere Beweismethoden schneller
> und eleganter sind, um dieses Problem zu lösen. Ich bin
> mir aber nicht ganz sicher, wie man es mit Hilfer
> vollständiger Induktion löst.

>

> Man zeigt es für n = 0 [mm]\Rightarrow[/mm] gcd(4, 3) = 1.
> Man nimmt gcd(21n + 4, 14n + 3) = 1 an und zeigt, dass
> daraus

>

> gcd(21(n+1) + 4, 14(n+1) + 3) = 1 folgt.

>

> Wie macht man weiter?

Hallo,
zu zeigen, dass etwas für alle n NICHT gilt, ist nicht gerade ein sinnvolles Anwendungsgebiet für Induktionsbeweise.
Was mir als einzige Möglichkeit einfällt:
Beweise mit vollst. Ind., dass für alle n gilt 
[mm]2>\bruch{21n + 4}{14n + 3}>1,5.[/mm]

Gruß Abakus

Bezug
                
Bezug
Vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:35 Mo 20.07.2015
Autor: tobit09

Hallo abakus!


>  zu zeigen, dass etwas für alle n NICHT gilt, ist nicht
> gerade ein sinnvolles Anwendungsgebiet für
> Induktionsbeweise.

Auch ich scheitere daran, hier einen "sinnvollen" Induktionsbeweis zu finden.
Ich denke aber nicht, dass sich negierte Aussagen grundsätzlich nicht für Induktionsbeweise eignen.

(Beispielsweise lässt sich der Satz, dass jede nichtleere Teilmenge [mm] $A\subseteq\IN$ [/mm] ein kleinstes Element besitzt wie folgt beweisen:
Man zeigt, dass jede Teilmenge [mm] $A\subseteq\IN$ [/mm] ohne kleinstes Element schon die leere Menge ist, indem man per Induktion nach n zeigt: Für alle [mm] $n\in\IN$ [/mm] gilt NICHT, dass es ein [mm] $m\le [/mm] n$ mit [mm] $m\in [/mm] A$ gibt.)


>  Was mir als einzige Möglichkeit einfällt:
>  Beweise mit vollst. Ind., dass für alle n gilt 
>  [mm]2>\bruch{21n + 4}{14n + 3}>1,5.[/mm]

Die rechte Ungleichung ist z.B. für n=1 falsch.

Vor allem aber sehe ich nicht, was uns diese Ungleichungen für den gesuchten Nachweis bringen.


Viele Grüße
Tobias

Bezug
        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 16:24 Mo 20.07.2015
Autor: M.Rex

Hallo.

> Zeige, dass der Bruch [mm]\bruch{21n + 4}{14n + 3}[/mm] für alle n
> [mm]\in \IN[/mm] nicht kürzbar ist.

>

> Wie kann man das mittels vollständiger Induktion
> beweisen?

Ist das explizit per vollständiger Induktion angefordert?
Denn dann schließe ich mich mal abakus an, das ist kein geeignetes Verfahren für die Nicht-Existenz.


>

> Ich bin mir bewusst, dass andere Beweismethoden schneller
> und eleganter sind, um dieses Problem zu lösen. Ich bin
> mir aber nicht ganz sicher, wie man es mit Hilfer
> vollständiger Induktion löst.

>

> Man zeigt es für n = 0 [mm]\Rightarrow[/mm] gcd(4, 3) = 1.
> Man nimmt gcd(21n + 4, 14n + 3) = 1 an und zeigt, dass
> daraus

>

> gcd(21(n+1) + 4, 14(n+1) + 3) = 1 folgt.

>

> Wie macht man weiter?

Ich würde den Bruch aufteilen:

[mm] \frac{21n+4}{14n+3} [/mm]
[mm] =\frac{14n+3+7n+1}{14n+3} [/mm]
[mm] =\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3} [/mm]
[mm] =1+\frac{7n+1}{14n+3} [/mm]

Nun wieder du.

Marius

Bezug
                
Bezug
Vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:45 Mo 20.07.2015
Autor: tobit09

Hallo Marius!


> Ich würde den Bruch aufteilen:
>  
> [mm]\frac{21n+4}{14n+3}[/mm]
>  [mm]=\frac{14n+3+7n+1}{14n+3}[/mm]
>  [mm]=\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3}[/mm]
>  [mm]=1+\frac{7n+1}{14n+3}[/mm]
>  
> Nun wieder du.

Wieder sehe ich nicht, wie uns das weiter bringt.

Zu zeigen ist, dass $21n+4$ und $14n+3$ teilerfremd sind.
Ich erkenne keinen wirklichen Zusammenhang zur rationalen Zahl

     [mm] $\frac{21n+4}{14n+3}=\frac{2*(21n+4)}{2*(14n+3)}$, [/mm]

die sich in gekürzter und ungekürzter Form darstellen lässt.


Viele Grüße
Tobias

Bezug
                
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:06 Mo 20.07.2015
Autor: m8sar6l1Uu


> Hallo.
>  
> Ist das explizit per vollständiger Induktion angefordert?
>  Denn dann schließe ich mich mal abakus an, das ist kein
> geeignetes Verfahren für die Nicht-Existenz.

Nein, ist es nicht. Ich wollte es bloß als Übung strikt mit vollständiger Induktion machen.

>Ich würde den Bruch aufteilen:
>
>$ [mm] \frac{21n+4}{14n+3} [/mm] $
>$ [mm] =\frac{14n+3+7n+1}{14n+3} [/mm] $
>$ [mm] =\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3} [/mm] $
>$ [mm] =1+\frac{7n+1}{14n+3} [/mm] $
>
>Nun wieder du.

[mm] $1+\frac{7n+1}{14n+3} [/mm] = [mm] 1+\frac{7n+1}{2(7n+1) + 1} [/mm] $ ?

Da der Nenner immer um 1 größer ist als das doppelte des Zählers, kann es kein $n$ geben, sodass der Bruch gekürzt wird.

Aber wie hilft mir das für eine Vollständige Induktion?

Bezug
                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 17:28 Mo 20.07.2015
Autor: tobit09

Hallo m8sar6l1Uu!


> > Ist das explizit per vollständiger Induktion angefordert?

  

> Nein, ist es nicht. Ich wollte es bloß als Übung strikt
> mit vollständiger Induktion machen.

Ergebnis des Versuches, diese Aussage sinnvoll mit Induktion zu beweisen ist offenbar, dass es unabhängig voneinander 4 Leute (du, ich, abakus und M.Rex) nicht geschafft haben.
Das deutet daraufhin, dass kein "naheliegender" "sinnvoller" Induktionsbeweis existiert.

Induktion ist eben nicht bei jeder Aussage über alle natürlichen Zahlen das Mittel der Wahl.



> >Ich würde den Bruch aufteilen:
> >
>  >[mm] \frac{21n+4}{14n+3}[/mm]
>  >[mm] =\frac{14n+3+7n+1}{14n+3}[/mm]
>  >[mm] =\frac{14n+3}{14n+3}+\frac{7n+1}{14n+3}[/mm]
>  
> >[mm] =1+\frac{7n+1}{14n+3}[/mm]
>  >
>  >Nun wieder du.
>
> [mm]1+\frac{7n+1}{14n+3} = 1+\frac{7n+1}{2(7n+1) + 1}[/mm] ?
>  
> Da der Nenner immer um 1 größer ist als das doppelte des
> Zählers, kann es kein [mm]n[/mm] geben, sodass der Bruch gekürzt
> wird.

Mich überzeugt die Begründung noch nicht: Warum sind für alle [mm] $m\in\IN$ [/mm] die Zahlen $m$ und $2m+1$ teilerfremd?

Zu zeigen ist also, dass jede natürliche Zahl [mm] $k\in\IN$, [/mm] die sowohl $m$ als auch $2m+1$ teilt, schon $k=1$ erfüllt.

Gelte also $k|m$ und $k|2m+1$.
Zu zeigen ist $k=1$.

Wegen $k|2m+1$ und $k|m$ gilt auch $k|(2m+1)-m$, also $k|m+1$.
Zusammen mit $k|m$ folgt daraus $k|(m+1)-m$, also $k|1$.

Bekanntlich (?) folgt somit $k=1$.


Damit ist gezeigt, dass $7n+1$ und $2(7n+1)+1$ teilerfremd sind.
Zu zeigen ist in der ursprünglichen Aufgabenstellung jedoch, dass $21n+4$ und $14n+3$ teilerfremd sind.

Gehe dazu (ohne Induktion) ähnlich vor wie ich es dir für das Beispiel mit $m$ und $2m+1$ vorgemacht habe.


> Aber wie hilft mir das für eine Vollständige Induktion?

Marius wollte offenbar einen Weg ohne Induktion beginnen.

Wie gesagt: Anscheinend lässt sich diese Aufgabe gar nicht in naheliegender Weise sinnvoll per Induktion lösen.


Viele Grüße
Toiias

Bezug
                                
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:53 Mo 20.07.2015
Autor: m8sar6l1Uu

Wie wäre es mit einem Widerspruchsbeweis stattdessen?

Angenommen es gebe einen gemeinem Faktor $m > 1$, der beide Terme teilt.

Dann muss gelten:

$ (21n+4) [mm] \equiv [/mm] 0 $ (mod m)
$ (14n+3) [mm] \equiv [/mm] 0 $ (mod m)

Dann muss nach gelten:

$ (2*(21n+4)) [mm] \equiv [/mm] 2*0 $ (mod m)
$ (3*(14n+3)) [mm] \equiv [/mm] 3*0 $ (mod m)

$ (42n+8) [mm] \equiv [/mm] 0 $ (mod m)
$ (42n+9) [mm] \equiv [/mm] 0 $ (mod m)

Und daraus wiederum:

$ ((42n+9) - (42n+8)) [mm] \equiv [/mm] (0-0) $ (mod m)

$ 1 [mm] \equiv [/mm] 0 $ (mod m) [mm] \gdw [/mm] $m = 1$ .

Also gibt es keinen Faktor $m > 1$, der beide Terme teilt. Also ist der Bruch nicht kürzbar.

Bezug
                                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 17:54 Mo 20.07.2015
Autor: tobit09


> Wie wäre es mit einem Widerspruchsbeweis stattdessen?
>  
> Angenommen es gebe einen gemeinem Faktor [mm]m > 1[/mm], der beide
> Terme teilt.
>  
> Dann muss gelten:
>  
> [mm](21n+4) \equiv 0[/mm] (mod m)
>  [mm](14n+3) \equiv 0[/mm] (mod m)
>
> Dann muss nach gelten:
>  
> [mm](2*(21n+4)) \equiv 2*0[/mm] (mod m)
> [mm](3*(14n+3)) \equiv 3*0[/mm] (mod m)
>
> [mm](42n+8) \equiv 0[/mm] (mod m)
> [mm](42n+9) \equiv 0[/mm] (mod m)
>  
> Und daraus wiederum:
>  
> [mm]((42n+9) - (42n+8)) \equiv (0-0)[/mm] (mod m)
>  
> [mm]1 \equiv 0[/mm] (mod m) [mm]\gdw[/mm]  [mm]m = 1[/mm] .
>  
> Also gibt es keinen Faktor [mm]m > 1[/mm], der beide Terme teilt.
> Also ist der Bruch nicht kürzbar.

Sehr schön! [ok]

Bezug
                                                
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:36 Mo 20.07.2015
Autor: sinnlos123

und warum nicht m>0 ?
hängt das damit zusammen, das beim teilen eh alles >1 alles <1 nur invers darstellt?

Bezug
                                                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 02:26 Di 21.07.2015
Autor: m8sar6l1Uu


> und warum nicht m>0 ?

Wenn wir zeigen wollen, dass ein Bruch [mm] $\frac{a}{b}$ [/mm] nicht kürzbar ist, heißt das, dass der größte gemeinsame Teiler von $a$ und $b$, gcd($a$, $b$), gleich 1 ist.

Zum Beispiel: [mm] $\frac{2}{4}$ [/mm] ist noch weiter kürzbar, weil der gcd(2, 4) = 2. Man kann also beide Zahlen noch durch die Zahl 2 dividieren.

Hingegen ist [mm] $\frac{1}{2}$ [/mm] nicht weiter kürzbar, da 1 und 2 nur noch die Zahl 1 als geimeinsamen Teiler haben. Aber einen Bruch mit 1 zu kürzen ist sinnlos, da sich an dem Bruch selbst dadurch nichts ändert.

Wenn es also eine Zahl $m$ gebe, die den Zähler und den Nenner gleichzeitig teilt UND größer als 1 ist, dann ist der Bruch kürzbar. Gleichheit mit 1 funktioniert immer.


Bezug
                                                                
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 02:32 Di 21.07.2015
Autor: sinnlos123

meine frage ziehlte auf 0<m<1 ab

Bezug
                                                                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 02:33 Di 21.07.2015
Autor: m8sar6l1Uu

$m$ ist ein Teiler einer Zahl und Teiler sind nur ganze Zahlen.

Bezug
                                                                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 09:13 Di 21.07.2015
Autor: M.Rex

Hallo

Wenn eine Zahl z ein Teiler einer anderen Zahl z ist, gibt es ein [mm] n\in\IN [/mm] für die gilt [mm] $z=n\cdot [/mm] t$

Das die Zahl n aus den natürlichen Zahlen ist, ist wichtig, da ohne diese Einschränkung jede Zahl ein Teiler von jeder anderen Zahl wäre, da in [mm] \IR [/mm] die Gleichung [mm] $z=n\cdot [/mm] t$ immer nach n auflösbar ist.

Marius

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]