Russische Bauernmultiplikation - Beweis durch vollständige Induktion

23.10.2016, 17:29

AprikosenSchlamm

Russische Bauernmultiplikation - Beweis durch vollständige Induktion

Meine Frage:
Hi,

wie beweist man die russische Bauernmultiplikation (https://de.wikipedia.org/wiki/Russische_Bauernmultiplikation) mittels vollständiger Induktion über die Anzahl der Rechenschritte?

Nehmen wir als Buchstaben mal a und b => a * b
Zu beweisen ist nun: M(a,b) = a * b, wobei M diese Bauernmultiplikation ist

Meine Ideen:
Also mein Problem ist folgendes:

Um die benötigten Schritte der Multiplikation zu bestimmen, braucht man ja einen der Faktoren (sagen wir b). Der muss gegeben sein. Und damit komme ich irgendwie nicht klar.

Für n=1 ist es logisch. Einen einzigen Schritt gibt es nur, wenn b = 1 ist. Und damit geht die Gleichung auf.
Für n=2 gibt es 2 mögliche b. b=2 und b=3. Wie beweist man das jetzt? Für diesen konkreten Fall kann man das ja für b=2 und b=3 getrennt beweisen (a * 2 und a * 3). Aber wenns allgemein wird (also im Induktionsschritt) weiß ich nicht mehr weiter.

Was ich rausgefunden habe ist, dass b immer größer/gleich 2^(n-1) und kleiner 2^n ist. Mein Ansatz wäre dann sowas:

Man fängt mit einem Beweis von $\begin{eqnarray*} M(a, 2^n) \end{eqnarray*}$ an. Das ist nicht schwer, weil $\begin{eqnarray*} 2^n \end{eqnarray*}$ ja immer positiv ist.
d.h. $\begin{eqnarray*} M(a, 2^n) = M(2a, 2^{n-1})= ... = M(2^n * a, 1) = 2^n * a \end{eqnarray*}$

Dann gehts weiter mit $\begin{eqnarray*} M(a, 2^n + 1) \end{eqnarray*}$ . Der erste Schritt ist ja $\begin{eqnarray*} M(2a, 2^{n-1}) + a \end{eqnarray*}$
Und da kann man den Beweis von oben einsetzen und fertig.

So geht das weiter bis $\begin{eqnarray*} M(a, 2^{n+1}) \end{eqnarray*}$ Und hier weiß ich nicht mehr weiter.

Ist das überhaupt der richtige Ansatz? Weil normalerweise muss man ja irgendwo eine Induktionsvoraussetzung einsetzen, aber die ist ja im Prinzip nur:
$\begin{eqnarray*} M(a,b) = a * b \end{eqnarray*}$ für alle n <= 1

Ich weiß nicht, wie ich damit arbeiten soll. Wie gesagt, das gegebene b, dass man da braucht, verwirrt mich.

Danke schon mal für jegliche Hilfe smile

24.10.2016, 12:58

HAL 9000

Auf diesen Beitrag antworten »

Ok, der zweite Faktor $\begin{align*} b \end{align*}$ ist es, den du im Laufe des Verfahrens halbierst. Ich betone das deshalb, damit es zu keinen Missverständnissen kommt, denn in dem von dir verlinkten Wikipedia-Beitrag wurde dafür der erste Faktor genommen.

Dann würde ich die Behauptung so formulieren:

Zitat:

Es ist $\begin{align*} M(a,b)=a\cdot b \end{align*}$ für alle $\begin{align*} b \end{align*}$ mit $\begin{align*} 2^{n-1}\leq b < 2^n \end{align*}$ .

Beweisen kann man das durch Vollständige Induktion über $\begin{align*} n \end{align*}$ .

Im Induktionsanfang $\begin{align*} n=1 \end{align*}$ ist das ganze für $\begin{align*} 2^0\leq b < 2^1 \end{align*}$ nachzuweisen, d.h., da liegt nur $\begin{align*} b=1 \end{align*}$ in diesem Intervall. Dass $\begin{align*} M(a,1)=a \end{align*}$ gilt, ist laut Beschreibung dieser Bauernmultiplikation offensichtlich klar.

Im Induktionsschritt $\begin{align*} n\to n+1 \end{align*}$ betrachten wir $\begin{align*} b \end{align*}$ mit $\begin{align*} 2^n\leq b<2^{n+1} \end{align*}$ und haben dort zwei Fälle zu unterscheiden:

1) $\begin{align*} b \end{align*}$ gerade, d.h. $\begin{align*} b=2b' \end{align*}$ mit $\begin{align*} 2^{n-1}\leq b' < 2^n \end{align*}$ .

2) $\begin{align*} b \end{align*}$ ungerade, d.h. $\begin{align*} b=2b'+1 \end{align*}$ mit $\begin{align*} 2^{n-1}\leq b' < 2^n \end{align*}$ .

In beiden Fällen kann man einen Zusammenhang zwischen $\begin{align*} M(a,b) \end{align*}$ und $\begin{align*} M(2a,b') \end{align*}$ feststellen, und zudem letzteres über die Induktionsvoraussetzung bestimmen, nämlich als $\begin{align*} 2ab' \end{align*}$ .

24.10.2016, 15:09

AprikosenSchlamm

Auf diesen Beitrag antworten »

Danke für die Antwort smile

Okay, ich bin mir nicht sicher, welcher Zusammenhang da existiert.

Meine Idee:

$\begin{eqnarray*} b' \end{eqnarray*}$ ist ja die Hälfte von $\begin{eqnarray*} b \end{eqnarray*}$ . Kann man das dann so schreiben:

$\begin{eqnarray*} M(2a,b') = M(2a, \frac{b}{2}) = M(a, b) \end{eqnarray*}$ ?
Hat das eine Aussage, oder forme ich etwas offensichtliches nur um?

24.10.2016, 15:12

AprikosenSchlamm

Auf diesen Beitrag antworten »

Ich kann leider nicht editieren, tut mir Leid wegen des Doppelposts.

$\begin{eqnarray*} M(2a,b') = M(2a, \frac{b}{2}) = M(a, b) \end{eqnarray*}$

Mein Gedanke da ist es, die Multiplikationsvorschrift rückwärts zu benutzen. also a zu halbieren und b zu verdoppeln. Geht das?

24.10.2016, 15:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von AprikosenSchlamm
Okay, ich bin mir nicht sicher, welcher Zusammenhang da existiert.

Das hängt natürlich vom Fall ab:

1) $\begin{align*} b \end{align*}$ gerade:

Dort gehört der a-Wert der ersten Zeile laut Vorschrift nicht zur Summe, also ist einfach $\begin{align*} M(a,b) = M(2a,b') \end{align*}$

2) $\begin{align*} b \end{align*}$ ungerade:

Hier gehört der a-Wert der ersten Zeile laut Vorschrift zur Summe, also ist hier $\begin{align*} M(a,b) = a+M(2a,b') \end{align*}$ .

Indunktionsvoraussetzung $\begin{align*} M(2a,b')=2ab' \end{align*}$ einsetzen, umformen, fertig.

24.10.2016, 15:56

AprikosenSchlamm

Auf diesen Beitrag antworten »

Ah, okay, macht Sinn. Vielen Dank smile

Neue Frage »

Antworten »

Russische Bauernmultiplikation - Beweis durch vollständige Induktion

Verwandte Themen