Wie Beweise ich das:

Erste Frage Aufrufe: 82     Aktiv: 09.03.2021 um 17:50
1
Das funktioniert per Induktion über die Anzahl der Schritte \(n\), die der Algo braucht.

Wenn \(n=0\), dann ist das ganze ja multiplikation mit \(1\) also klar.

Sei nun \(n+1 \in \mathbb{N}\) und die zu multiplizierenden zahlen seien \(a\) und \(b\) (\(a\) sei die linke zahl und \(b\) die rechte).
Falls nun \(a\) gerade ist, sind wir fertig, weil dann im zweiten schritt die induktions Hypothese anwendbar ist.
Falls nun \(a\) ungerade ist, erhalten wir, wenn wir den algo ab dem zweiten schritt betrachten, wegen Induktions Hypothese genau \(\frac{a-1}{2} \cdot 2b = (a-1) \cdot b\). da ja aber \(a\) ungerade, (und wir am ende vom algorithmus ja alle rechts stehenden zahlen addieren müssen, bei denen die linke ungerade ist) ist auch \(b\) einer der summanden. nach induktions Hypothese folgt also auch in dem falle, dass wir \((a-1)\cdot b + b= a\cdot b\) erhalten. 

Hoffe das ist so verständlich genug, falls nicht wär am besten du zeichnest dir die allgemeine situation mal auf
Diese Antwort melden
geantwortet

Student, Punkte: 2.27K
 

Was meinst du genau mit ind Hyp?   ─   florin.bucherer_s2018 09.03.2021 um 12:48

induktions hypothese. habs im text abgeändert   ─   b_schaub 09.03.2021 um 13:22

Danke vielmals, ich habe es zwar noch nicht ganz verstanden, werde es aber hoffentlich verstehen, wenn ich es noch einmal alles aufzeichne. Was ich bis jetzt verstanden habe (nachdem ich google gefragt habe, was induktionshypothese überhaubt ist) ist zwar kompliziert aber logisch (Wie alles in mathe :) )   ─   florin.bucherer_s2018 09.03.2021 um 17:50

Kommentar schreiben