Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Natürliche Zahlen als Summe von Zweierpotenzen

Natürliche Zahlen als Summe von Zweierpotenzen

Schüler

Tags: Induktion, Zweierpotenzen

joda2802 aktiv_icon

19:20 Uhr, 17.11.2017

Hallo,
Ich habe zum Spaß nach einem Induktionsbeweis dafür gesucht, dass sich jede Natürliche Zahl als Summe von paarweise verschiedenen Zweierpotenzen aufschreiben lässt, bin aber nach einigem Suchen und Probieren bin ich noch nicht fündig geworden.

Mein bisheriger Lösungsansatzist wie folgt:

Induktionsanfang:
1 lässt sich als Summe paarweise verschiedener Zweierpotenzen aufschreiben:

1 = 2^{0}

Induktionsannahme
Für alle natürlichen

< n

sei die Behauptung wahr.

Induktionsbehauptung
Dann kann auch

n

als Summe paarweise verschiedener Zweierpotenzen geschrieben werden.

Kennt vielleicht jemand einen Lösungsansatz für den Induktionsbeweis?
Danke im Vorraus!

euer joda2802

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

ledum aktiv_icon

20:03 Uhr, 17.11.2017

Hallo

2^{n}

lässt sich doch nicht als Summe von 2 verschiedenen 2er Potenzen schreiben, genausowenig wie dein

2^{0}

was

j

auch nicht eine summe ist.
du willst wohl zeigen

n = \sum_{k = 0} a_{k} \cdot 2^{k}

mit

a_{k}

aus

(0,1)

dann versuch es mit dieser Formel , ich denke aber es ist einfacher zu zeigen, dass man diese Darstellung durch teilen durch 2 von

n

finden kann oder jeweils die höchste Potenz von 2 subtrahieren.
du kannst ja auch beweisen, dass man jede 2 er Potenz im

10

er System darstellen kann, das ist im Prinzip nichts anderes.
Gruß ledum

joda2802 aktiv_icon

21:03 Uhr, 18.11.2017

Danke für die schnelle Antwort!

Ist dann folgender Lösungsansatz schlüssig?:

Man ziehe von

n

die größte Zweierpotenz(ich nenn sie mal

k)

ab, für die gilt

k < n

und erhält dadurch

n'

. Es muss nun gelten, dass

n' < \frac{n}{2},

k

sonst nicht die
größte Zweierpotenz kleiner

n

wäre. Da angenommen wurde, dass für alle natürlichen Zahlen<n die Behauptung wahr ist, ist auch für

n

die Behauptung wahr, wobei

k

kein Summand von

n'

sein kann,da

n' < \frac{n}{2}

.

Deshalb ist

n = \sum_{i = 0} a_{i} \cdot 2^{i}

mit ai aus

(0,1),

wobei kein Summand doppelt vorkommt.Sonst wäre die Aussage ja trivial und man könnte einfach

n = 2^{0} + 2^{0} + 2^{0} . .

. schreiben.
Danke im Vorraus!

euer joda2802
;-)

ledum aktiv_icon

23:06 Uhr, 18.11.2017

Hallo
zieh mal von

2043

die höchst Potenz von 2 hier also

1024

ab, es bleibt viel mehr als

\frac{n}{2}

.
sei

n

nicht selbst eine 2er Potenz
also sei

2^{k_{1}} < n < 2 \cdot 2^{k_{1}}

subtrahiere

2^{k}

es bleibt ein

m

mit

1 < m < 2^{k - 1}

wiederhole mit dem jetzt kleineren

2^{k_{2}}, 2^{k_{2}} < m < 2 \cdot 2^{k_{2}}

das kann man solange fortführen,

(l

mal bis kein Rest bleibt da der kleinste mögliche Rest 2 oder 1 ist.
dann kann man

n

schreiben als

n = \sum_{i = 1}^{l} 2^{k_{i}}

Gruß ledum

joda2802 aktiv_icon

23:26 Uhr, 18.11.2017

Aber

\frac{2043}{2}

ist doch größer als

2043 - 1024

Gruß
Joda2802

ledum aktiv_icon

13:16 Uhr, 19.11.2017

Hallo
du hast recht, war mein Fehler! sorry
Gruß ledum

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1399310

1398962

	Status: nicht eingeloggt	Noch nicht registriert?