eine etwas andere induktions aufgabe

27.10.2010, 23:57

hnky

eine etwas andere induktions aufgabe

hallo,

ich habe momentan probleme bei folgender induktionsaufgabe:

Zitat:

Beweise mit hilfe des induktionsprinzips folgende aussage:
Jede natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ lässt sich mithilfe eines $\begin{eqnarray*} k\geq 0 \end{eqnarray*}$ und eines ungeraden $\begin{eqnarray*} q\in \mathbb N \end{eqnarray*}$ in der form $\begin{eqnarray*} n=2^k*q \end{eqnarray*}$ darstellen.

ich bin mir hier beim induktionsanfang schon nicht sicher: $\begin{eqnarray*} n=1 => 1=2^k*q \end{eqnarray*}$

da $\begin{eqnarray*} q\in \mathbb N \end{eqnarray*}$ und q ungerade sein muss, kann q nicht $\begin{eqnarray*} (2^k)^{-1} \end{eqnarray*}$ sein(das würde ja immer eine gerade zahl sein), also muss $\begin{eqnarray*} q=1 \end{eqnarray*}$ und somit $\begin{eqnarray*} k=0 \end{eqnarray*}$ sein.

den induktionsschritt bekomme ich noch nicht hin:

$\begin{eqnarray*} n->n+1 \end{eqnarray*}$

zu zeigen ist also: $\begin{eqnarray*} n+1=2^k*q \end{eqnarray*}$ .

falls ich den induktionsanfang richtig gemacht habe, kann ich doch direkt schon die induktionsvorraussetzung anwenden:

$\begin{eqnarray*} 2^k*q+1=2^k*q \end{eqnarray*}$

nunja, und hier wäre somit $\begin{eqnarray*} 1=0 \end{eqnarray*}$ , was offensichtlich falsch ist.

ich hatte noch einige weitere überlegungen, aber die bringen mich auch nicht sonderlich weiter:

in der aufgabenstellung steht zwar nichts davon, dass $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ ist, aber ich denke, dass das hier der fall ist.

q ist ungerade, d.h. $\begin{eqnarray*} q=2m-1 \end{eqnarray*}$ , $\begin{eqnarray*} m\in \mathbb N \end{eqnarray*}$ .

hat jemand eine idee, und könnte mir weiterhelfen?

danke schonmal im voraus.

28.10.2010, 00:04

jester.

Auf diesen Beitrag antworten »

Vollständige Induktion

28.10.2010, 00:14

hnky

Auf diesen Beitrag antworten »

Iorek spricht in seinem thread von einer fallunterscheidung innerhalb der induktion, nur frage ich mich gerade, wonach er unterschieden hat, damit das ganze klappt.

n ungerade/gerade ?
k > n bzw k<n ?

bei mir will das einfach nicht klappen, aber vllt ist es schon zu spät für heute.

28.10.2010, 08:46

Iorek

Auf diesen Beitrag antworten »

Zitat:

Original von hnky
n ungerade/gerade ?

Ja, damit klappt das. Für gerades n ist der Induktionsschritt quasi trivial, für ungerades n nicht ganz so trivial, nutz dafür den Tipp von René Gruber.

Zitat:

Original von René Gruber
Vielleicht ist ja Induktion "im weiteren Sinne" gemeint, d.h. mit einem Induktionsschritt $\begin{eqnarray*} (<n) \to n \end{eqnarray*}$ statt des üblichen $\begin{eqnarray*} (n-1)\to n \end{eqnarray*}$ ?

28.10.2010, 16:25

hnky

Auf diesen Beitrag antworten »

danke, dann versuche ich es einmal damit:

Sei n gerade $\begin{eqnarray*} => \frac{n}{2} \in \mathbb N \end{eqnarray*}$ .

den induktionsanfang müsste ich doch dann bei n=2 machen, also $\begin{eqnarray*} 2=2^k*q \end{eqnarray*}$ , da q ungerade sein muss, ist q=1 und somit k=1.

der induktionsschritt erscheint mir nicht ganz so trivial zu sein, jedenfalls für mich nicht.
$\begin{eqnarray*} n->n+1 \end{eqnarray*}$ bedeutet doch in diesem fall, dass ich weiß, dass ich eine gerade natürliche zahl durch $\begin{eqnarray*} 2^k*q \end{eqnarray*}$ darstellen kann, ich muss also zeigen, dass ich auch die nächste gerade zahl in der form darstellen kann.

in dem fall wäre also mit $\begin{eqnarray*} n+1 \end{eqnarray*}$ die nächste gerade zahl gemeint, oder?

um das ganze besser zu verstehen, habe ich mir überlegt, wie das ganze weiter gehen könnte, beispielsweise:

$\begin{eqnarray*} 4=2^2*1 \end{eqnarray*}$
$\begin{eqnarray*} 6=2^1*3 \end{eqnarray*}$
$\begin{eqnarray*} 8=2^3*1 \end{eqnarray*}$
$\begin{eqnarray*} 10=2^1*5 \end{eqnarray*}$
$\begin{eqnarray*} 12=2^2*3 \end{eqnarray*}$

nun sehe ich hier allerdings noch keinen wirklichen zusammenhang, könntest du mir noch einmal weiterhelfen?

28.10.2010, 16:34

Iorek

Auf diesen Beitrag antworten »

Mach die Fallunterscheidung ein wenig anders:

Wenn n gerade ist, dann ist n+1 ungerade; und wie sich eine ungerade Zahl in dieser Form darstellen lässt ist wirklich trivial Augenzwinkern

Wenn n ungerade ist, dann ist n+1 gerade, insbesondere existiert dann eine natürliche Zahl m mit 2m=n+1. Die natürlichen Zahlen sind angeordnet, also erhältst du weiter $\begin{eqnarray*} m\leq n \end{eqnarray*}$ .

28.10.2010, 17:19

hnky

Auf diesen Beitrag antworten »

danke für den hinweis.

damit ist der fall n gerade ja wirklich trivial Big Laugh

für den fall n ungerade müsste ich doch jetzt den hinweis von René Gruber befolgen, und den induktionsschritt für m->n machen, oder habe ich das falsch verstanden?

dann wäre ja $\begin{eqnarray*} n+1=2m \end{eqnarray*}$
$\begin{eqnarray*} <=> n=2m-1 \end{eqnarray*}$

$\begin{eqnarray*} 2m-1 \end{eqnarray*}$ ist aber immer ungerade, und das wäre doch dann genau der 1. fall, oder täusche ich mich da?

(das ist eine sehr gemeine induktionsaufgabe, die mich noch an den rand des wahnsinns treibt)

28.10.2010, 17:23

Iorek

Auf diesen Beitrag antworten »

Wenn du das so umformt ist aber auch n wieder ungerade, das darfst du so also nicht machen.

Wir sollten auch irgendwann mal die Induktionsvoraussetzung anwenden, das ist jetzt der Fall:

IV: Die Behauptung gelte für ein $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ .

IS: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

Fallunterscheidung:
Sei n gerade: $\begin{eqnarray*} \checkmark \end{eqnarray*}$

Sei nun n ungerade, dann ist n+1 gerade, d.h. $\begin{eqnarray*} \exists m\in\mathbb N:~n+1=2m \end{eqnarray*}$ , jetzt nutze meinen Hinweis bzgl. der Anordnung auf $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ , danach zieht dann Renes Hinweis.

28.10.2010, 18:36

hnky

Auf diesen Beitrag antworten »

danke, ich hab es nun verstanden smile

Neue Frage »

Antworten »

eine etwas andere induktions aufgabe

Verwandte Themen