Vollständige induktion

28.05.2005, 14:17

cjaeger

Vollständige induktion

hi, hab hier kleine probleme mit der induktion:

Beweisen Sie mittels Vollständiger Induktion ( $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ ):

a) $\begin{eqnarray*} 4^{n} > 7n-5 \end{eqnarray*}$

b) Die Potenzmenge für n-elementige Menge M enthält $\begin{eqnarray*} 2^{n} \end{eqnarray*}$

..................................................................................................

bei Aufgabe a hab ich schon:

Ind.Anf. ist A(3)=>48>16, für n=1,2 gilt es noch nicht.

Ind.Schluss:
n->n+1

$\begin{eqnarray*} 4^{n+1} > 7(n+1)-5 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow 4\cdot 4^{n} >7n+2 \end{eqnarray*}$

jetzt ist ja $\begin{eqnarray*} 4^{n} \end{eqnarray*}$ >7n-5

$\begin{eqnarray*} \Rightarrow 4\cdot (7n-5)>7n+2 \end{eqnarray*}$

wenn ich das nach n auflöse kommt aber nur blödsinn raus:

n= $\begin{eqnarray*} \frac{22}{21} \end{eqnarray*}$

wo ist mein Fehler?

Aufgabe b hab ich keine Ahnung wie ich ansetzen soll...

vielen dank...schonmal..

chris Hammer

28.05.2005, 14:27

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von cjaeger
Ind.Anf. ist A(3)=>48>16, für n=1,2 gilt es noch nicht.

$\begin{eqnarray*} 4^1>7\cdot 1-5=2 \end{eqnarray*}$ und $\begin{eqnarray*} 4^2>7\cdot 2-5=11 \end{eqnarray*}$ sollen falsch sein???

Zitat:

Original von cjaeger
Ind.Schluss:
n->n+1

$\begin{eqnarray*} 4^{n+1} > 7(n+1)-5 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow 4\cdot 4^{n} >7n+2 \end{eqnarray*}$

jetzt ist ja $\begin{eqnarray*} 4^{n} \end{eqnarray*}$ >7n-5

$\begin{eqnarray*} \Rightarrow 4\cdot (7n-5)>7n+2 \end{eqnarray*}$

wenn ich das nach n auflöse kommt aber nur blödsinn raus:

n= $\begin{eqnarray*} \frac{22}{21} \end{eqnarray*}$

Du solltest nicht von deiner Aussage ausgehen und dann Umformungen machen, sondern mit einer Ungleichungskette arbeiten:

$\begin{eqnarray*} 4^{n+1}=4\cdot 4^n>4\cdot (7n-5) \end{eqnarray*}$

Jetzt musst du noch

$\begin{eqnarray*} 4\cdot (7n-5)\geq 7n+2 \end{eqnarray*}$

beweisen. $\begin{eqnarray*} n=\frac{22}{21} \end{eqnarray*}$ kann beim Umformen einer Ungleichung sicher nicht rauskommen! Da muss auch eine Ungleichung rauskommen, richtig wäre $\begin{eqnarray*} n>\frac{22}{21} \end{eqnarray*}$ !
Damit müsstest du es jetzt schaffen.
Zu b): Die Potenzmenge ist ja die Menge aller Teilmengen. Überlege dir zuerst, wie viele k-elementige $\begin{eqnarray*} 0\leq k\leq n \end{eqnarray*}$ Teilmengen eine n-elementige Teilmenge hat! Dann musst du die alle aufaddieren.
Und falls du es mit Induktion beweisen sollst: Beim Induktionsschritt nimmst du dir eine n+1-elementige Menge $\begin{eqnarray*} M=\{a_1,...,a_{n+1}\} \end{eqnarray*}$ . Betrachte die Teilmenge $\begin{eqnarray*} T=\{a_1,...,a_n\} \end{eqnarray*}$ . Wie viele Teilmenge besitzt T? Wie viele besitzt dann M und warum?

Gruß MSS

28.05.2005, 15:23

cjaeger

Auf diesen Beitrag antworten »

okay...danke schonmal....he ich das richtig das
meine ungleichung (wollte auch > schreiben statt =) wahr
ist für n>22/21? also für gerundet n>1,05? ....

zu b) Also ich hab jetz mal verschriftlicht den Ansatz....

Ind-Anfang:
A(0)= $\begin{eqnarray*} 2^{0} \end{eqnarray*}$ =1 für bsp. L={}
A(1) = $\begin{eqnarray*} 2^{1} \end{eqnarray*}$ =2 für bsp. M={a,{}}, also P(M)={{a},{}}
....

Ind-Schluss:

n-->n+1

Sei
M:={a1, a2, ..., an, a(n+1)}
T:={a1, a2, ...., an}

dann ist doch T eine Teilmenge von M, und hat 1 Element nämlich a(n+1) weniger.....

also: |T|=|M-1|

T besitzt eine Teilmenge weniger, n viele, M hat n+1 viele.

hab ich das richtig verstanden bis jetzt?

und wie kommich nun auf den beweis?

danke schonmal...

chris

Neue Frage »

Antworten »

Vollständige induktion

Verwandte Themen