nicht angemeldet
Gunnar Bittersmann@@Mike:
nuqneH
Warum macht er bei ungeraden nicht einfach +1 um wieder die Geraden-Regel anzuwenden?
Kann man machen:
[latex]a_n = \begin{cases}a_{n-1}/2, & \text{wenn }a_{n-1}\text{ gerade,}\a_{n-1}+1, & \text{wenn }a_{n-1}\text{ ungerade.}\end{cases}[/latex]
Allerdings ist der Beweis, dass man nach endlich vielen Schritten immer 1 rauskommt, dann aber recht einfach. Mit vollständiger Induktion:
Induktionsanfang: Der Algorithmus kommt für die Startwerte a₀ = 1 und a₀ = 2, a₁ = 2/2 = 1 bei 1 an.
Induktionsschritt: Unter der Annahme, dass der Algorithmus für alle Startwerte a₀ < 2k - 1 bei 1 ankommt, ist zu zeigen, dass er das auch für a₀ = 2k - 1 und a₀ = 2k tut. (k ∈ ℕ, k ≥ 2)
Beweis für a₀ = 2k: a₁ = 2k/2 = k. Da k < 2k - 1, kommt der Algorithmus laut Induktionsvoraussetzung bei 1 an.
Beweis für a₀ = 2k - 1: a₁ = a₀ + 1 = 2k. Dass der Algorithmus dann bei 1 ankommt, wurde eben gezeigt.
Qapla'
Gut sein ist edel. Andere lehren, gut zu sein, ist noch edler. Und einfacher.
(Mark Twain)
Der Martin