Anwendung starke Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Mit [mm] n\in\IN [/mm] sei die Folge [mm] a_n [/mm] definiert:
[mm] a_0 [/mm] := 1, [mm] a_1 [/mm] := 1, [mm] a_n [/mm] := [mm] 3*a_{n-2} [/mm] + [mm] a_{n-1}
[/mm]
Zeigen oder widerlegen Sie mit starker Induktion:
a) [mm] a_n \le 3^n
[/mm]
b) [mm] 3^n \le a_{n+1}
[/mm]
c) [mm] 2^n \le a_{n+2} [/mm] |
Normale Induktion kenne ich, zum Begriff der starken Induktion finde ich immer nur, dass man keinen Induktionsanfang braucht und dass man sich nicht nur auf die Korrektheit der Aussage für n, sondern für alle k [mm] \le [/mm] n verlassen kann.
Das einzige Beispiel was man überall findet ist ein Primzahlbeweis, den ich aber nicht wirklich übersetzt bekomme.
zu den Aufgaben selbst:
a) Wenn [mm] a_n \le 3^n, [/mm] dann [mm] a_{n+1} \le 3^{n+1}, [/mm] also [mm] 3*3^{n-1} [/mm] + [mm] 3^n \le 3^{n+1} [/mm] passt dann mit [mm] 2*3^n \le 3*3^n
[/mm]
b) [mm] 3^n \le a_{n+1} [/mm] nach [mm] 3^{n+1} \le 3*3^{n-1} [/mm] + [mm] 3^n [/mm] funktioniert nicht da [mm] 3*3^n \le 2*3^n [/mm] sein soll
c) [mm] 2^{n+1} \le 3*2^{n-1} [/mm] + [mm] 2^n [/mm] geht auch [mm] 2^{n+1} \le 2^{n-1} [/mm] + [mm] 2^{n+1}
[/mm]
Mein Hauptproblem ist irgendwie: "wie schreibt man das korrekt?"
Das "kein Induktionsanfang" ist für mich irgendwie ein Problem, denn wenn ich nämlich keinen ganz groben Denkfehler drin haben könnte ich exakt den gleichen Beweis für [mm] a_0 [/mm] := 100 oder [mm] a_0 [/mm] := -100 führen und da wären ja offensichtlich a),b),c) alle falsch durch ausprobieren.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:59 Do 10.05.2018 | | Autor: | fred97 |
> Mit [mm]n\in\IN[/mm] sei die Folge [mm]a_n[/mm] definiert:
> [mm]a_0[/mm] := 1, [mm]a_1[/mm] := 1, [mm]a_n[/mm] := [mm]3*a_{n-2}[/mm] + [mm]a_{n-1}[/mm]
> Zeigen oder widerlegen Sie mit starker Induktion:
>
> a) [mm]a_n \le 3^n[/mm]
> b) [mm]3^n \le a_{n+1}[/mm]
> c) [mm]2^n \le a_{n+2}[/mm]
>
> Normale Induktion kenne ich, zum Begriff der starken
> Induktion finde ich immer nur, dass man keinen
> Induktionsanfang braucht
Wo hast Du das denn her ? Natürlich braucht man den Induktionsanfang !
> und dass man sich nicht nur auf
> die Korrektheit der Aussage für n, sondern für alle k [mm]\le[/mm]
> n verlassen kann.
Ja, so etwa kann man die Induktionsvoraussetzung beschreiben.
>
> Das einzige Beispiel was man überall findet ist ein
> Primzahlbeweis, den ich aber nicht wirklich übersetzt
> bekomme.
>
> zu den Aufgaben selbst:
>
> a) Wenn [mm]a_n \le 3^n,[/mm] dann [mm]a_{n+1} \le 3^{n+1},[/mm] also
> [mm]3*3^{n-1}[/mm] + [mm]3^n \le 3^{n+1}[/mm] passt dann mit [mm]2*3^n \le 3*3^n[/mm]
>
> b) [mm]3^n \le a_{n+1}[/mm] nach [mm]3^{n+1} \le 3*3^{n-1}[/mm] + [mm]3^n[/mm]
> funktioniert nicht da [mm]3*3^n \le 2*3^n[/mm] sein soll
> c) [mm]2^{n+1} \le 3*2^{n-1}[/mm] + [mm]2^n[/mm] geht auch [mm]2^{n+1} \le 2^{n-1}[/mm]
> + [mm]2^{n+1}[/mm]
>
> Mein Hauptproblem ist irgendwie: "wie schreibt man das
> korrekt?"
>
> Das "kein Induktionsanfang" ist für mich irgendwie ein
> Problem,
Für mich auch ! Wie gesagt, ein Induktionsanfang ist unabdinglich.
> denn wenn ich nämlich keinen ganz groben
> Denkfehler drin haben könnte ich exakt den gleichen Beweis
> für [mm]a_0[/mm] := 100 oder [mm]a_0[/mm] := -100 führen und da wären ja
> offensichtlich a),b),c) alle falsch durch ausprobieren.
>
Zu den Aufgaben:
a) und c) lassen sich locker mit starker Induktion beweisen.
b) ist schon für n=2 falsch.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:51 Fr 11.05.2018 | | Autor: | tobit09 |
Hallo zusammen!
Es gibt verschiedene Formulierungen von starken Induktionsprinzipien. Manche brauchen einen Induktionsanfang, manche nicht.
Beispiel mit Induktionsanfang:
Sei für jedes [mm] $n\in\IN_0$ [/mm] eine Aussage $A(n)$ gegeben, so dass folgende Bedingungen erfüllt sind:
1. A(0) gilt.
2. Für jedes [mm] $n\in\IN_0$ [/mm] mit der Eigenschaft, dass $A(k)$ für alle Zahlen [mm] $k\in\IN_0$ [/mm] mit [mm] $k\le [/mm] n$ gilt, gilt auch $A(n+1)$.
Dann gilt $A(n)$ für alle [mm] $n\in\IN_0$.
[/mm]
Hier ist die Induktionsanfangs-Bedingung 1. i.A. nicht entbehrlich.
Beispiel ohne Induktionsanfang:
Sei für jedes [mm] $n\in\IN_0$ [/mm] eine Aussage $A(n)$ gegeben, so dass folgende Bedingung erfüllt ist:
3. Für jedes [mm] $n\in\IN_0$ [/mm] mit der Eigenschaft, dass $A(k)$ für alle Zahlen [mm] $k\in\IN_0$ [/mm] mit $k<n$ gilt, gilt auch $A(n)$.
Dann gilt $A(n)$ für alle [mm] $n\in\IN_0$.
[/mm]
Hier impliziert schon Bedingung 3. die Gültigkeit von A(0).
Viele Grüße
Tobias
|
|
|
|
