Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis Eindeutigkeit

Beweis Eindeutigkeit

Universität / Fachhochschule

Tags: G-adische Darstellung

anonymous

17:28 Uhr, 19.03.2020

Hallo,
im Anhang findet ihr die Aufgabe auf die ich mich beziehe und mein Lösungsansatz.
Es geht darum die Eindeutigkeit der g-adische Darstellung zu zeigen. Ich wähle für

g = 2,

da für mich nur die sogenannte Binärentwicklung interessant ist.
Der Beweis wird durch Induktion über

k

ausgeführt.

Ich bin mir nicht sicher, ob ich die einzelnen Induktionsschritte wirklich verstanden habe.

Mein Problem, ist glaube ich der Schritt, indem a‘ = ∑ai g^(k-i)… hier spielt also die Induktionsannahme ein..

Ist die Induktionsannahme, denn das die Darstellung (siehe Anhang) eindeutig ist für ein beliebiges, aber festes

k

Element von den natürlichen Zahlen...?

Vielleicht kann jemand das mal mit anderen Worten erklären..

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."

pwmeyer aktiv_icon

19:33 Uhr, 19.03.2020

Hallo,

bei diesem Beweis wird die Aussage (Eindeutigkeit für festes

k)

für ein

k > 1

gezeigt. Bei Beweis wird die Aussage für

k - 1

(Induktionsannahme) angewandt auf

a' = \sum_{i = 2}^{k} a_{i} \cdot 2^{k - i} = \sum_{j = 1}^{k - 1} a_{j + 1} \cdot 2^{k - 1 - j}

D . h . :

Für das

a'

sind die Koeffizienten eindeutig.

Gruß pwm

anonymous

20:41 Uhr, 19.03.2020

Hallo,
Danke für deine Antwort.
Dass heißt der Induktionsanfang ist so richtig, wie ich ihn durchgeführt habe.
Gehört dann, die Umformung (siehe Anhang:im IS) nach

a 1

auch noch zum Induktionsanfang ?

Falls dies nicht so ist, habe ich noch nicht verstanden, warum man zunächst behauptet

a 1

sei eindeutig.

__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}__{_}

Ne die Überlegung ist Quatsch.

Ich habe es immer noch nicht ganz verstanden....

Vielleicht sollte ich noch weiter am Anfang beginnen...

Warum führt man die Induktion über

k

durch, wo doch

k

die Länge der Binärzahl angibt..

Im Induktionsanfang ist die Darstellung eindeutig, denn wenn die Länge nur eine Ziffer besitzt, so kann diese nach Voraussetzung nicht Null sein, also ist sie automatisch 1 bzw. man entnimmt es aus der Darstellung für

a

.

Kannst du das vielleicht etwas kleinschrittiger erklären?

Du schreibst, dass bei dem Beweis die Aussage für ein festes

k > 1

gezeigt wird, aber

a'

ist doch gerade die Ziffernfolge (a2,...,ak). Damit kann man die Induktionsvoraussetzung auch nur auf

a 2

etc anwenden ? Oder kann man die Annahme auf alle a2,a3,...,ak anwenden ?

Warum machst du einen Indexshift?
Was sollte damit deutlich werden?
Liebe Grüße

anonymous

21:15 Uhr, 19.03.2020

Oder ist die Idee die Folgende:

Induktionsanfang ist klar.

Induktionsvoraussetzung/Induktionsannahme: Die Darstellung sei für ein festes

k > 1

bereits eindeutig.

Induktionsschritt: Zu zeigen ist, falls

k

gilt, dann auch

k + 1

Sei

k > 1 . .

. dann wird

a 1

ermittelt und man stellt fest, dass die

a 1

eindeutig ist.

Dann unterscheidet man für

a'

zwei Fälle, wobei Fall 1 für

a' = 0

ebenfalls eindeutig ist.

Im zweiten Fall spielt nun die Induktionsannahme eine Rolle. Nach dieser ist

a'

eindeutig, da

a' = (a 2, a 3, ... .)

und demnach ist

k > 1

.

Ganz richtig ist das aber immer noch nicht..

: - (

pwmeyer aktiv_icon

21:21 Uhr, 19.03.2020

Hallo,

Die Behauptung ist:

\sum_{i = 1}^{k} a_{i} \cdot 2^{k - i} = \sum_{i = 1}^{k} b_{i} \cdot 2^{k - i} \Rightarrow a_{i} = b_{i}

für

i = 1 ... k

Der INduktionsbeweis wird bezüglich der Länge

k

der Binärzahlen geführt.

Induktionsanfang,

k = 1

. Es gibt nur eine einstellige Binärzahl, nämlich

1 = 1 \cdot 2^{0}

.

Der Induktionsschluss wird für

k - 1 \to k

aufgeschrieben.

Wenn als ein

a = \sum_{i = 1}^{k} a_{i} \cdot 2^{k - i}

gegeben ist, dann wird zunächst gezeigt, dass dadruch

a_{1}

eindeutig bestimmt ist. Ok

Was ist mit

a_{2}, . .

a_{k}

?

Das sind die Koeffizienten von

a' = a - a_{1} \cdot 2^{k}

a'

hat eine Binärdarstellung der Länge

k - 1

(das wollte ich durch den Indexshift auch formal deutlich machen), also sind durch

a'

die Koeffizienten

a_{2}, . .

a_{k}

nach Induktionsvoraussetzung ebenfall eindeutig bestimmt.

Gruß pwm

anonymous

22:07 Uhr, 19.03.2020

Ahh..
mir ist der Ablauf nun schon viel klarer geworden. Das nennt man doch dann doch auch eine "allgemeine Induktion" oder ?

Ich sende morgen erneut den Beweis, so wie ich ihn dann aufschreiben würden. Es wäre super, wenn du da dann noch einmal drüber gucken könntest.

Liebe Grüße

anonymous

22:07 Uhr, 19.03.2020

anonymous

09:35 Uhr, 20.03.2020

Hallo,

ich Anhang füge ich Foto ein, so wie ich die Induktion nun aufschreiben würde.

Ist sie dann formal korrekt ?

Über eine Rückmeldung wäre ich sehr dankbar.

pwmeyer aktiv_icon

10:19 Uhr, 20.03.2020

Dazu zwei Bemerkungen:

Du schreibst "... gelte für ein festes aber beliebiges k'<k..". Die Induktionsvoraussetzung muss für

k - 1

gelten, Du führst ja den Induktionsschritt aus für

k - 1 \to k

.

Die Abschätzung

a - a_{1} \cdot 2^{k - 1} < 2^{k - 1}

müsste aus meiner Sicht begründet werden.

Gruß pwm

anonymous

11:12 Uhr, 20.03.2020

Danke,
ich habe die Induktionsvoraussetzung nun verändert und versucht eine Begründung zu formulieren für die Abschätzung. (Siehe Anhang)

Was meinst du dazu ?

Liebe Grüße,
Lena

pwmeyer aktiv_icon

13:13 Uhr, 20.03.2020

Hallo,

das habe ich nicht verstanden. Warum nimmst Du nicht die Begründung aus dem gedruckten Text, nämlich den von Dir markierten grünen Teil, der diese Ungleichung durch eine einfache Abschätzung liefert.

Gruß pwm

anonymous

13:25 Uhr, 20.03.2020

Das habe ich nun nicht verstanden..
Wie schätze ich das damit ab ?

Ich habe gerade überlegt, aber momentan fällt mir nichts ein..sorry

pwmeyer aktiv_icon

18:24 Uhr, 20.03.2020

Hallo,

naja, die

a_{i}

sind 0 oder 1 also jedenfall

\leq 1,

damit:

a' = \sum_{i = 2}^{k} a_{i} \cdot 2^{k - i} \leq \sum_{i = 2}^{k} 2^{k - i} = \sum_{j = 0}^{k - 2} 2^{j} = 2^{k - 1} - 1 < 2^{k - 1}

Dabei habe ich die Formel für die geometrische Summe verwendet.

Gruß pwm

anonymous

14:36 Uhr, 21.03.2020

Hallo,
danke für die Antwort.

Was ist das

j

bei deiner Indexverschiebung ? ist das

j = k - i - 2

anonymous

14:40 Uhr, 21.03.2020

Muss man

j

noch irgendwo definieren?

pwmeyer aktiv_icon

19:36 Uhr, 21.03.2020

Hallo,

es ist

j = k - i

.

Gruß pwm

anonymous

10:31 Uhr, 23.03.2020

Ich habe noch eine Rückfrage bezüglich deines Indexshifts. Ich hätte ihn so wie im Anhang zu sehen ist durchgeführt. Warum ist

j

dann

k - i

? Das ergibt für mich keinen Sinn?

Kann ich das nicht einfach so schreiben, wie ich das im Anhang gemacht habe oder ist es dann unvollständig ?

anonymous

13:28 Uhr, 23.03.2020

@pwmeyer,
ich habe noch einer Frage zum Induktionsanfang.

Du schreibst, "es gibt nur eine einstellige Binärzahl", aber es gibt doch auch die Binärziffer 0 ?

ermanus aktiv_icon

13:29 Uhr, 23.03.2020

Hallo,
wie begründest du denn das letzte Gleichheitszeichen im Anhang?
Gruß ermanus

anonymous

13:31 Uhr, 23.03.2020

Naja,

wenn man sich

z . B

. für

k = 5

die Summe einmal hinschreibt, ist es ja eben genau das gleiche, nur das die Summanden in anderer Reihenfolge aufsummiert werden oder sehe ich das falsch?

anonymous

13:37 Uhr, 23.03.2020

Kann ich den Induktionsanfang nicht wie folgt argumentieren,

Für die binäre Länge

k = 1

gibt es nur eine eindeutige Darstellung nämlich

a = a 1 \cdot 2^{0} =

(Nach Voraussetzung) 1

- \to

Die natürliche Zahl 1 entspricht also im Binärsystem der Ziffer 1.

ermanus aktiv_icon

13:39 Uhr, 23.03.2020

Und wozu benötigst du dann überhaupt die "Shifterei"?
Einzig ausschlaggebend ist also dann wohl die Gleicheit der Mengen

{k - i ∣ i = 2, \dots, k}

und

{j ∣ j = 0, \dots, k - 2}

,
die ja offensichtlich ist.
Die Zuordnung

j = k - i

von pwmeyer ist eine passende Bijektion.

anonymous

13:42 Uhr, 23.03.2020

Ich habe das ganze geschiftet, um die geometrische Summenformel anzuwenden, denn ich dachte dafür muss der Startindex bei 0 beginnen..?

Kann ich das nun so machen, wie ich es gemacht habe ?

ermanus aktiv_icon

13:48 Uhr, 23.03.2020

Du hast doch nun bereits die Gleichheit der beiden Summen

\sum_{i = 2}^{k} 2^{k - i} = \sum_{j = 0}^{k - 2} 2^{j}

.
Die ist ja durch die Gleichheit der Exponentenmenge hinreichend
nachgewiesen. Und in der rechten Seite beginnt der Index bereits bei

0

.
Wozu willst du da denn noch etwas shiften?

anonymous

13:53 Uhr, 23.03.2020

Ja okay,

aber ich würde gerne mit einem Indexshift arbeiten.
Angenommen ich hätte diese Gleichheit nicht gesehen,
dann hätte ich erstmal einen Indexshift durchgeführt, weil ich eher die geometrische Summenformel im Hinterkopf gehabt hätte...

Kann ich im Exponent dann einfach

k - 2 - i

für

j

austauschen ?

Oder wäre das formal nicht ganz richtig ?

anonymous

13:55 Uhr, 23.03.2020

Ich würde den Induktionsanfang wie folgt formulieren.
Für die Länge

k = 1

der binären Ziffernfolge existiert nur die eindeutige Darstellung

a = a 1 \cdot 2^{0} =

(Nach Vor.)

1 \cdot 2^{0} = 1

.

Die natürliche Zahl 1 lässt sich also eindeutig durch die Binärziffer 1 darstellen.

ermanus aktiv_icon

14:00 Uhr, 23.03.2020

Ich beziehe mich auf 13:53:

Das wäre doch ganz unbegründet.
Es kommt in Wirklichkeit darauf an, welche Exponentenmenge du erzeugen
willst, und das ist hier die Menge

{k - 2, \dots, 0}

,
die man wunderbar als

{j ∣ j = 0, \dots, k - 2}

beschreiben kann.
Damit man einen Anfangsindex zu 0 machen kann, ist ein Shift
ja nun nicht das Generalrezept, zumal hier die Reihenfolge
umgekehrt(!) werden muss. Du hättest dich nur um die auftretenden
Exponenten kümmern müssen.

anonymous

14:11 Uhr, 23.03.2020

Ja das stimmt @ermanus und womöglich ist dies auch die schönere Lösung...

aber prinzipiell spricht doch auch nichts gegen mein Lösungsweg oder ??

Die Frage ist nur, ob ich irgendein Kommentar zu

j

schreiben müsste.

ermanus aktiv_icon

14:18 Uhr, 23.03.2020

Ich rate dir eher, diesen Shift nicht durchzuführen.
Damit vernebelst du einen absolut klaren Beweisschritt.
Warum erst verschieben, dann umdrehen und zum Schluss wegen
Erklärungsbeibringe-Schuld einen Riesenaufwand betreiben zu müssen,
wo dann vermutlich in der Begründung wieder zurückgeshiftet
werden muss.
Kurz: dein geliebter ;-) Shift ist mehr als überflüssig, eher hinderlich.

anonymous

14:51 Uhr, 23.03.2020

Ja gut,
vielen Dank für deine Geduld @ermanus.

Ich werde dann über die Exponentenmenge argumentieren.

Nun bleibt nur noch der Induktionsanfang offen.

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

1497583

1497324

	Status: nicht eingeloggt	Noch nicht registriert?