Induktionsbeweis

06.05.2014, 17:24

Schattenklinge

Auf diesen Beitrag antworten »

Induktionsbeweis

Hi,

ich soll im Fach Informatik eine vollständiger Induktion machen, und damit zeigen, dass diese geschlossene Form gelte:

T(n) = log(zur basis 2)(n+1) * b + a

Das ist die Formel, ich darf vereinfachend annehmen, dass n = $\begin{eqnarray*} 2^{k}-1 \end{eqnarray*}$ ist und daher die Induktion auch über k vollzogen werden kann.

Wie geh ich da nun vor? Ich weiß, wie eine Induktion funktioniert, aber nicht in diesem Fall? Wäre über Hilfe dankbar!

06.05.2014, 17:27

bijektion

Auf diesen Beitrag antworten »

Mehr ist nicht gegeben? Ist es richtig $\begin{eqnarray*} T(n)=b \cdot \log_2(n+1) +a \end{eqnarray*}$ ?

06.05.2014, 17:35

Schattenklinge

Auf diesen Beitrag antworten »

Ich hab nur noch das hier...

[attach]34158[/attach]

06.05.2014, 17:40

bijektion

Auf diesen Beitrag antworten »

Poste doch mal die ganze Aufgabe.

07.05.2014, 19:53

Schattenklinge

Auf diesen Beitrag antworten »

Das ist die Aufgabe...

[attach]34184[/attach]

07.05.2014, 19:57

bijektion

Auf diesen Beitrag antworten »

Was sind denn die Fälle der Fallunterscheidung?

Anzeige

08.05.2014, 11:19

Schattenklinge

Auf diesen Beitrag antworten »

T(0) = a
und
T(n) = b + T((n-1)/2)

08.05.2014, 12:23

bijektion

Auf diesen Beitrag antworten »

Ok. Dann musst du also zeigen, dass $\begin{eqnarray*} \bar T(n)=b \cdot \log _2(n+1) + a = \begin{cases}<br /> a & n=0 \\<br /> b+T(\frac{n-1}{2}) & n>0 \\<br /> \end{cases} \end{eqnarray*}$ für alle $\begin{eqnarray*} n \in \mathbb{N}_0 \end{eqnarray*}$ gilt.

Du kannst ja scheinbar $\begin{eqnarray*} n=2^k-1 \end{eqnarray*}$ annehmen, mit $\begin{eqnarray*} k \in\mathbb{N}_0 \end{eqnarray*}$ .

Induktionsanfang: Das ist der Fall $\begin{eqnarray*} k=0 \end{eqnarray*}$ , also auch $\begin{eqnarray*} n=0 \end{eqnarray*}$ . Gilt hier Gleichheit?

08.05.2014, 15:57

Schattenklinge

Auf diesen Beitrag antworten »

Ja, die Gleichheit gilt, denn:

2^0 - 1= 0
also n=0 und 0=0.

Induktionsvoraussetzung ist demnach: b* log zur basis 2(n+1)+a

Induktionsschritt: n->n+1

Und wie weiter? :o

08.05.2014, 16:06

bijektion

Auf diesen Beitrag antworten »

Jetzt nehmen wir mal an, es gilt schon bis $\begin{eqnarray*} n=2^k-1 \end{eqnarray*}$ , da wir Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ machen, muss gezeigt werden, das es dann auch für $\begin{eqnarray*} 2^{k+1}-1 \end{eqnarray*}$ gilt.

Dann fang doch einfach mal an, da kürzt sich schon einiges.

09.05.2014, 09:00

Schattenklinge

Auf diesen Beitrag antworten »

D.h. ich muss $\begin{eqnarray*} n=2^k-1 \end{eqnarray*}$ beweisen per Induktion?

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

09.05.2014, 09:06

bijektion

Auf diesen Beitrag antworten »

Du musst zeigen, dass aus der Gültigkeit für $\begin{eqnarray*} 2^k -1 \end{eqnarray*}$ auch die Gültigkeit für $\begin{eqnarray*} 2^{k+1}-1 \end{eqnarray*}$ folgt.
Das hilft einfaches einsetzen: $\begin{eqnarray*} b \cdot \log_2(2^{k+1}-1+1)+a= \dots \end{eqnarray*}$ .

09.05.2014, 09:44

Schattenklinge

Auf diesen Beitrag antworten »

$\begin{eqnarray*} b \cdot \log_2(2^{k+1}-1+1)+a \end{eqnarray*}$
$\begin{eqnarray*} = b \cdot \log_2(2^{k+1})+a \end{eqnarray*}$
$\begin{eqnarray*} = b \cdot (k+1) +a \end{eqnarray*}$

Ist das so richtig?

09.05.2014, 09:51

bijektion

Auf diesen Beitrag antworten »

Jetzt kannst du noch die Induktionsvoraussetzung nutzen.

09.05.2014, 09:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von bijektion
Du kannst ja scheinbar $\begin{eqnarray*} n=2^k-1 \end{eqnarray*}$ annehmen, mit $\begin{eqnarray*} k \in\mathbb{N}_0 \end{eqnarray*}$ .

Wenn man die Rekursion wie gesehen formuliert, dann gilt das so geschrieben überhaupt nur für $\begin{eqnarray*} n=2^k-1 \end{eqnarray*}$ , auch die Behauptung. Augenzwinkern

Augenzwinkern

Für andere $\begin{eqnarray*} n \end{eqnarray*}$ muss man dann schon mit Gaußklammern arbeiten, also $\begin{eqnarray*} T(n) = b+T\left( \left\lfloor \frac{n-1}{2} \right\rfloor \right) \end{eqnarray*}$ o.ä., damit man nicht irgendwann "gebrochene" Argumente für $\begin{eqnarray*} T \end{eqnarray*}$ erhält. smile

smile

09.05.2014, 10:24

Schattenklinge

Auf diesen Beitrag antworten »

Zitat:

Original von bijektion
Jetzt kannst du noch die Induktionsvoraussetzung nutzen.

Wo und wie setz ich die denn ein? :o

09.05.2014, 10:50

bijektion

Auf diesen Beitrag antworten »

Du kannst etwa $\begin{eqnarray*} b \cdot \log_2(2^{k+1}+1-1)+a = b \cdot (\log_2 2^k+\log_2 2)+a \end{eqnarray*}$ nutzen.

09.05.2014, 11:12

Schattenklinge

Auf diesen Beitrag antworten »

Ich sehe da allerdings nicht, wie mir das weiterhilft...

09.05.2014, 11:19

bijektion

Auf diesen Beitrag antworten »

Es ist $\begin{eqnarray*} b\cdot (\log_2 2^k +\log_2 2)+a = \color{red} b \cdot \log_2 2^k +a \color{black} +b \cdot \log_2 2 \end{eqnarray*}$ , über den ersten Teil wissen wir nach Induktionsvoraussetzung, das der gerade $\begin{eqnarray*} =T(2^k-1) \end{eqnarray*}$ ist, jetzt noch das $\begin{eqnarray*} b \end{eqnarray*}$ dazu und fertig.

09.05.2014, 11:46

Schattenklinge

Auf diesen Beitrag antworten »

Achsoooooo! Natürlich, jetzt sehe ich das auch, mir war das jetzt nicht bewusst, dass ich ausmultiplizieren kann^^

Hab nur auf diesen blöden Logaritmus geschaut :/

09.05.2014, 11:50

Schattenklinge

Auf diesen Beitrag antworten »

Danke für die Hilfe! smile

smile

09.05.2014, 11:52

bijektion

Auf diesen Beitrag antworten »

Kein Problem smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »