Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:21 Mi 11.11.2009 | | Autor: | Unk |
| Aufgabe | Sei [mm] n\in \mathbb{N}.
[/mm]
Zeigen sie per vollständiger Induktion, dass n sich eindeutig in der Form [mm] n=\sum_{i=0}^{\infty}a_{i}n^{i} [/mm] mit [mm] a_{i}\in\{1,0\} [/mm] schreiben lässt. |
Hallo,
das Ganze weist ja irgendwie auf das Dualsystem hin.
Induktionsanfang ist kein Problem, nur der Induktionsschritt, weil ja auf der rechten Seite in der Summe überhaupt kein n drin ist.
Da weiß ich garnicht, wie ich nach n+1 gehen soll.
Das einzige was ich gemacht habe ist: [mm] n+1=n=\sum_{i=0}^{\infty}a_{i}n^{i}+1=n=\sum_{i=0}^{\infty}a_{i}n^{i}+1\cdot 2^0. [/mm]
Kann ich dann irgendwie sagen [mm] a_0=0 [/mm] und dann den letzten Summandem mit in die Summe ziehen?
Oder macht man das ganz anders?
Gruß Unk
|
|
| |
|
> Sei [mm]n\in \mathbb{N}.[/mm]
> Zeigen sie per vollständiger
> Induktion, dass n sich eindeutig in der Form
> [mm]n=\sum_{i=0}^{\infty}a_{i}n^{i}[/mm] mit [mm]a_{i}\in\{1,0\}[/mm]
> schreiben lässt.
> Hallo,
>
> das Ganze weist ja irgendwie auf das Dualsystem hin.
> Induktionsanfang ist kein Problem, nur der
> Induktionsschritt, weil ja auf der rechten Seite in der
> Summe überhaupt kein n drin ist.
> Da weiß ich garnicht, wie ich nach n+1 gehen soll.
>
> Das einzige was ich gemacht habe ist:
> [mm]n+1=n=\sum_{i=0}^{\infty}a_{i}n^{i}+1=n=\sum_{i=0}^{\infty}a_{i}n^{i}+1\cdot 2^0.[/mm]
> Kann ich dann irgendwie sagen [mm]a_0=0[/mm] und dann den letzten
> Summandem mit in die Summe ziehen?
>
> Oder macht man das ganz anders?
>
> Gruß Unk
Hallo Unk,
ich sehe nicht, was das mit dem Zweiersystem
zu tun haben soll. Falls in der Formel alles richtig
geschrieben ist, kann man doch einfach mal sehen:
Für jede natürliche Zahl n (dafür braucht man
keinen Induktionsbeweis !) gilt offenbar
$\ n\ =\ [mm] 0*1+1*n+0*n^2+0*n^3+\,......$
[/mm]
also $\ n\ =\ [mm] \summe_{i=0}^{\infty}a_i*n^{i}$
[/mm]
wobei [mm] a_i=\begin{cases} 1, & \mbox{für } i=1 \\ 0, & \mbox{falls } i\not=1 \end{cases}
[/mm]
Zu beweisen wäre die Eindeutigkeit dieser
Darstellung für alle [mm] n\in\IN [/mm] (woran ich allerdings
begründete Zweifel habe ...).
Nun kommt mir aber ein schlimmer Verdacht:
nämlich dass du die Gleichung eben wirklich
nicht korrekt wiedergegeben hast und die
Aufgabe doch mit dem Zweiersystem zu tun
hat !
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:56 Mi 11.11.2009 | | Autor: | Unk |
> Nun kommt mir aber ein schlimmer Verdacht:
>
> nämlich dass du die Gleichung eben wirklich
> nicht korrekt wiedergegeben hast und die
> Aufgabe doch mit dem Zweiersystem zu tun
> hat !
>
> LG Al-Chw.
Oh ja natürlich.
Ich hab mich verschrieben. Was man eigentlich induktiv zeigen soll, ist, dass sich jedes [mm] n\in \mathbb{N} [/mm] in der Form [mm] n=n=\sum_{i=0}^{\infty}a_{i}2^{i} [/mm] mit [mm] a_{i}\in\{1,0\} [/mm] schreiben lässt.
Da ergeben sich dann die von mir benannten Probleme für mich.
|
|
|
| |
|
Hallo Unk,
eventuell ist ein Induktionsbeweis nach der
Variablen n gar nicht sehr geeignet. Ich könnte
mir vorstellen, dass man einen Induktionsbeweis
nach der Anzahl der Binärstellen machen kann.
Es ist relativ leicht zu zeigen, dass man jede
natürliche Zahl durch eine Binärdarstellung
beschreiben kann. Es bliebe dann die Eindeu-
tigkeit zu beweisen.
Ich denke an die folgende Methode zur Er-
mittlung der Binärstellen, am Beispiel der
Zahl [mm] 53_{DEC} [/mm] :
53 u
26 g
13 u
6 g
3 u
1 u
[mm] $\Rightarrow\qquad 53_{DEC}\ [/mm] =\ [mm] 110101_{BIN}$ [/mm]
(Die Zahl wird fortlaufend halbiert, dabei werden
halbzahlige Ergebnisse abgerundet. Neben jeder
Zahl notiert man, ob sie ungerade oder gerade
ist. Aus dieser Folge der Paritäten entsteht dann
die Binärentwicklung der Zahl)
LG Al-Chw.
|
|
|
| |
|
Hallo,
ich habe mir mal überlegt, durch welchen einfachen
Algorithmus man das Zählen in Binärzahlen beschrei-
ben kann. Das Zählen von 0 bis [mm] 20_{DEC} [/mm] sieht ja zum
Beispiel so aus:
$\ [mm] n_{DEC}$ [/mm] $\ [mm] n_{BIN}$
[/mm]
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
16 10000
17 10001
18 10010
19 10011
20 10100
Bezeichnen wir die Binärstellen der Zahl n mit [mm] a_{n,i}:
[/mm]
[mm] n=\summe_{i=0}^{\infty}a_{n,i}*2^{i}
[/mm]
Hinweis: [mm] a_{n,0} [/mm] ist die hinterste Binärziffer !
Wie genau entsteht jeweils aus einer der Binärzahlen
die nächste ?
Es gibt ein einfaches Rezept:
Falls die Binärzahl (zu einer natürlichen Zahl n) mit
einer Null endet, so ändere einfach diese hinterste
Ziffer (das ist natürlich das [mm] a_{n,0}) [/mm] zu einer Eins ab.
Andernfalls endet die Binärzahl mit einer Gruppe
von k Einsen, vor welcher eine Null (oder noch gar
nichts) steht. Ändere in diesem Fall die (k+1) hin-
tersten Stellen ab, setze also [mm] a_{n+1,i}:=1-a_{n,i}für [/mm] alle
[mm] i\in\{0,1,2,\,.....\,,k\} [/mm] .
Noch einfacher gesagt: Suche die hinterste
Null in der Binärzahl. Es sei die Ziffer [mm] a_{n,k}.
[/mm]
Setze dann [mm] a_{n+1,i}:=1-a_{n,i} [/mm] für alle [mm] i\in\{0,1,2,\,.....\,,k\}.
[/mm]
Alle anderen Ziffern bleiben so wie sie waren.
$\ [mm] a_{n+1,i}:=\begin{cases}1-a_{n,i}&\mbox{falls}\quad i\le k\\ a_{n,i}&\mbox{sonst}\end{cases}$
[/mm]
(ich sehe zwar noch nicht genau, wie man dies für
einen Induktionsbeweis nutzen soll).
LG Al
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:55 Mi 11.11.2009 | | Autor: | felixf |
Hallo!
> Sei [mm]n\in \mathbb{N}.[/mm]
> Zeigen sie per vollständiger
> Induktion, dass n sich eindeutig in der Form
> [mm]n=\sum_{i=0}^{\infty}a_{i}2^{i}[/mm] mit [mm]a_{i}\in\{1,0\}[/mm]
> schreiben lässt.
>
> das Ganze weist ja irgendwie auf das Dualsystem hin.
> Induktionsanfang ist kein Problem, nur der
> Induktionsschritt, weil ja auf der rechten Seite in der
> Summe überhaupt kein n drin ist.
> Da weiß ich garnicht, wie ich nach n+1 gehen soll.
>
> Das einzige was ich gemacht habe ist:
> [mm]n+1=n=\sum_{i=0}^{\infty}a_{i}2^{i}+1=n=\sum_{i=0}^{\infty}a_{i}2^{i}+1\cdot 2^0.[/mm]
> Kann ich dann irgendwie sagen [mm]a_0=0[/mm] und dann den letzten
> Summandem mit in die Summe ziehen?
Nun, du musst halt binaere Addition machen und den Uebertrag beachten.
> Oder macht man das ganz anders?
Es gibt da verschiedene Moeglichkeiten. Entweder man macht es so wie du gerade.
Oder man verwendet starke Induktion (man nimmt also an, dass die Behauptung fuer alle $n' < n$ stimmt und nicht nur fuer $n' = n - 1$) und zieht von $n$ [mm] $2^k$ [/mm] ab mit $k$ maximal so, dass $n - [mm] 2^k \ge [/mm] 0$ ist. Dann ist $n - [mm] 2^k [/mm] < [mm] 2^k \le [/mm] n$, womit du $n - [mm] 2^k$ [/mm] per Induktion so darstellen kannst. Schliesslich ueberzeugst du dich, dass in dieser Darstellung [mm] $a_k [/mm] = 0$ ist, du also [mm] $a_k [/mm] = 1$ setzen kannst um [mm] $2^k$ [/mm] wieder dazuzuaddieren und $n$ zu erhalten.
LG Felix
|
|
|
|
