Jede natürliche Zahl kann durch Zweierpotenzen dargestellt werden. |
23.08.2011, 17:25 | Sam45 | Auf diesen Beitrag antworten » |
Jede natürliche Zahl kann durch Zweierpotenzen dargestellt werden. Ich möchte gerne beweisen, dass JEDE natürliche Zahl durch die Summe vo Zweierpotenzen dargestellt werden kann. Kann mir jemand dabei behilflich sein, einen geeigneten Ansatz bzw. eine Summenformel aufzustellen? Vielen Dank schon einmal im Voraus Meine Ideen: Differenzierung von geraden und ungeraden Zahlen? N(gerade)= 2^k + 2^p N(ungerade)= 2^k + 2^p + 2^0 |
||
23.08.2011, 17:43 | tmo | Auf diesen Beitrag antworten » |
Du meinst wohl, dass jede natürliche Zahl als Summe paarweise verschiedener Zweier-Potenzen dargestellt werden kann. Sonst wäre die Aussage ja trivial und man würde einfach schreiben. Der Beweis dieser präzsieren Aussage ist ein Fall für Induktion: n = 1 : klar. n > 1: Betrachte die größte 2er-Potenz, die nicht größer als n ist, und ziehe sie von n ab. |
||
23.08.2011, 18:42 | Elvis | Auf diesen Beitrag antworten » |
Für jede natürliche Zahl kann jede natürliche Zahl n eindeutig als Summe von b-Potenzen dargestellt werden : , wobei die Koeffizienten aus sind. Für b=10 erhält man die Dezimalzahlen, für b=2 die Dualzahlen. Eindeutig wird die Darstellung dadurch dass man fordert dass für der Koeffizient von 0 verschieden ist. |
||
24.08.2011, 11:11 | Sam45 | Auf diesen Beitrag antworten » |
Vielen Dank für eure schnellen Antworten! Elvis, wenn du sagst, dieser Beweis kann für jede beliebige Basis gelingen. Wie führst du den Beweis denn weiter? |
||
24.08.2011, 11:13 | Sam45 | Auf diesen Beitrag antworten » |
Und tmo, von welcher Summenformel gehst du denn aus, wenn du mit der Induktion die allgemeine Gültigkeit nachweist? |
||
24.08.2011, 11:51 | Leopold | Auf diesen Beitrag antworten » |
Da braucht man keine Summenformel. Den Induktionsanfang hat tmo bereits geliefert: ist "Summe" paarweise verschiedener Zweierpotenzen, nämlich . Jetzt der Induktionsschluß. Induktionsannahme Für alle natürlichen Zahlen sei die Behauptung wahr. Das heißt, jede solche Zahl kann als Summe paarweise verschiedener Zweierpotenzen geschrieben werden. Induktionsbehauptung Dann kann auch als Summe paarweise verschiedener Zweierpotenzen geschrieben werden. Beweis (Induktionsannahme -> Induktionsbehauptung) Da die Zweierpotenzen streng monoton wachsen, muß zwischen zwei Zweierpotenzen liegen: Jetzt wende auf ( ist kleiner als ) die Induktionsannahme an. Was ist alles zu beachten? |
||
Anzeige | ||
|
||
24.08.2011, 13:31 | René Gruber | Auf diesen Beitrag antworten » |
Die Alternativvariante des Induktionsschrittes ist, für die beiden möglichen Fälle gerade () sowie ungerade () die Induktionsvoraussetzung für zu nutzen. |
||
24.08.2011, 18:02 | Sam45 | Auf diesen Beitrag antworten » |
Danke nochmal für eure Antworten. Reicht dieser Beweis, um zu zeigen, dass der ägyptische Multiplikationsalgorithmus immer funktioniert? Aufgabe: 12 x 13 1 13 2 26 / 4 52 / 8 104 4+8= 12 52+104= 156 |
|