Vollständige Induktion - Anwendung Induktionsvoraussetzung

02.02.2025, 17:42

Johann2124

Vollständige Induktion - Anwendung Induktionsvoraussetzung

Ich habe folgende Aufgabe: Zeige durch direktes Ausrechnen, aber auch durch Induktion:
$\begin{eqnarray*} \binom{\alpha}{k} + \binom{\alpha}{k + 1} = \binom{\alpha + 1}{k + 1} \quad \text{für $\alpha \in \mathbb{R}$ und $k \in \mathbb{N}_{\geq 0}$}. \end{eqnarray*}$

Beweis durch direktes Ausrechnen:
Per definitionem ist
$\begin{eqnarray*} \binom{\alpha}{k} + \binom{\alpha}{k + 1} = \frac{\alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1)}{k!} + \frac{\alpha (\alpha - 1) \cdots (\alpha - k +1) (\alpha - k)}{(k + 1)!}\\ = \frac{(k + 1) \alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1) + \alpha (\alpha - 1) \cdots (\alpha - k + 1) (\alpha - k)}{(k + 1)!}\\ = \frac{\Big((k + 1) + (\alpha - k)\Big) \alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1)}{(k + 1)!}\\ = \frac{(\alpha + 1) \alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1)}{(k + 1)!} = \binom{\alpha + 1}{k + 1}. \end{eqnarray*}$

Beweis durch vollständige Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ :
Die obrige Aussage bezeichne ich kurz mit $\begin{eqnarray*} A(k) \end{eqnarray*}$ . Die Aussage $\begin{eqnarray*} A(0) \end{eqnarray*}$ ist wahr, denn
$\begin{eqnarray*} \binom{\alpha}{0} + \binom{\alpha}{1} = 1 + \frac{\alpha}{1!} = \frac{\alpha + 1}{1!} = \binom{\alpha + 1}{1}. \end{eqnarray*}$
Die Aussage $\begin{eqnarray*} A(1) \end{eqnarray*}$ ist wahr, denn
$\begin{eqnarray*} \binom{\alpha}{1} + \binom{\alpha}{2} = \frac{\alpha}{1!} + \frac{\alpha (\alpha - 1)}{2!} = \frac{2 \alpha + \alpha (\alpha - 1)}{2!} = \frac{\Big(2 + (\alpha - 1)\Big) \alpha}{2!} = \frac{(\alpha + 1) \alpha}{2!} = \binom{\alpha + 1}{2}. \end{eqnarray*}$
Sei $\begin{eqnarray*} A(k) \end{eqnarray*}$ für irgendein $\begin{eqnarray*} k \end{eqnarray*}$ richtig, also
$\begin{eqnarray*} \binom{\alpha}{k} + \binom{\alpha}{k + 1} = \binom{\alpha + 1}{k + 1}. \end{eqnarray*}$
Unter dieser Voraussetzung ist
$\begin{eqnarray*} \binom{\alpha}{k + 1} + \textcolor{red}{\binom{\alpha}{k + 2}} = \binom{\alpha}{k + 1} + \left(\textcolor{red}{\binom{\alpha + 1}{k + 2} - \binom{\alpha}{k + 1}}\right) = \binom{\alpha + 1}{k + 2}. \end{eqnarray*}$

Meine Frage:
Streng genommen, habe ich nicht die Induktionsvoraussetzung angewendet, sondern die Voraussetzung indem ich k durch k+1 substituiere. Darf ich das so machen? Falls nicht, komme ich beim Indukionsschritt nicht weiter und bräuchte eure Unterstützung.

02.02.2025, 17:51

HAL 9000

Auf diesen Beitrag antworten »

Im Induktionschritt muss man nicht zwingend die Induktionsvoraussetzung benutzen. Wenn man sie allerdings gar nicht benötigt heißt das aber, dass es eigentlich unnötig war, das ganze als Induktionsbeweis zu organisieren.

P.S.: Wenn aber die Aufgabensteller es unbedingt so wollen, dann zeigt man ihnen eben auf diese Weise deutlich, was man von der Idee Induktionsbeweis in diesem Fall hält: Eigentlich nichts. Augenzwinkern

02.02.2025, 18:22

IfindU

Auf diesen Beitrag antworten »

Du zeigst die Aussage $\begin{eqnarray*} A(k+1) \end{eqnarray*}$ unter der Annahme, dass $\begin{eqnarray*} A(k+1) \end{eqnarray*}$ richtig ist? Damit hast du einen Zirkelschluss.

Stattdessen würde sich anbieten versuchen das $\begin{eqnarray*} k+2 \end{eqnarray*}$ loszuwerden, mit einer (hoffentlich bereits gezeigten) alternativen Rechenregel: Wiki

02.02.2025, 22:18

Johann2124

Auf diesen Beitrag antworten »

Welches der angegebenen Rechenregeln würdest du den nehmen? Ich habe es mit der Regel
$\begin{eqnarray*} \binom{n}{k}=\frac{n-k+1}{k}\binom{n}{k-1} \end{eqnarray*}$
probiert, aber komme da auch nicht weiter. Ich habe:
$\begin{eqnarray*} \binom{\alpha}{k+1} + \binom{\alpha}{k+2} = \binom{\alpha}{k+1} + \frac{\alpha-k-1}{k+2}\binom{\alpha}{k+1}. \end{eqnarray*}$
Was mich aber noch nicht weitergeführt hat.

02.02.2025, 22:38

HAL 9000

Auf diesen Beitrag antworten »

Der direkte Beweis

Zitat:

Original von Johann2124
$\begin{eqnarray*} \binom{\alpha}{k} + \binom{\alpha}{k + 1} = \frac{\alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1)}{k!} + \frac{\alpha (\alpha - 1) \cdots (\alpha - k +1) (\alpha - k)}{(k + 1)!}\\ = \frac{(k + 1) \alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1) + \alpha (\alpha - 1) \cdots (\alpha - k + 1) (\alpha - k)}{(k + 1)!}\\ = \frac{\Big((k + 1) + (\alpha - k)\Big) \alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1)}{(k + 1)!}\\ = \frac{(\alpha + 1) \alpha (\alpha - 1) \cdots (\alpha - k + 2) (\alpha - k + 1)}{(k + 1)!} = \binom{\alpha + 1}{k + 1}. \end{eqnarray*}$

ist richtig, damit bist du ja bereits fertig. Freude

Wenn du aber unbedingt willst, kannst du ihn auch unverändert als Induktionsschritt $\begin{eqnarray*} (k-1)\to k \end{eqnarray*}$ eine Beweises durch Vollständige Induktion übernehmen. Das wäre dann ein Induktionsschritt, der auf einen Rückgriff auf die Induktionsvoraussetzung verzichtet, aber das ist (wie bereits erwähnt) ja nicht verboten. Augenzwinkern

03.02.2025, 12:33

IfindU

Auf diesen Beitrag antworten »

Meine Hoffnung war es so zum Ziel zu kommen
$\begin{eqnarray*} \binom {\alpha + 1} {k+2} = \frac {\alpha + 1} {k+2} \binom {\alpha } {k+1} = \frac {\alpha + 1} {k+2} \left (\binom {\alpha-1 } {k+1} + \binom {\alpha -1} {k} \right) \end{eqnarray*}$ .

Ausmultipliziert
$\begin{eqnarray*} \frac {\alpha + 1} {k+2} \binom {\alpha-1 } {k+1} + \frac {\alpha + 1} {k+2}\binom {\alpha -1} {k}= \left (\frac {\alpha } {k+2} + \frac {1} {k+2} \right)\binom {\alpha-1 } {k+1} + \left( \frac {\alpha } {k+1} - \frac {\alpha } {k+1} +\frac {\alpha } {k+2}+ \frac {1} {k+2} \right) \binom {\alpha -1} {k} \end{eqnarray*}$ und damit
$\begin{eqnarray*} \binom {\alpha + 1} {k+2}= \binom {\alpha} {k+2} + \binom {\alpha} {k+1} + \text{Rest} \end{eqnarray*}$

An der Stelle hätte man schon ein paar richtige Terme und paar die sich noch gegenseitig wegkürzen müssen. An der Stelle wird HAL zu recht behaupten können die restliche Berechnung um Rest=0 zu zeigen ist vermutlich noch aufwändiger als die ganze Aussage direkt nachzurechnen. Aber wenigstens oberflächlich ist es nicht-trivaler Einsatz der Induktionsannahme Augenzwinkern

03.02.2025, 12:57

Johann2124

Auf diesen Beitrag antworten »

@ HAL 9000 und IfindU: Vielen Dank für die Hilfe!

03.02.2025, 13:23

HAL 9000

Auf diesen Beitrag antworten »

Wie viele Themen, war auch dieses schon mal hier im Matheboard aufgeschlagen:

Vollständige Induktion

Wie man sieht, habe ich meine Meinung zu wenig sinnvollen Induktionsbeweisen seitdem nicht geändert.

Neue Frage »

Antworten »

Vollständige Induktion - Anwendung Induktionsvoraussetzung

Verwandte Themen