Vollständige Induktion Josephus Nummer |
| 27.10.2012, 01:21 | rsb | Auf diesen Beitrag antworten » |
| Vollständige Induktion Josephus Nummer Ich komm irgendwie nicht weiter. Also unsere Aufgabe ist: Finde alle n für die gilt: J(n) = n/2 Ich habe zur Probe die Josephus-Nummern in einer Tabelle dargestellt und es scheint, als wäre bei n=2 und bei n=10 und n=42 der Fall gegeben. Nun habe ich ein Rekursionsschema versucht aufzustellen - bin aber schon daran gescheitert. Ich wusste nur, dass es heißen muss : Vorgängerzahl * 4 +2, also 2 * 4 +2 = 10 oder dann 4 * 10 +2 = 42. Da habe ich im Internet folgendes Rekursion gefunden: K(m) = 4 * K(m-1) +2. Also das heißt: J(n) = n/ 2 wenn n = K(m) = 4 * K(m-1) +2 Das funktioniert auch alles super. Jetzt muss ich wissen, ob das was ich mache, richtig ist. Also zunächst mache ich den Induktionsanfang und setze m=1 und bekomme für K(1) = 2 raus. Induktionsschritt: Induktionsvoraussetzung: für alle nat. Zahlen n = K(m) gilt J(K(m)) = K(m) / 2 = (4 * (K(m-1) + 2)) / 2 = 2* K(m-1) + 1 Induktionsbehauptung: für K(m) = K(m+1) <-- ist das richtig rausgedrückt? gilt: K(m+1) = 4 * K(m+1-1) +2 Induktionsbeweis: 4 * K(m+1-1) +2 = 4 * K(m) + 2 = 2 ( 2 * K(m) +1) = ??? Wie geht's jetzt weiter? Wie komme ich auf meine Induktionsvoraussetzung? Ich muss doch jetzt irgendwie auf 2* K(m-1) + 1 oder? |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
