erste Cunningham-Kette < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:31 Fr 09.10.2009 | | Autor: | itse |
| Aufgabe | Gegeben ist die Rekursion:
[mm] $a_{k+1} [/mm] = 2 [mm] \cdot{} a_k [/mm] + 1, [mm] a_1 [/mm] = 2$
Berechne [mm] a_2, a_3, a_4, a_5, [/mm] stelle das Bildungsgesetz auf und beweise. |
Hallo Zusammen,
folgende Werte ergeben sich für die Rekursion:
[mm] $a_1 [/mm] = 2
[mm] $a_2 [/mm] = 2 [mm] \cdot{} [/mm] 2 +1 = 5$
[mm] $a_3 [/mm] = 2 [mm] \cdot{} [/mm] 5 +1 = 11$
[mm] $a_4 [/mm] = 2 [mm] \cdot{} [/mm] 11 +1 = 23$
[mm] $a_5 [/mm] = 2 [mm] \cdot{} [/mm] 23 +1 = 47$
Nach 2 Stunden des Nachdenkens, bin ich noch immer nicht auf das Bildungsgesetz gekommen, ich habe jedoch folgendes über Wolfram Alpha gefunden für die Zahlenfolge: 2, 5, 11, 23, 47
[mm] $a_k [/mm] = [mm] \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^k -2 \right)$, [/mm] die erste Cunningsham-Kette
1. Induktionsanfang $n = 1: [mm] a_1 [/mm] = [mm] \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^1 -2 \right) [/mm] = [mm] \bruch{1}{2} \cdot{} [/mm] (6-2) = 2 (w)$
2. Induktionsschluss
a, Induktionsannahme: Für $n [mm] \in \IN$ [/mm] gelte [mm] $a_k [/mm] = [mm] \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^k -2 \right)$
[/mm]
b, Induktionsbehauptung: [mm] $a_{k+1} [/mm] = [mm] \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^{k+1} -2 \right)$
[/mm]
c, Induktionsbeweis:
[mm] $a_{k+1} [/mm] = 2 [mm] \cdot{} a_k [/mm] + 1 = 2 [mm] \left( \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^k -2 \right) \right) [/mm] + 1 = 3 [mm] \cdot{} 2^k [/mm] -2 + 1 = 3 [mm] \cdot{} 2^k [/mm] -1$ (*)
Nun noch die Induktionsbehauptung umformen:
[mm] $\bruch{1}{2} \cdot{} \left(3 \cdot{} 2^{k+1} -2 \right) [/mm] = [mm] \bruch{3 \cdot{} 2^{k+1}}{2} [/mm] - 1 = [mm] \bruch{3 \cdot{} 2^k \cdot{} 2}{2} [/mm] - 1 = 3 [mm] \cdot{} 2^k [/mm] - 1$
-> (*) $3 [mm] \cdot{} 2^k [/mm] -1 = [mm] \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^{k+1} -2 \right)$
[/mm]
Stimmt der Beweis? Aber vor allem wie kommt man den auf das Bildungsgesetz? Durch bloses Ausprobieren, hab ich es nicht geschafft.
Gruß
itse
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:41 Fr 09.10.2009 | | Autor: | abakus |
> Gegeben ist die Rekursion:
>
> [mm]a_{k+1} = 2 \cdot{} a_k + 1, a_1 = 2[/mm]
>
> Berechne [mm]a_2, a_3, a_4, a_5,[/mm] stelle das Bildungsgesetz auf
> und beweise.
> Hallo Zusammen,
>
> folgende Werte ergeben sich für die Rekursion:
>
> [mm]$a_1[/mm] = 2
>
> [mm]a_2 = 2 \cdot{} 2 +1 = 5[/mm]
>
> [mm]a_3 = 2 \cdot{} 5 +1 = 11[/mm]
>
> [mm]a_4 = 2 \cdot{} 11 +1 = 23[/mm]
>
> [mm]a_5 = 2 \cdot{} 23 +1 = 47[/mm]
>
> Nach 2 Stunden des Nachdenkens, bin ich noch immer nicht
> auf das Bildungsgesetz gekommen, ich habe jedoch folgendes
> über Wolfram Alpha gefunden für die Zahlenfolge: 2, 5,
> 11, 23, 47
>
> [mm]a_k = \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^k -2 \right)[/mm],
> die erste Cunningsham-Kette
>
> 1. Induktionsanfang [mm]n = 1: a_1 = \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^1 -2 \right) = \bruch{1}{2} \cdot{} (6-2) = 2 (w)[/mm]
>
> 2. Induktionsschluss
>
> a, Induktionsannahme: Für [mm]n \in \IN[/mm] gelte [mm]a_k = \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^k -2 \right)[/mm]
>
> b, Induktionsbehauptung: [mm]a_{k+1} = \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^{k+1} -2 \right)[/mm]
>
> c, Induktionsbeweis:
>
> [mm]a_{k+1} = 2 \cdot{} a_k + 1 = 2 \left( \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^k -2 \right) \right) + 1 = 3 \cdot{} 2^k -2 + 1 = 3 \cdot{} 2^k -1[/mm]
> (*)
>
> Nun noch die Induktionsbehauptung umformen:
>
> [mm]\bruch{1}{2} \cdot{} \left(3 \cdot{} 2^{k+1} -2 \right) = \bruch{3 \cdot{} 2^{k+1}}{2} - 1 = \bruch{3 \cdot{} 2^k \cdot{} 2}{2} - 1 = 3 \cdot{} 2^k - 1[/mm]
>
> -> (*) [mm]3 \cdot{} 2^k -1 = \bruch{1}{2} \cdot{} \left(3 \cdot{} 2^{k+1} -2 \right)[/mm]
>
>
> Stimmt der Beweis? Aber vor allem wie kommt man den auf das
> Bildungsgesetz? Durch bloses Ausprobieren, hab ich es nicht
> geschafft.
Hallo,
die Differenzen der jeweils benachbarten Zahlen sind 3, 6, 12, 24, 48. ...
Das sind übrigens FAST auch die Folgenglieder, die sich darstellen lassen als 3-1, 6-1, 12-1, 24-1...
Mach was draus!
Gruß Abakus
>
> Gruß
> itse
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:53 Sa 10.10.2009 | | Autor: | itse |
Guten Morgen,
die Differenzen werden also pro Zahlenfolge immer verdoppelt: 3, 6, 12, 24, 48
Die Folgeglieder ergeben sich aus:
2 = 3-1
5 = 6-1
11 = 12-1
23 = 24-1
Ich habe nun versucht mit Zweierpotenzen das ganze nachzubilden jedoch fällt hier die 3 aus der Reihe.
Somit komme ich immer nur auf 3 [mm] \cdot{} (2^n [/mm] - 1), gilt nur das erste Glied der Folge. Wie kann ich dies noch umformen um auf die Lösung zu kommen?
Stimmt der Beweis eigentlich so?
Grüße
itse
|
|
|
| |
|
Hallo,
wenn du auf die explizite Bildungsvorschrift selbst kommen willst, musst du (so wie man es immer machen kann) die Berechnungsvorschrift wiederholt auf sich selbst anwenden und auf beliebige n in [mm] a_{k+n} [/mm] erweitern und k=0 setzen.
Der Beweis stimmt natürlich, setzt aber (wie du weißt) voraus, dass man die Lösung schon kennt.
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:30 Sa 10.10.2009 | | Autor: | abakus |
> Guten Morgen,
>
> die Differenzen werden also pro Zahlenfolge immer
> verdoppelt: 3, 6, 12, 24, 48
>
> Die Folgeglieder ergeben sich aus:
>
> 2 = 3-1
> 5 = 6-1
> 11 = 12-1
> 23 = 24-1
>
> Ich habe nun versucht mit Zweierpotenzen das ganze
> nachzubilden jedoch fällt hier die 3 aus der Reihe.
>
> Somit komme ich immer nur auf 3 [mm]\cdot{} (2^n[/mm] - 1), gilt nur
Das ist falsch, das (-1) gehört NICHT in die Klammer.
> das erste Glied der Folge. Wie kann ich dies noch umformen
> um auf die Lösung zu kommen?
Die Bildungsvorschrift lautet [mm] 3*2^{n-1}-1.
[/mm]
Gruß Abakus
>
> Stimmt der Beweis eigentlich so?
>
> Grüße
> itse
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:16 So 11.10.2009 | | Autor: | itse |
> > Guten Morgen,
> >
> > die Differenzen werden also pro Zahlenfolge immer
> > verdoppelt: 3, 6, 12, 24, 48
> >
> > Die Folgeglieder ergeben sich aus:
> >
> > 2 = 3-1
> > 5 = 6-1
> > 11 = 12-1
> > 23 = 24-1
> >
> > Ich habe nun versucht mit Zweierpotenzen das ganze
> > nachzubilden jedoch fällt hier die 3 aus der Reihe.
> >
> > Somit komme ich immer nur auf 3 [mm]\cdot{} (2^n[/mm] - 1), gilt nur
> Das ist falsch, das (-1) gehört NICHT in die Klammer.
> > das erste Glied der Folge. Wie kann ich dies noch
> umformen
> > um auf die Lösung zu kommen?
> Die Bildungsvorschrift lautet [mm]3*2^{n-1}-1.[/mm]
Wie bist du denn darauf gekommen? Vom Gedankengang her meine ich?
Vielen Dank
itse
|
|
|
| |
|
Hallo,
auch wenn du jetzt abakus meintest, man könnte es so machen:
gegeben: [mm] a_{1}, a_{n+1}=2*a_{n} [/mm] +1
Wenden wir die Rekursionsvorschrift auf sich selbst an:
[mm] a_{n+2}= 2*2*a_{n} [/mm] +2*1 +1
[mm] a_{n+3}=2^3*a_{n} +2^2+2^1+2^0
[/mm]
[mm] a_{n+m}=2^m*a_{n}+\summe_{i=0}^{m-1}2^i
[/mm]
Nun kennen wir von den Binärzahlen, dass [mm] \summe_{i=0}^{m-1}2^i +1=2^m [/mm] ist.
-> [mm] a_{n+m}=2^m*(a_{n}+1)-1
[/mm]
Setzen wir nun n=1 und verschieben den Index, dann erhalten wir die Bildungsvorschrift.
lg
|
|
|
|
