Beweisen Sie die folgenden Aussagen mittels vollständiger Induktion:

Question

die Aufgabe ist folgende:
Beweisen Sie die folgenden Aussagen mittels vollständiger Induktion:

(a) Sei q Element der reellen Zahlen ohne die 1, dann gilt für alle n größer gleich 0:
∑ⁿ_i=0 qⁱ = (1 - qⁿ⁺¹) / (1 -q)"
Mein Ansatz: Für A(1) zeigen und dann für A(n+1) zeigen, also umformen.
Sollte dieser richtig sein, wäre eine Lösung überflüssig.

(b) Jede nitchleere Teilmenge A von ℕ₀ besitz ein kleinstes Element.
Mein Gedanken: A ist schon einmal eine Menge mit Objekten. Innerhalb dieser
Menge muss also ein bestimmtes n existieren, welches das kleinste Element
ist. Wie ich dies nun mathematisch beweisen kann, fällt mir einfach nicht ein.

Florian T. S. :-)

Comments

Was meinst du mit "...wäre eine Lösung überflüssig"?

---

Also, dass ich weiß wie ich umformen müssten wenn mein Ansatz stimmt :-)

Verwirrung sorgt bei mir die Aufgabe b) :-/

---

PS: Ansatz sollte A(0) sein, da ja ohne die eins :-D

---

Achso ok. a) kann man übrigens auch direkt zeigen ohne Induktion.

Nein der Ausschluss von 1 ist auf \(q\) bezogen nicht auf \(n\)!

---

Ups, falsch gelesen!

Den direkten Beweis könnte ich als zusätzliche Übung mal versuchen :-)

Könntest du mir eventuell bitte für b) einen Ansatz geben? Ich würde es gerne ohne
die Lösung probieren. Theoretisch könnte ich ja sagen:
"Sei x Element der Menge A, dann ist auch x Element der Menge N da
A eine Teilmenge von N ist. Da A eine nichtleere Menge ist, muss ein
kleinstes x in A existieren." Nur wie ich jetzt zeige, dass es ein kleinstes
gibt, bereitet mir Schwierigkeiten..

---

Ja mach das mal der ist wesentlich kürzer (fast ein Einzeiler).

Wenn es wirklich darum geht b) direkt per Induktion zu zeigen, dann wird das aber nur für alle endlichen Teilmengen klappen (dabei machst du eine Induktion über die Anzahl der Elemente der Teilmenge). Sollen auch unendliche Teilmengen betrachtet werden, so kannst du das auch schön per Widerspruch zeigen.

---

Ich schreibe dir mal mein bisheriges Ergebnis auf:

Sei A eine nichtleere Teilmenge von ℕ₀. Weiterhin sei A eine Menge mit
endlich vielen Elementen m. Daraus folgt, dass m < n gilt und das alle m
Element von A sind.

A = {m ∈ A | m < n}, als Beispiel: A = {0, 1, 2, ..., n-1}.
Doch wie soll ich nun per Induktion zeigen, dass 0 das kleinste Element ist?

Ein Ansatz wäre eventuell: ∑^n-1_i=1 n-1. Für A(1) = 0. Doch mit was soll ich
die Summe vergleichen, mit der Menge A würde ja keinen Sinn machen,
da steht schließlich schon auf der linken Seite.

---

Eigentlich kannst du das ganze komplett wieder vergessen, aber ich versuch dir mal aufzuzeigen was für eine Käse da steht:

Sei A eine nichtleere Teilmenge von ℕ₀. Weiterhin sei A eine Menge mit 
endlich vielen Elementen m.

Ok.

 Daraus folgt, dass m < n gilt 

Aha wo kommt aufeinmal \(n\) her und warum gilt das?

das alle m 
Element von A sind. 

??? Ich dachte \(m\) ist die Anzahl der Elemente von \(A\) warum soll das jetzt Element sein und was meinst du mit alle "\(m\)"?

A = {m ∈ A | m < n}, als Beispiel: A = {0, 1, 2, ..., n-1}. 
Doch wie soll ich nun per Induktion zeigen, dass 0 das kleinste Element ist? 

Das passt gar nicht. Es geht darum allgemeine Teilmengen zu betrachten nicht nur die Teilmengen von 0 bis irgendeiner Zahl. Erst an dieser Stelle wird auch klar was du vorher mit deinem Absatz gemeint hast. Das ist keine sinnvolle Ordnung.

Ein Ansatz wäre eventuell: ∑^n-1_i=1 n-1. Für A(1) = 0. 

Warum aufeinmal eine Summe? Was berechnest du da?

-> Wie du siehst ist das ganze sehr verwirrend. 

Der Induktionsanfang ist, dass du zeigst, dass eine beliebige ein-elementige Teilmenge der natürlichen Zahlen ein Minimum besitzt (was ja recht trivial ist).

---

Ich denke mal wieder zu kompliziert. Sobald ich vollständige Induktion sehe, verbinde ich das mit einem Summenzeichen, dieser Fehler muss aus meinem Kopf rein.

Nochmal:
Sei A eine nichtleere Teilmenge von ℕ₀. Weiterhin sei A eine Menge mit 
endlich vielen Elementen n (War ja ok).

Für k = 1 wäre dann A₁:= ({k₁}, k₁) ∈ ℕ₀
Daraus folgt dann, dass n₁ das kleinste Element der Menge A₀ ist.
Für den Nachfolger gilt jetzt n + 1, dann folgt daraus:
A_k+1:= {k₁, k₂, k₃, ..., k_n-1, k, k_n+1}.
Aus dieser Menge kann man theoretisch zwei Teilmengen bilden:
A_k+1:= {k₁, k₂, k₃, ..., k_n-1, k} ∪ {k_n+1}.

Somit kann man folgern, dass k und k_n+1 ein kleinestes Element haben,
in diesem Fall k₁. Das kleinste Element dieser beiden Teilmengen ist
also auch das kleinste Element von A_n+1.

q.e.d. (??)

---

Ups sollte k₁ anstatt n₁ und k + 1 anstatt n + 1 sein :-D

---

Du musst an deiner Notation arbeiten.

Was soll  A₁:= ({k₁}, k₁)  sein?

Beim IS die Menge aufzuteilen um die IV anzuwenden ist ein guter Gedanke, aber

Für den Nachfolger gilt jetzt n + 1, dann folgt daraus: 
A_k+1:= {k₁, k₂, k₃, ..., k_n-1, k, k_n+1}. 

Was soll das bedeuten, warum folgt da was draus?

Somit kann man folgern, dass k und k_n+1 ein kleinestes Element haben, 
in diesem Fall k₁. Das kleinste Element dieser beiden Teilmengen ist 
also auch das kleinste Element von A_n+1. 

Klingt das für dich sinnvoll?

-> Nicht vergessen, dass dieser Beweis am Ende nur für alle endlichen Teilmengen gilt, vergleich das mit der Originalaufgabenstellung.

---

A₁:= ({k₁}, k₁) sollen einelementige Teilmengen sein.

Da dies für ein n (In diesem Fall k₁) gezeigt wurde, kann der Induktionsschritt n + 1 folgen.

Wenn {k} und {k_n+1} ein kleinestes Element k₁ haben und Teilmengen von A_k+1 sind,
dann muss k₁ doch auch das kleinste Element von A_k+1 sein oder?

Mhmmm... ich habe eben noch einen Hinweis entdeckt:
"Jede nichtleere Teilmenge A von N0 besitzt ein kleinstes Element"
Hinweis: Zeigen Sie induktiv für alle n ∈ N0, dass für eine Teilmenge A von N0, die kein
kleinstes Element besitzt, der Schnitt {0, 1, . . . , n} ∩ A leer ist. Folgern Sie daraus dann die
zu zeigende Aussage.

Aber so viel hilft mir das auch nicht weiter..

---

So schreibt man doch keine Mengen auf? A₁:= ({k₁}, k₁)

In der Schreibweise sind {k} und {k_(n+1)} einelementige Mengen, und warum muss das kleinste Element kleiner sein als \(k_{n+1}\)?

Ja dieser Hinweis macht das was ich ominös als Beweis durch Widerspruch bezeichnet habe (und ist nicht auf endliche Teilmengen beschränkt).

Warum hilft dir das nicht weiter? Was verstehst du an dem Hinweis nicht? Wenn du das zeigst, kann A ja nur leer sein was der Widerspruch zur Voraussetzung ist. Ich würde dir wärmstens empfehlen diesen Weg einzuschlagen.

---

Es muss kleiner sein, weil k_n+1 sein Nachfolger ist, oder?

Ich denke, der Beweis durch v.i. ist da noch etwas zu schwer für mich.
Ich versuche mal den Beweis durch Widerspruch.
Dabei werde ich eventuell damit beginnen, zu behaupten, dass
es eine nichtleere Menge A ∈ ℕ gibt, welche kein kleinstes Element besitzt.

Der Anfang vom Studium ist wirklich frustrierend, ich komme mir ehrlich
gesagt total hohl vor :-/

---

Also sorry aber den Grundgedanken hast du richtig nur alles drum herum ist irgendwie nichts halbes und nichts ganzes. Vor allem musst du dir klar sein, dass sich die Induktion nur auf die ANZAHL der Elemente der Teilmenge bezieht und nicht auf die konkreten Elemente selber, diese können beliebig sein.

Beim Widerspruchsbeweis brauchst du ebenfalls Induktion....ich finde ihn persönlich ein wenig anspruchsvoller aber das spielt keine Rolle. Mach dir Gedanken darüber und wenn du was hast, dass man präsentieren kann und von der Notation her stimmig ist, dann poste das mal (bitte nicht wieder sofort einfach irgendwas runter tippen). 

Keine Sorge, du bist nicht alleine damit. Ist verständlich das Gefühl, du lernst ja auch grade erst wirklich logisch und strukturiert zu denken :). Wichtig ist, dass du, wenn du eine Argumentation aufschreibst nicht dich damit überzeugen sollst sondern jemand anderen. Da ist vor allem eine schlüssige und einheitliche Notation grundlegend.

Answer 1

a)  

A(n):   ∑ⁿ_i=0 qⁱ = (1 - qⁿ⁺¹) / (1 -q)

Basis A(0):   q⁰ = 1 (1-q¹) / 1-q  wahr

A(n) -> A(n+1):

∑ⁿ⁺¹_i=0  qⁱ

⁼ ∑ⁿ_i=0 qⁱ  +  qⁿ⁺¹ 

=_IV  (1 - qⁿ⁺¹) / (1 -q)  +  qⁿ⁺¹

= (1 - qⁿ⁺¹ + (1-q) •  qⁿ⁺¹ ) / (1-q)

= ( 1 - qⁿ⁺¹ +  qⁿ⁺¹ + q •  qⁿ⁺¹ ) / (1-q)

= ( 1 - q^(n+1)+1 ) / (1-q)  qed.

Gruß Wolfgang