Vollständige Induktion / Relationen und Ordnungen

27.02.2011, 12:41

Lisa456

Auf diesen Beitrag antworten »

Vollständige Induktion / Relationen und Ordnungen

Meine Frage:
Hi, ich bin gerade im ersten Semester Maschinenbau und die Mathematik Prüfung steht bald an. Ich habe Probleme mit folgenden beiden Aufgaben.

1. Mittels vollständiger Induktion beweise man , dass für alle ungeraden n $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$ der Ausdruck $\begin{eqnarray*} 2^{n} + 1 \end{eqnarray*}$ durch 3 teilbar ist.

2. Gegeben sei auf $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ die Relation R mit aRb <=>
"a kleiner oder gleich b". Gebe die eigenschaften (reflexiv, symetrisch ,antisymetrisch und transitiv von R an.

Meine Ideen:
Aufgabe 1:
nur ungerade zahlen, daher stelle ich n als 2m-1 da. Wobei m eine beliebe zahl aus dem raum der Natürlichen Zahlen sein kann.

Induktktionsanfang: mit m=1

$\begin{eqnarray*} \frac{2^{2*1-1}+1 }{3} = 1 \end{eqnarray*}$

Induktionsannahme:

$\begin{eqnarray*} 2^{2m-1} +1 \end{eqnarray*}$ sei durch 3 teilbar.

Induktionsschritt:
Hier bin ich mir nicht ganz sicher, denn eign haben wir es immer so gemacht das wir in dem Induktionsschritt gezeigt haben das es auch für n+1 gilt, was hier aber nicht funktioniert weil man soll ja laut aufgabenstellung nur ungerade zahlen benutzen. Deswegen habe ich hier N = n+2 = 2m+1

=> $\begin{eqnarray*} 2^{2m+1} +1 \end{eqnarray*}$ , allerdings kann ich jetzt keine aussage darüber treffen ob er wirklich durch 3 teilbar ist.

Aufgabe 2:

Hier verstehe ich nicht so ganz worum es überhaupt geht. Das einzige was ich im Skriptum gefunden habe sind die Bedingungen.
Die Relation R heißt
reflixiv , falls (x,x) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ für alle x $\begin{eqnarray*} \in \end{eqnarray*}$ dom(R).
symmetrisch, falls aus (x,y) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ sets (y,x) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ folgt.
antisymmetrisch, falls aus (x,y) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ und (y,x) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ auch stets x=y folgt.
transitiv, falls aus (x,y) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ und (y,z) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ auch stets (x,z) $\begin{eqnarray*} \in \mathbb R \end{eqnarray*}$ folgt.

27.02.2011, 12:45

kiste

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 2^{2m+1} +1 = 4\cdot 2^{2m-1} + 1 \end{eqnarray*}$ und $\begin{eqnarray*} 4 = 3+1 \end{eqnarray*}$ hilft.

Zum zweiten musst du jetzt eben in diesem konkreten Fall testen ob die Bedingungen erfüllt sind.

Gilt zum Beispiel immer dass aus a kleiner gleich b auch b kleiner gleich a folgt? Falls ja dann ist die Relation symmetrisch. Mit den anderen Eigenschaften analog verfahren.

27.02.2011, 12:53

Lisa456

Auf diesen Beitrag antworten »

Achsoo, also bei aufgabe 1 hast du die beiden ausdrücke gleich gesetzt, aber wie kommst auf 4* und was hast du für m genommen?

aufgabe 2:
Woher weiß man denn ob aus a kleiner gleich b , auch b kleiner gleich a folgt weil es sind doch irgendwelche zahlen oder nicht?

27.02.2011, 12:56

kiste

Auf diesen Beitrag antworten »

m ist beliebig und die Umformung sind nur die Potenzgesetze.

Wenn du die Symmetrie nicht allgemein zeigen kannst suche ein Gegenbeispiel.

27.02.2011, 13:01

Lisa456

Auf diesen Beitrag antworten »

Das musst du mir mal genauer erklären da blicke ich nicht ganz durch, aufgrund welcher Potzengesetze kommst du darauf?

Achsoo ja gut das macht Sinn. Ja gut das würde hier in dem Beispiel aber keine symmetrie ergeben weil wenn a kleiner als b ist dann kann ja b nicht kleiner als a sein oder?

27.02.2011, 13:09

kiste

Auf diesen Beitrag antworten »

Ein Beispiel ist immer konkret ;-)
Nimm beispielsweise a=3 und b=5 dann wird ein Schuh draus.

Und das mit den Potenzgesetzen kann doch nicht dein Ernst sein, oder? Da schaust du bitte selbst nochmal drüber bis du es siehst.

Anzeige

27.02.2011, 13:20

Lisa456

Auf diesen Beitrag antworten »

mhhh wenn 3<5 und 5nicht<3 bzw 5>3 , also wenn man nicht< als> interpretiert dann sollte die symmetrie gegeben sein willst du mir damit sagen?

Tut mir leid ich sehe hier einfach keine der Potzgesetze die ich hier anwenden könnte, bzw ich kann nicht nachvollziehen was du da gemacht hast.

27.02.2011, 13:56

kiste

Auf diesen Beitrag antworten »

2^2=4

und deinen ersten Absatz verstehe ich nicht. Die Relation ist doch offensichtlich nicht symmetrisch da 3<=5 gilt aber nicht 5<=3

27.02.2011, 14:10

Lisa456

Auf diesen Beitrag antworten »

Ja das 2^2 =4 verstehe ich, aber wie kommst du dazu

$\begin{eqnarray*} 2^{2m+1} +1 = 4\cdot 2^{2m-1} + 1 \end{eqnarray*}$ ....woher weißt du das es das gleiche ist wenn du im exponent -1 nimmst und den ganzen ausdruck mit 4 multiplizierst?

27.02.2011, 14:26

Lisa456

Auf diesen Beitrag antworten »

Ahhh ok ich hab verstanden wie du darauf kommst. Ist den nun nachgewiesen das es auf für n+2 gilt? Weil laut der annahme ist der Ausdruck

$\begin{eqnarray*} 2^{2m-1} + 1 \end{eqnarray*}$ ja durch 3 teilbar und dieser ausdruck durch 3 teilbar ist dann sollte ja jedes vielfache was durch die multiplikation entsteht auch durch 4 teilbar sein oder?

27.02.2011, 14:31

Lisa456

Auf diesen Beitrag antworten »

....auch durch 3 teilbar sein oder?

27.02.2011, 15:03

kiste

Auf diesen Beitrag antworten »

Ordne einmal deine Gedanken und schreib es sauber auf.

27.02.2011, 15:15

Lisa456

Auf diesen Beitrag antworten »

Anders gesagt ist der nachweiß damit erbracht das es auch für n+2 gilt, mit

$\begin{eqnarray*} 2^{2m+1} +1 = 4\cdot 2^{2m-1} + 1 \end{eqnarray*}$ ?

27.02.2011, 15:25

kiste

Auf diesen Beitrag antworten »

Nein, aber ich habe bereits ganz oben einen weiteren Tipp dir geliefert wie man das beweisen kann.

27.02.2011, 15:31

Lisa456

Auf diesen Beitrag antworten »

mhhh ich hätte jetzt gedacht das es bewiesen sei, aufgrund der induktionsannahme $\begin{eqnarray*} 2^{2m-1} + 1 \end{eqnarray*}$ , weil dies ja durch 3 teilbar sein sollte und nur weil es mit 4 multipliziert wird ist es ja immer noch druch 3 teilbar, oder ist das falsch?

27.02.2011, 15:36

Lisa456

Auf diesen Beitrag antworten »

oder meinst du das man die 4 als 3+1 darstellt und somit :

$\begin{eqnarray*} (3+1)\cdot (2^{2m-1} + 1) \end{eqnarray*}$

27.02.2011, 15:40

kiste

Auf diesen Beitrag antworten »

Und weiter? ...

27.02.2011, 15:48

Lisa456

Auf diesen Beitrag antworten »

einfach ausrechnen?....

27.02.2011, 15:58

Lisa456

Auf diesen Beitrag antworten »

3* $\begin{eqnarray*} (2^{2m-1}) \end{eqnarray*}$ + 3+ $\begin{eqnarray*} (2^{2m-1}) \end{eqnarray*}$ +1

= 4 $\begin{eqnarray*} (2^{2m-1}) \end{eqnarray*}$ +4

und nu?

27.02.2011, 17:00

Lisa456

Auf diesen Beitrag antworten »

Hallo? noch da?

27.02.2011, 19:06

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von Lisa456
3* $\begin{eqnarray*} (2^{2m-1}) \end{eqnarray*}$ + 3+ $\begin{eqnarray*} (2^{2m-1}) \end{eqnarray*}$ +1

Das jetzt ausnutzen!

Und ein 3fach Post ist zu vermeiden, ich bin auch nicht den ganzen Tag nur hier ;-)

27.02.2011, 21:38

Lisa456

Auf diesen Beitrag antworten »

ja gut das stimmt =). Also der rechte Term gleicht ja der Ind. Annahme.

Und er linke ist ja eigentlich nur das 3-fache davon, also sollte dieser natürlich auch druch 3 teilbar sein oder nicht?

28.02.2011, 16:42

kiste

Auf diesen Beitrag antworten »

Ja. Sauber aufgeschrieben:
Die ersten beiden Summanden sind trivialerweise durch 3 teilbar, die anderen beiden Summanden gerade die Induktionsvoraussetzung, also auch durch 3 teilbar.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »