Beweis Ungleichung durch Induktion?

... komplette Frage anzeigen

6 Antworten

Hier ein Beweis ohne Induktion. Der Trick ist, die Formen umzuformen, bis man andere kombinatorische Deutungen hineinlesen kann, und damit auf einmal Schätzungen ohne jegliche Zuhilfenahme von Induktion erzeugen kann.

Behauptung. S:={n ∈ ℕ : 2ⁿ – 5 > n²} = {n∈ℕ : n≥5}

Beweis. (Richtung ⊆). Man beobachtet zunächst:

n |  n² | 2ⁿ–5 | 2ⁿ–5 > n² ?
===========================
0 | 0 | -4 | nein
1 | 1 | -3 | nein
2 | 4 | -1 | nein
3 | 9 | -3 | nein
4 | 16 | 11 | nein
5 | 25 | 27 | ja
===========================

Darum gilt S ⊆ ℕ\\{0; 1; 2; 3; 4} = {n∈ℕ : n≥5}.

(Richtung ⊇). Sei n≥5. Es gilt n² + 5 ≤ n² + n = (n+1)n. Zu zeigen: n(n+1) < 2ⁿ. Man umformt das Produkt (n+1)·n bis man eine andere Deutung hineinlesen kann:

(n+1)·n = 2·½(n+1)·(n+1 – 1)
      = 2·(n+1 über 2)

= (n+1) + (n+1)
( 2 ) ( 2 )

= (n+1) + ( n+1 ) wegen Symmetrie
( 2 ) (n+1–2) der Paskal'schen Zahlen

= (n+1) + (n+1)
( 2 ) (n–1)

= (n) + (n) + ( n ) + ( n ) wegen rekursiver
(1) (2) (n–2) (n–1) Formel für Pask.∆

Man beachte, dass 1 < 2 < n–2 < n–1, da n > 4, da n ≥ 5. Daher sind die vier binomischen Koeffizienten der Form (n über k) für paarweise verschiedene Werte von k mit 0<k<n. Da außerdem k=0 und k=n nicht vorkommen erhält man somit:

(n+1)·n = (n) + (n) + ( n ) + ( n )
(1) (2) (n–2) (n–1)

≤ ∑ (n über k) für k von 1 bis n–1
< ∑ (n über k) für k von 0 bis n
= ∑ |{k-elementige Teilmengen von n}|
für k von 0 bis n
= |{Teilmengen von n}| = |Pot(n)| = 2ⁿ

Zusammengefasst gilt:

n² + 5 ≤ n² + n = (n+1)n < 2ⁿ.

Darum

n² < 2ⁿ–5

für alle n≥5. Darum gilt {n∈ℕ : n≥5} ⊆ S.                                                 QED.

Anmerkung. Das letzte Argument lässt sich verallgemeinern. Es gilt n² < 2ⁿ–k für alle n ≥ k und alle k≥0.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von kreisfoermig
18.10.2016, 00:29

Hier noch ein Beweis.

Lemma 1. 2ⁿ > 2n für alle n∈ℕ mit n>2.
Beweis. Sei n>2. Dann gilt 

2n = n + n
= (n) + (n)
(1) + (1)

= (n) + ( n ) wegen der Symmetrie
(1) + (n–1) des Paskal'schen ∆

≤ ∑ (n über k) für k von k=1 bis n–1

da 1 ≠ n–1, da n>2

< ∑ (n über k) für k von k=0 bis n

= ∑ |{k-elementige Teilmengen von n}|
für k von 0 bis n
= |{Teilmengen von n}| = |Pot(n)| = 2ⁿ

                                                                                         QED (Lemma 1).

Lemma 2.  Die Abbildung ƒ : n∈ℕ ⟼2ⁿ – 5 – n² ist monoton steigen für n>2.
Beweis. Sei n∈ℕ mit n>2. Dann gilt

ƒ(n+1)–ƒ(n) = 2ⁿ⁺¹–2ⁿ – (5–5) – ((n+1)²–n²)
= 2ⁿ·(2–1) – 0 — ((n²+2n+1)–n²)
= 2ⁿ – (2n+1) ≥ 0

Der letzte Schritt gilt, da 2ⁿ > 2n für n>2 laut Lemma 1, und da 2ⁿ, 2n ganze Zahlen sind, es gilt 2ⁿ ≥ 2n + 1.  Somit gilt ƒ(n+1) ≥ ƒ(n) für alle n>2.  QED.

Folgerung 3. ƒ(n) > 0 für alle n ≥ 5.
Beweis. ƒ(5) = 2 > 0. Wegen Monotonie ab 3 gilt ƒ(n)≥ƒ(5) > 0 für n≥5. QED.


Satz. 2ⁿ – 5 > n² ⟺ n≥5.
Beweis. (⟹). Man berechnet die l. S. und r. S. für n∈{0;1;…;4} und stellt fest, dass für diese Werte die Gleichung nicht stimmt. (⟸). Gilt laut Folgerung 3. QED.


Hinter Folgerung 3 könnte zwar rein theoretisch ein Induktionsargument stecken. Dennoch kann man auch diese auch ersetzen. Somit ist dieser Beweis ebenfalls (möglichst) induktionsfrei.

1

Mal ein Beweis ohne Induktion
Für n = 5 stimmt die Aussage erstmals. Ab hier ist die Änderungsrate des Potenzterms 2^(n+1) / 2^n = 2, die des quadratischen Terms höchstens (n+1)^2 / n^2 = 1 + 2/n + 1/n^2 <= 1 + 2/5 + 1/25 = 1,44, der Potenzterm steigt ab 5 also schneller als der quadratische .

Antwort bewerten Vielen Dank für Deine Bewertung

Suche zuerst durch Probieren die kleinste mögliche Zahl, bei der du dann die Induktion verankern kannst. Und dann schaust du halt, was du für den Beweis des "Induktionsschrittes" (jeweils von n zu n+1)  noch nachweisen musst.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von constiEinstein
17.10.2016, 20:20

Und wie würde so ein Beweis aussehen? Muss die Frage nicht selbst beantworten geht um jemand anderes :D 
Ich versuche nur zu helfen 
n ist größer gleich 5 

0

Versuchen wir es doch erst mal durch probieren

n=1    2^1-5 > 1^2  falsch
n=2    2^2-5 > 2^2  falsch
n=3    2^3-5 > 3^2  falsch
n=4    2^4-5 > 4^2  falsch
n=5    2^5-5 > 5^2  richtig.

Also versuchen wir folgenden Satz zu beweisen: Für alle natürlichen Zahlen n mit n ≥ 5 gilt:  2^n-5>n^2

Beweis durch vollständige Induktion

Induktionsbeginn: n=5  2^5-5 = 32 -5 = 27, 5^2 = 25,  Also ist Behauptung für n= 5 richtig.

Induktionsannahme: Die Behauptung sei richtig für n, also 2^n-5>n^2

Induktionsschritt: Wir müssen beweisen, dass die Behauptung dann auch für n+1 richtig ist. Zu zeigen ist also:  2^(n+1)-5>(n+1)^2

Beweis: 

(Ich verwende im folgenden  n^2  ≥ 2n für n ≥ 2, ggf. separat beweisen über vollständige Induktion)

2^(n+1)-5 

= 2* 2^n -5 

= 2^n + 2^n -5   

=   (2^n - 5) + (2^n -5) + 5 

> n^2 + n^2 + 5 (wegen Induktionsannahme) 

> n^2  + 2n + 5 (weil n^2  ≥ 2n für n ≥ 2) 

> n^2 +2n + 1 (weil 5 > 1)

= ( n + 1 )^2

Q.E.D.

Antwort bewerten Vielen Dank für Deine Bewertung

Das Prinzip der vollständigen Induktion bezüglich der natürlichen Zahlen:

______

---

Induktionsbeginn (I.B): Zeige das für die kleinste natürliche Zahl A(n) gilt.

---

Induktionsannahme (I.A): Angenommen A(n) gilt für ein f.a.b. k

Induktionsschritt (I.S): Folgere aus A(k) => A(k+1)

---

q.e.d

______

Zu Deiner Ungleichung:

I.B:

2^(1)-5 > 1² <=> -3 > 1 f

2^(2)-5 > 2² <=> -1 > 4 f

2^(3)-5 > 3² <=> 3 > 9 f

2^(4)-5 > 4² <=> 11 > 16 f

2^(5)-5 > 5² <=> 27 > 25 r

I.A: 2^(k)-5 > k²

I.S: 2^(k+1)-5 > (k+1)²

2^(k+1)-5 > (k+1)² <=> (2*2^(k)-5 > 2*(k+1)²) <=> 2*(k+1)² > (k+1)²

q.e.d


Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von kreisfoermig
17.10.2016, 21:57

2ᵏ⁺¹–5 > (k+1)² ⟺ (2·2ᵏ–5 > (k+1)²) ⟺ 2·(k+1)² > (k+1)²

Das letzte ⟺ ist ungültig. Richtig wäre eher ⟸, was ja reicht. Es gilt nun:

2·2ᵏ–5 = 2·(2ᵏ – 5) + 5
> 2·k² + 5 per Induktion
> k² + 2k + 1, da k²+5 > 2k+1,
da k²-2k > -4,
da k(k-2) > 0,
da k>2
= (k+1)²

Darum gilt 2ᵏ⁺¹–5 = 2·2ᵏ–5 > (k+1)².

1

hier super erklärt;

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von constiEinstein
17.10.2016, 20:47

Ich bin jetzt an der stelle dass ich (n+1) eingesetzt habe jetzt muss ich es doch mit dem endgültigen term auf der anderen Seite vergleichen oder?

0

Was möchtest Du wissen?