Vollständige Induktion mit abhängigem Binom

17.10.2012, 18:11

Binomial

Vollständige Induktion mit abhängigem Binom

Meine Frage:
Ich möchte beweisen, dass Folgendes gilt:

$\begin{eqnarray*} (n+1)(n-j)^j \geq (n+1-j)^j, n \in N, j \leq n \end{eqnarray*}$

Meine Ideen:
Ich komme hier leider zu keinem sinnvollen Ansatz.

17.10.2012, 18:20

riwe

Auf diesen Beitrag antworten »

RE: Vollständige Induktion mit abhängigem Binom

Zitat:

Original von Binomial
Meine Frage:
Ich möchte beweisen, dass Folgendes gilt:

$\begin{eqnarray*} (n+1)(n-j)^j \geq (n+1-j)^j, n \in N, j \leq n \end{eqnarray*}$

Meine Ideen:
Ich komme hier leider zu keinem sinnvollen Ansatz.

ob das geht verwirrt

setze j = n

17.10.2012, 18:41

Binomial

Auf diesen Beitrag antworten »

Nun, dann die längere Variante:

Ich soll zeigen, dass folgendes gilt:
$\begin{eqnarray*} n! \geq (n-j)^j, n \in N, j \leq n \end{eqnarray*}$

Dies wollte ich mit Induktion über n wie folgt beweisen:
IA: $\begin{eqnarray*} n = 1 \end{eqnarray*}$
$\begin{eqnarray*} 1! = 1 \geq (n-0)^0 = 1 \geq (n-1)^1 = 0 \end{eqnarray*}$

IS: $\begin{eqnarray*} n = n + 1 \end{eqnarray*}$
$\begin{eqnarray*} (n+1)! = (n+1)n! \geq_{IV} (n+1)(n-j)^j \end{eqnarray*}$

Ist die Aussage korrekt, so müsste ich jedoch für die Formel auf $\begin{eqnarray*} (n+1-j)^j \end{eqnarray*}$ kommen ...

17.10.2012, 18:45

HAL 9000

Auf diesen Beitrag antworten »

Es gibt keine Gewähr dafür, dass ein Induktionsbeweis von Ungleichungen auf diese Art klappen muss - kann ja sein, dass du durch derartiges Einsetzen der Induktionsvoraussetzung bereits zu grob abschätzt. Und genau das ist hier passiert, wie Werner klar und deutlich aufgezeigt hat.

Tipp: Du musst im Induktionsschritt ja nicht unbedingt auf dasselbe $\begin{eqnarray*} j \end{eqnarray*}$ zurückgreifen, sondern...

17.10.2012, 19:04

Binomial

Auf diesen Beitrag antworten »

@HAL 9000

Nun, wenn nicht mit vollständiger Induktion, wie kann ich die Aussage sonst beweisen? Ich wäre für einen Tipp wirklich sehr dankbar.

17.10.2012, 19:09

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Binomial
Nun, wenn nicht mit vollständiger Induktion

Das habe ich nicht gesagt - offenbar kannst du mit meinem Tipp nichts anfangen. Also:

Induktion: Ja
So wie du sie angepackt hast: Nein

17.10.2012, 19:22

Binomial

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
So wie du sie angepackt hast: Nein

Nun, wie kann man sie den anpacken, damit man den Satz beweisen kann? j ist immer kleiner oder gleich n. Das hilft mir momentan aber nicht viel weiter ...

17.10.2012, 19:25

HAL 9000

Auf diesen Beitrag antworten »

Gut, ich hole mal etwas weiter aus, und verrate damit alles:

Zitat:

Aussage $\begin{eqnarray*} A(n,j) \end{eqnarray*}$ : Es gilt $\begin{eqnarray*} n! \geq (n-j)^j \end{eqnarray*}$ .

Aussage $\begin{eqnarray*} B(n) \end{eqnarray*}$ : Es gilt $\begin{eqnarray*} A(n,j) \end{eqnarray*}$ für alle ganzen $\begin{eqnarray*} j \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq j\leq n \end{eqnarray*}$ .

Jetzt weisen wir $\begin{eqnarray*} B(n) \end{eqnarray*}$ durch Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ nach.

Induktionsanfang $\begin{eqnarray*} n=1 \end{eqnarray*}$ hast du ja schon erledigt.

Im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ haben wir $\begin{eqnarray*} A(n+1,j) \end{eqnarray*}$ für $\begin{eqnarray*} j=0,1,\ldots,n+1 \end{eqnarray*}$ nachzuweisen. Für $\begin{eqnarray*} j=0 \end{eqnarray*}$ sehen wir, dass $\begin{eqnarray*} A(n+1,0) \end{eqnarray*}$ trivialerweise gilt. Für $\begin{eqnarray*} 1\leq j\leq n+1 \end{eqnarray*}$ nutzen wir nun zum Nachweis von $\begin{eqnarray*} A(n+1,j) \end{eqnarray*}$ die Induktionsvoraussetzung, aber nicht die Teilaussage $\begin{eqnarray*} A(n,j) \end{eqnarray*}$ (so wie du es erfolglos versucht hast), sondern $\begin{eqnarray*} A(n,j-1) \end{eqnarray*}$ ... Alles klar?

EDIT: Ok, ich hab nochmal drüber nachgedacht, wie man es einfacher verständlich machen kann. Dazu formen wird die Behauptung äquivalent um, indem wir $\begin{eqnarray*} k=n-j \end{eqnarray*}$ statt $\begin{eqnarray*} j \end{eqnarray*}$ verwenden:

Zitat:

(Äquivalente) Behauptung: Für alle natürlichen Zahlen $\begin{eqnarray*} k,n \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq n \end{eqnarray*}$ gilt $\begin{eqnarray*} n!\geq k^{n-k} \end{eqnarray*}$ .

Jetzt kommst du mit deiner Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ vermutlich zurecht. Aber nach wie vor muss dann im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ der Fall $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ gesondert betrachtet werden, da für den ja die Induktionsvoraussetzung nicht gilt.

18.10.2012, 20:34

Binomial

Auf diesen Beitrag antworten »

Ich würde es denn nun wie folgt versuchen:
$\begin{eqnarray*} (n+1)!=(n+1)n! \geq (n+1)(n-j)^j > (n-j)(n-j)^j = (n-j)^{j+1} > (n+1-j)^j \end{eqnarray*}$

Der Sonderfall $\begin{eqnarray*} j = n + 1 \end{eqnarray*}$ würde wie folgt behandelt:
$\begin{eqnarray*} (n+1)! \geq (n+1-j)^j > (n+1 - (n+1))^{n+1} = 0 \end{eqnarray*}$

18.10.2012, 21:02

HAL 9000

Auf diesen Beitrag antworten »

Du hast es nicht begriffen - dabei dachte ich, dass zumindest diese letzte Variante mit $\begin{eqnarray*} k \end{eqnarray*}$ deutlich genug war. unglücklich

Zitat:

Original von Binomial
Ich würde es denn nun wie folgt versuchen:
$\begin{eqnarray*} (n+1)!=(n+1)n! \geq (n+1)(n-j)^j > (n-j)(n-j)^j = (n-j)^{j+1} > (n+1-j)^j \end{eqnarray*}$

Wieso soll $\begin{eqnarray*} (n-j)^{j+1} > (n+1-j)^j \end{eqnarray*}$ gelten? Es ist ein leichtes, ein Gegenbeispiel zu finden, z.B. mit $\begin{eqnarray*} j=n-1 \end{eqnarray*}$ .

Bzw. (vermutlich ohne es zu merken) hast du vor diesem falschen Schlussschritt richtigerweise die Behauptung für $\begin{eqnarray*} j+1 \end{eqnarray*}$ statt $\begin{eqnarray*} j \end{eqnarray*}$ bewiesen, so wie ich es im ersten Erklärungsversuch oben verständlich machen wollte, denn es ist ja $\begin{eqnarray*} (n-j)^{j+1} = ((n+1)-(j+1))^{j+1} \end{eqnarray*}$ .

18.10.2012, 21:26

Binomial

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Du hast es nicht begriffen - dabei dachte ich, dass zumindest diese letzte Variante mit $\begin{eqnarray*} k \end{eqnarray*}$ deutlich genug war. unglücklich

Mir ist einfach noch nicht ganz klar von welcher Annahme ich im Induktionsschritt ausgehen darf. Wenn ich den Schritt von n nach n + 1 mache, was darf ich dann für j annehmen? Ist j <= n + 1 oder ist j <= n?

18.10.2012, 22:04

HAL 9000

Auf diesen Beitrag antworten »

Ich denke ich hab in diesem Thread genug gesagt, dass ein verständiger Mensch mit Hochschulreife das nachvollziehen können müsste. unglücklich

18.10.2012, 23:38

riwe

Auf diesen Beitrag antworten »

sogar ich einfaches gemüt finde, dass ganz besonders deine äquivalente behauptung ganz einfach nachzuvollziehen ist Augenzwinkern

eine sehr schöne hilfe Freude

Neue Frage »

Antworten »

Vollständige Induktion mit abhängigem Binom

Verwandte Themen