Jede natürliche Zahl kann durch Zweierpotenzen dargestellt werden.

Neue Frage »

Sam45 Auf diesen Beitrag antworten »
Jede natürliche Zahl kann durch Zweierpotenzen dargestellt werden.
Meine Frage:
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
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.
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.
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?
Sam45 Auf diesen Beitrag antworten »

Und tmo, von welcher Summenformel gehst du denn aus, wenn du mit der Induktion die allgemeine Gültigkeit nachweist?
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?
 
 
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.
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
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »