Beweis durch vollständige Induktion k*2^(n-k)

13.07.2013, 17:19

whiskybob

Beweis durch vollständige Induktion k*2^(n-k)

Meine Frage:
Ich bereite mich gerade auf die Klausur vor und bin über diese Aufgabe gestollpert.

1. Zeigen Sie mittels vollständiger Induktion, dass für alle n ? N0
gilt:

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

Meine Ideen:
Mein Rechnung sieht nun wie folgt aus:

IA: (n=0): beide Seiten ergeben 0.

zZ: $\begin{eqnarray*} \sum\limits_{k=1}^{n+1} (k * 2^{n-k}) = 2^{n+2} - (n + 3) \end{eqnarray*}$

IS: $\begin{eqnarray*} \sum\limits_{k=1}^{n+1} (k * 2^{n-k}) = \sum\limits_{k=1}^n (k * 2^{n-k}) + (n+1) * 2^{-1} = 2^{n+1}-(n+2)+(n+1)* \frac{1}{2} = \end{eqnarray*}$

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

Nun habe ich dass zu zeigende Ergebnis benahe, allerdings nur beinahe hergeleitet.

Habe ich etwas grundsätzliches nicht beachtet oder steckt der Fehler im Detail.

13.07.2013, 17:50

Helferlein

Auf diesen Beitrag antworten »

Du hast das n in der Summe nicht ersetzt.

14.07.2013, 11:58

whiskybob

Auf diesen Beitrag antworten »

Muss ich n durch n+1 dann hier ersetzten?

$\begin{eqnarray*} \sum\limits_{k=1}^{n+1} (k * 2^{(n+1)-k}) = \sum\limits_{k=1}^n (k * 2^{n-k}) + (n+1) * 2^{0} = 2^{n+1}-(n+2)+(n+1)* 1= \end{eqnarray*}$

dies führt mich nun zu:

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

Sorry, ich glaube ich benötige nochmal Hilfe.

14.07.2013, 12:26

m4themag1er

Auf diesen Beitrag antworten »

Zitat:

Original von whiskybob
Muss ich n durch n+1 dann hier ersetzten?

$\begin{eqnarray*} \sum\limits_{k=1}^{n+1} (k * 2^{(n+1)-k}) = \sum\limits_{k=1}^n (k * 2^{n-k}) + (n+1) * 2^{0} = 2^{n+1}-(n+2)+(n+1)* 1= \end{eqnarray*}$

dies führt mich nun zu:

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

Sorry, ich glaube ich benötige nochmal Hilfe.

Die erste Gleichheit ist falsch. Bei dir ist da die +1 in der Potenz von 2 verlorgen gegangen!

14.07.2013, 16:44

whiskybob

Auf diesen Beitrag antworten »

Okay. Danke für die Hilfe.

Ich habe bei einer anderen Aufgabe auch ein kleines Problem. Einfach hier posten oder ein neues Thema erstellen?

14.07.2013, 16:49

alterHund

Auf diesen Beitrag antworten »

neues!

13.09.2013, 13:23

jimmyt

Auf diesen Beitrag antworten »

Wie wäre es damit:

I.V.: $\begin{eqnarray*} \sum_{k=1}^{n} k \cdot 2^{n-k} = 2^{n+1} - (n+2) \end{eqnarray*}$

I.A.: n=1:

$\begin{eqnarray*} \sum_{k=1}^{1} k \cdot 2^{n-k} = 1 \cdot 2^{1-1} = 1 \cdot 2^{0} =1 \cdot 1 = 1 \end{eqnarray*}$ (linke Seite)

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

I.S.:

zu zeigen: $\begin{eqnarray*} \sum_{k=1}^{n+1} k \cdot 2^{n+1-k} = 2^{n+2} - (n+3) \end{eqnarray*}$

n -> n+1:

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

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

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

$\begin{eqnarray*} = 2 \cdot \sum_{k=1}^{n} k \cdot 2^{n-k} + ( (n+1) \cdot 2^{0}) \end{eqnarray*}$

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

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

$\begin{eqnarray*} \stackrel{I.V.}{=} 2 \cdot (2^{n+1} - (n+2)) + n+1 \end{eqnarray*}$

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

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

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

$\begin{eqnarray*} = 2^{n+2} - (n + 3) \hspace{1cm} \Box \end{eqnarray*}$

13.09.2013, 13:26

klarsoweit

Auf diesen Beitrag antworten »

@jimmyt: es ist ja schön, daß du alte Threads rauskramst und die Lösung postest. Aber wirklich hilfreich ist das nicht. geschockt

13.09.2013, 13:38

jimmyt

Auf diesen Beitrag antworten »

@klarsoweit: Ok, dann lasse ich es bleiben. Augenzwinkern

Neue Frage »

Antworten »

Beweis durch vollständige Induktion k*2^(n-k)

Verwandte Themen