Inhaltsangabe Verbergen

3 Wie beweist man die Teilbarkeit mit Hilfe der vollständigen Induktion?

Was du lernen wirst

In diesem Beitrag lernst du, wie man die Teilbarkeit mit Hilfe der vollständigen Induktion beweist.
Also Aussagen wie $A(n): n^2 + n$ ist durch 2 teilbar. Dabei gehe ich davon aus, dass dir bereits die Grundlagen der vollständigen Induktion bekannt sind. Falls das nicht der Fall ist, kannst du diese in folgendem Beitrag auffrischen:

Was du mit damit anfangen kannst

Wenn du verstehst, wie man die Teilbarkeit mit Hilfe der vollständigen Induktion beweist, dann kannst du eine gute Note schreiben und es für den Rest deines Lebens wieder vergessen.

Es gibt bei allen Arten von Induktionsbeweisen(Ungleichungen, Teilbarkeit, Summenformen) ein Merkmal, was es unterscheidet. Auf dieses Merkmal weise ich immer in den Beiträgen hin! (siehe unten)

Wie beweist man die Teilbarkeit mit Hilfe der vollständigen Induktion?

Ich gehe davon aus, dass dir die Schritte der vollständigen Induktion bereits bekannt sind. Falls nicht, hier hast du eine kleine Zusammenfassung des Ablaufs:

Induktionsanfang(Wir beweisen, dass die Aussage für die kleinste Zahl wahr ist.)
Induktionsschritt(Wir beweisen, dass die Aussage auch für alle Zahlen über dem Startwert gilt.)
1. Induktionsvoraussetzung formulieren(Wir schreiben aus, dass unsere Annahme für ein $n$ gültig ist.)
2. Induktionsbehauptung formulieren(Wir formulieren unser Ziel, und zwar, dass wenn es für ein beliebiges $n$ gilt, es auch für das darauf folgende $n+1$ gilt.)
3. Beweis des Induktionsschrittes(Unter Verwendung der Annahme formen wir solange um, bis wir die Form der Behauptung erreichen.)

Klausurtipp

Die ersten drei Schritte(Induktionsanfang, -voraussetzung, -behauptung) sind einfach, damit kannst du immer Punkte sammeln.

Ich werde das Konzept an einem einfachen Beispiel erklären und anschließend noch ein schwereres Beispiel zeigen:

Beweise mit Hilfe der vollständigen Induktion, dass folgende Aussage gilt.

$A(n): n^2 + n$ ist gerade $\hspace{0.5cm} \forall n \hspace{0.1cm} \epsilon \hspace{0.1cm} \mathbb{N}$

Kleine Randinformation: In dem Beweis, würdest du höchstens Abkürzungen wie (IA) = Induktionsanfang, (IV) = Induktionsvoraussetzung, (IB) = Induktionsbehauptung, (IS) = Induktionsschritt verwenden. Text gehört ebenfalls zur Beweisführung dazu.

Die Definition der Teilbarkeit lautet:
Eine ganze Zahl $b$ teilt eine ganze Zahl $a$ genau dann, wenn es eine ganze Zahl $n$ gibt, für die $a = b \cdot n$ gilt.

(IA)

$A(1):$
$1^2 + 1$
$= 1 + 1$
$= 2$
$= 2(1)$

(IV)

Die Aussage $A(n)$ gilt für ein beliebiges, aber festes $n$ .
$A(n): n^2 + n = 2k$

(IB)

Wenn $A(n)$ gilt, dann gilt auch $A(n+1)$ .
$A(n+1): (n+1)^2 + (n+1)$ ist gerade $\hspace{0.5cm} \forall n \hspace{0.1cm} \epsilon \hspace{0.1cm} \mathbb{N}$

(IS)

$(n+1)^2 + (n+1)$
$= n^2 + 2n + 1 + n + 1$
$= n^2 + 3n + 2$
$= n^2 + n + 2n + 2$
$= (n^2 + n) + 2n + 2$
$= 2k + 2n + 2$
$= 2(k + n + 1)$

Quod erat demonstrandum.

(IA)

Da es nur für alle natürlichen Zahlen gelten soll, setzen wir für $n = 1$ ein.
Je nachdem wie der Lehrer es definiert, kann es auch sein das die 0 enthalten sein muss. Dann würdet ihr hier für $n$ eine 0 einsetzen.
Der letzte Teil ( $2(1)$ ) kommt dir womöglich unnötig vor, denn am vorhergehenden Schritt ( $2$ ) kann man bereits erkennen, dass es durch 2 teilbar ist. Dennoch füge ich das hier hinzu, denn das Ausklammern des Teilers ist das Kernmerkmal beim Beweisen der Teilbarkeit, mit dieser Methode.

(IV)

In der Regel ein einfacher Satz, dass die Aussage gilt. Falls man die Induktionsvoraussetzung in der Klausur braucht, sollte man ihn auswendig kennen.
Die Darstellung $n^2 + n = 2k$ sollte hier unbedingt stehen, da sie uns später von Nutzen sein wird.

(IB)

Wir formulieren unsere Behauptung und schreiben einmal $A(n+1)$ auf. Dafür setzen wir für $n$ einfach $n+1$ ein.

(IS)

Das Ziel ist es ein Glied zu erzeugen, das so aussieht wie der Term in deiner Voraussetzung, hier ist das $n^2+n$ , damit wir ihn später ersetzen können.

Wir starten mit der Prämisse $(n+1)^2 + (n+1)$ .
Dann lösen wir die Klammern auf, die Linke mit der 1. Binomischen Formel, die Rechte fällt einfach weg.
Vereinfachen.
Zerlegen von $3n$ in $n$ und $2n$ , warum siehst du im nächsten Schritt.
Jetzt kann ich $(n^2 + n)$ klammern, weil es genau der Term aus der Voraussetzung ist, und ich weiß das dieser durch 2 teilbar is, daher kann ich ihn gleich mit $2k$ ersetzen.
ersetzen von $(n^2 + n)$ mit $2k$ .
Ausklammern unseres gesuchten Teilers(in diesem Fall die 2).
Profit.

Bei dieser Methode ist das Ziel, irgendwo im Term den gleichen Term wie in der Voraussetzung zu bilden, sodass ich ihn mit der Darstellung der Teilbarkeit ersetzen kann.

Wie du dir den Term aus der Voraussetzung im Induktionsschritt baust, kommt auf die Aufgabe an. Manchmal kann es sein das du einfach ergänzen musst(also aus z.b $(6^n)$ einfach $(6^n - 1 + 1)$ machst, weil du die Form $(6^n - 1)$ mit deiner Darstellung der Teilbarkeit ersetzen willst. Dafür will ich dir folgendes Beispiel zeigen:

Beweise mit Hilfe der vollständigen Induktion, dass folgende Aussage gilt.

$A(n): 6^n - 1$ ist durch 5 teilbar $\hspace{0.5cm} \forall n \hspace{0.1cm} \epsilon \hspace{0.1cm} \mathbb{N}$

(IA)

$A(1):$
$6^1 - 1$
$= 6-1$
$= 5$
$= 5(1)$

(IV)

Die Aussage $A(n)$ gilt für ein beliebiges, aber festes $n$ .
$A(n): 6^n - 1 = 5k$

(IB)

Wenn $A(n)$ gilt, dann gilt auch $A(n+1)$ .
$A(n+1): 6^{n+1} - 1$ ist teilbar durch 5 $\hspace{0.5cm} \forall n \hspace{0.1cm} \epsilon \hspace{0.1cm} \mathbb{N}$

(IS)

$6^{n+1} - 1$
$= 6 ( 6^n ) - 1$
wir können $6^{n+1}$ auch als $6 ( 6^n )$ darstellen.
$= 6 ( 6^n - 1 + 1) -1$
hier ergänze ich die $-1$ , um die gleiche Form zu erhalten wie in unserer Voraussetzung!
$= 6 ( 5k + 1) -1$
jetzt ersetze ich die $6^n - 1$ mit $5k$ , denn wir haben bereits gezeigt, das es durch 5 teilbar ist.
$= 30k + 6 - 1$
$= 30k + 5$
$= 5(6k + 1)$
Gesuchten Teiler Ausklammern, um zu zeigen, dass es ein Teiler von dem Term in der Klammer ist!

Quod erat demonstrandum.

Sowas sehe ich gar nicht!!!

An einigen stellen des Induktionsschrittes hast du womöglich gedacht:

Sowas sehe ich nicht! Wie kommt man da drauf?
Someone on the Internet

Das ist vollkommen in Ordnung. Entspann dich einfach. Mach Übungen, schau dir die Lösungswege an. Nach einiger Zeit siehst du auch, wo du was ergänzen kannst, wo du klammern solltest, wo du eine Binomische Formel hast, oder faktorisieren musst. Alles eine Frage der Übung.

Zusammenfassung

Kurz gesagt, unterscheidet sich der Induktionsbeweis der Teilbarkeit nur im Induktionsschritt und der Voraussetzung. In der Voraussetzung macht es Sinn, die Teilbarkeit darzustellen $(a = bn)$ . Dann müssen wir nur noch unseren Term umformen und uns den Term aus der Voraussetzung bilden, sodass wir ihn dann mit der Darstellung der Teilbarkeit ersetzen können. Anschließend wird der Teiler ausgeklammert, um eindeutig zu zeigen, dass der gesamte Term durch den Teiler in der Aussage teilbar ist.

Übungen

Really nice: Aufgabensammlung, zu Beweisen mit Vollständiger Induktion, mit ausführlichen Lösungen

Hat dir der Inhalt gefallen?

Falls du mehr zu Themen der Informatik lesen willst, kannst du die Suche dafür verwenden:

Du bist der Meinung, das war der Beste Beitrag zum Thema Informatik den du jemals gelesen hast? Dann ist die einzig logische Schlussfolgerung, diesen Beitrag mit deinen Kommilitonen zu teilen. Oder auch nicht mach was du willst, ich bin nicht dein Dad.

Teilbarkeit mit vollständiger Induktion beweisen

Was du lernen wirst

Was du mit damit anfangen kannst

Wie beweist man die Teilbarkeit mit Hilfe der vollständigen Induktion?

Klausurtipp

Sowas sehe ich gar nicht!!!

Zusammenfassung

Übungen

Hat dir der Inhalt gefallen?

Kommentar verfassen Kommentieren abbrechen