Starke Induktion

Aufrufe: 361     Aktiv: 14.12.2020 um 17:50

0

Ich soll folgendes mit starker Induktion zeigen (also anstatt dass beim Induktionsschritt die Aussage nur für n angenommen wird, wird sie für alle k</=n angenommen). Den Induktionsanfang bekomme ich bei beiden hin, aber dann weiß ich nicht wie ich nach der Induktionsannahme weiter machen soll.

Diese Frage melden
gefragt

 

Kennen Sie schon Restklassen?   ─   anonym0165f 08.12.2020 um 17:01

nein, das hatten wir noch nicht in der Vorlesung.   ─   thxforallthefish 08.12.2020 um 17:20
Kommentar schreiben
1 Antwort
0

Zu ii) Verwende für den Induktionsschritt, dass es eine Primzahl \( p \) mit \( \frac{n+1}{2} < p < n+1 \) gibt. Wende dann auf \( n+1-p \) die Induktionsannahme an. Aus der Darstellung von \( n+1-p \) folgt dann die gewünschte Darstellung für \( n+1 \). Und dann musst du dir noch überlegen, dass die Zahlen in dieser Darstellung auch tatsächlich paarweise verschieden sind.

Beachte, dass du hier die Vorraussetzung \( n \ge 2 \) benötigst. Das musst du in deinem Induktionsanfang berücksichtigen.

Zu iii) Hier kannst du für den Induktionsschritt Folgendes tun: Wenn \( n+1 \) bereits eine Zweierpotenz ist, dann gilt die Aussage trivialerweise, andernfalls definiert man die Zahl \( m = \max\{ i \in \mathbb{N} \ \vert \ 2^i < n+1\} \) und wendet die Induktionsannahme auf \( n+1-2^m \) an. Aus der Darstellung von \( n+1-2^m \) folgt dann die gewünschte Darstellung von \( n+1 \). Und dann musst du dir noch überlegen, dass die Zweierpotenzen in dieser Darstellung auch tatsächlich paarweise verschieden sind.

Diese Antwort melden
geantwortet

Student, Punkte: 6.68K

 

Kommentar schreiben