Vollständige Induktion

02.02.2017, 15:01

Daniel_09

Vollständige Induktion

Meine Frage:
Hallo,

ich komme bei folgender Aufgabe nicht weiter.

$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} * \frac{1}{n^k} \leq \frac{1}{k!} \, (k,n \in \mathbb{N}, k\leq n) \end{eqnarray*}$

Diese soll durch vollständige Induktion gelöst werden.
ich komme beim Induktionsschritt nicht weiter.

Meine Ideen:
Induktionsschritt $\begin{eqnarray*} n\rightarrow n+1 ; \, k\rightarrow k+1 \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} \frac{1}{(n+1)^{k+1}} \leq \frac{1}{(k+1)!} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} \frac{1}{(n+1)^{k+1}} = \left (\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k+1 \end{pmatrix}\right) * \frac{1}{(n+1)^{k+1}} \end{eqnarray*}$

$\begin{eqnarray*} \leq \left(\frac{1}{k!}+ \begin{pmatrix} n \\ k+1 \end{pmatrix}\right) * \frac{1}{(n+1)^{k+1}} \end{eqnarray*}$

$\begin{eqnarray*} =\left(\frac{1}{k!} + \frac{n!}{(k+1)!*(n-(k+1)!} \right) * \frac{1}{(n+1)^{k+1}} \end{eqnarray*}$

Ab hier weiß ich nicht wie ich es weiter Zielbringend umformen könnte.

Wäre nett wenn mir da jemand weiterhelfen könnte smile

02.02.2017, 15:16

Matt Eagle

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Warum soll das per Induktion gemacht werden?

Wenn man den Term auf der linken Seite der zz Ungl. mal kürzt

$\begin{eqnarray*} {n\choose k}\frac 1{n^k}=\frac 1{k!}\prod_{j=1}^k\frac{n-k+j}n \end{eqnarray*}$

dann kann man die Abschätzung doch direkt ablesen, denn alle Faktoren unter dem Produktzeichen sind offenbar $\begin{eqnarray*} \leq 1. \end{eqnarray*}$

02.02.2017, 15:22

HAL 9000

Auf diesen Beitrag antworten »

@Daniel

Zunächst mal: Ich bin derselben Meinung wie Matt Eagle, der induktionslose Beweis ist hier vorzuziehen.

Aber gut, sagen wir mal wir versuchen es über vollständige Induktion. Aber dann solltest du dich zumindest entscheiden, über welche der beiden Variablen $\begin{align*} n \end{align*}$ oder $\begin{align*} k \end{align*}$ du diesen Induktionsbeweis führen willst. Dein doppeltes Gewurstel

Zitat:

Original von Daniel_09
Induktionsschritt $\begin{eqnarray*} n\rightarrow n+1 ; \, k\rightarrow k+1 \end{eqnarray*}$

geht jedenfalls gar nicht. unglücklich

02.02.2017, 17:20

Daniel_09

Auf diesen Beitrag antworten »

Die Aufgaben Überschrift lautet: ( Vollständige Induktion arithmetisch)

Zeigen sie mithilfe vollständiger Induktion: verwirrt

@ HAL 9000

Ich dachte ich müsste bei dieser Aufgabe zeigen, dass dies für jedes n und jedes k zählt verwirrt

02.02.2017, 17:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Daniel_09
Ich dachte ich müsste bei dieser Aufgabe zeigen, dass dies für jedes n und jedes k zählt verwirrt

Ja, das stelle ich ja auch nicht in Abrede. Es ist nur unverständlich, was deine "Doppelinduktion" bedeuten soll - ich bin gern offen für eine Erklärung deinerseits.

----------------------

Man kann die Aussage

Zitat:

$\begin{align*} A(k) \end{align*}$ : Für alle $\begin{align*} n \end{align*}$ mit $\begin{align*} n\geq k \end{align*}$ gilt $\begin{align*} \binom{n}{k}\cdot \frac{1}{n^k} \leq \frac{1}{k!} \end{align*}$ .

durch Vollständige Induktion über $\begin{align*} k \end{align*}$ zeigen, startend mit $\begin{align*} k=0 \end{align*}$ .

Man kann auch

Zitat:

$\begin{align*} B(n) \end{align*}$ : Für alle $\begin{align*} k \end{align*}$ mit $\begin{align*} 0\leq k\leq n \end{align*}$ gilt $\begin{align*} \binom{n}{k}\cdot \frac{1}{n^k} \leq \frac{1}{k!} \end{align*}$ .

durch Vollständige Induktion über $\begin{align*} n \end{align*}$ zeigen, startend mit $\begin{align*} n=0 \end{align*}$ .

Beide Methoden sind tauglich zum Beweis der Behauptung, es sind auch noch andere Varianten denkbar. Aber bei dem was du machst, ist mir vollkommen unklar, inwieweit das die Aussage für alle $\begin{align*} n\geq k \end{align*}$ beweisen soll. unglücklich

02.02.2017, 18:45

Daniel_09

Auf diesen Beitrag antworten »

meins ist wohl quatsch.

----------------------

Man kann die Aussage

Zitat:

durch Vollständige Induktion über $\begin{align*} k \end{align*}$ zeigen, startend mit $\begin{align*} k=0 \end{align*}$ .

darf ich mit k= 0 starten wenn $\begin{eqnarray*} k \in \mathbb{N} \end{eqnarray*}$ und $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ ohne die 0 definiert wurde?

02.02.2017, 18:51

HAL 9000

Auf diesen Beitrag antworten »

Klar darfst du: Dann beweist du sogar noch etwas mehr, nämlich auch für k=0. Allerdings musst du dort n=0 rausnehmen. Augenzwinkern

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen