Induktionsaufgabe

12.11.2006, 19:12

Lukas33

Induktionsaufgabe

Zeigen Sie, dass jede natürliche Zahl $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq n\leq q^N -1 \end{eqnarray*}$ als Linearkombination von Potenzen einer Basis $\begin{eqnarray*} q\in \mathbb N \end{eqnarray*}$ , q>1, darstellbar ist, d.h. dass gilt

$\begin{eqnarray*} n= \sum_{i=0}^{N-1}~d_i \cdot q^i , N\in \mathbb N , d_i \in \\ {0,...,q-1} \end{eqnarray*}$

Dies soll mit der vollständigen Induktion und mit Hilfe der Formel für die geometrische Reihe gelöst werden.

EDIT: Latex korrigiert (klarsoweit)

12.11.2006, 20:05

Dual Space

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe
Hast du eigene Ideen oder Ansätze? Was genau bereitet dir bei dieser Aufgabe Probleme?

12.11.2006, 20:06

Abakus

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe
OK, was sind deine Ideen zu der Aufgabe ? Zunächst wirst du entscheiden müssen, über welche Variable du die Induktion ansetzt.

Grüße Abakus smile

EDIT: zu langsam

12.11.2006, 20:58

Lukas33

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe
Ich hab ein Problem damit wo ich die Induktion ansetzen soll. Die eine Seite ist mir klar (denke ich zumindest). Da muss doch

$\begin{eqnarray*} \sum_{i=0}^{N-1}~d_i \cdot q^i \end{eqnarray*}$ stehen. Ich weiß nur nicht was ich auf die andere Seite schreiben muss um eine Induktion durchzuführen.

edit (Abakus): Latex

12.11.2006, 23:08

Abakus

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe
Das sagt noch nicht, über welche Variable die Induktion läuft. Mein Vorschlag wäre N zu nehmen.

Ansonsten ist die Behauptung eine "für alle.... existieren...." Aussage. Auf der anderen Seite der Gleichung steht die an den Allquantor gebundene Variable.

Der erste Schritt wäre nun der Induktionsanfang.

Grüße Abakus smile

13.11.2006, 08:55

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe
Also einen Induktionsbeweis über n halte ich für sinnvoller.

13.11.2006, 13:27

Abakus

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe

Zitat:

Original von klarsoweit
Also einen Induktionsbeweis über n halte ich für sinnvoller.

Das wäre eine andere Möglichkeit. In jedem Fall müssen wir vorher festlegen, über welche Variable die Induktion laufen soll.

Ansonsten können wir auch beide Möglichkeiten austesten Augenzwinkern

.

Grüße Abakus smile

17.11.2006, 15:48

Sugarfeet

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe
Ich habe zufällig die gleiche Aufgabe zu bearbeiten.

Die Induktion soll über n laufen. Mir ist nur nicht ganz klar wie ich den Induktionsschluss bewältige.

Rauskommen muss doch
$\begin{eqnarray*} n+1= \sum_{i=0}^(N-1)~d_i \cdot q^i +1 \end{eqnarray*}$

Ich verstehe nicht wie man eine Induktion über n laufen lassen kann, obwohl n nicht auf der rechten Seite auftaucht verwirrt

17.11.2006, 20:17

Sugarfeet

Auf diesen Beitrag antworten »

RE: Induktionsaufgabe
Kann mir nicht jemand helfen, ich bin echt am Verzweifeln... Hammer

17.11.2006, 20:42

Auf diesen Beitrag antworten »

Ich würde mir nicht vorschreiben lassen, wie ich den Beweis zu führen habe - Hauptsache er ist richtig. Und da bin ich ganz Abakus' Meinung: Induktion über $\begin{eqnarray*} N \end{eqnarray*}$ passt hier am besten.

Induktionsanfang $\begin{eqnarray*} N=1 \end{eqnarray*}$ sollte klar sein.

Im Induktionsschluss $\begin{eqnarray*} (N-1)\to N \end{eqnarray*}$ liege eine Zahl $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq n \leq q^N-1 \end{eqnarray*}$ vor. Die teilen wir - mit Rest - durch $\begin{eqnarray*} q \end{eqnarray*}$ , dabei ergebe sich Quotient $\begin{eqnarray*} n' \end{eqnarray*}$ und Rest $\begin{eqnarray*} r \end{eqnarray*}$ , also

$\begin{eqnarray*} n = qn' + r \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq r\leq q-1 \end{eqnarray*}$

Wie unschwer zu erkennen ist, erfüllt $\begin{eqnarray*} n' \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} 0\leq n' \leq q^{N-1}-1 \end{eqnarray*}$ , also kann darauf die Induktionsvoraussetzung angewendet werden...

Mehr sollte ich jetzt nicht mehr verraten müssen.

18.11.2006, 15:53

Sugarfeet

Auf diesen Beitrag antworten »

Gut, jetzt haben wir die Induktion nach N, wie geht es nach n? verwirrt

18.11.2006, 21:01

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Sugarfeet
Gut, jetzt haben wir die Induktion nach N, wie geht es nach n? verwirrt

Versuche Arthurs Idee einfach zu übertragen. Viel wird sich dabei am Gedankengang nicht ändern, also versuche es mal.

Grüße Abakus smile

Neue Frage »

Antworten »

Induktionsaufgabe

Verwandte Themen