Rekursive Folgendefinitionen

03/02/2014 - 14:02 von ram | Report spam
Ich wollte folgende Folge nichtrekursiv definieren:

S( 0 ):= 0
S( n ):= 2 · S( n - 1 )+ 1 n > 0


. Mir fiel auf, daß man die binàre Darstellung eines
Folgenglieds erhàlt, indem man die binàre Darstellung des
vorigen Folgenglieds um 1 nach links verschiebt und rechts
mit 1 auffüllt

n S( n ) binàr
0 0
1 1
2 11
3 111
4 1111

. Ich wußte auswendig, daß sich diese binàre Folge als
2^n-1 schreiben làßt, so daß ich dadurch auf die Lösung

S( n )= 2^n - 1

kam. Wie würde man solche Aufgaben ohne Verwendung der
Binàrdarstellung lösen?
 

Lesen sie die antworten

#1 Roland Franzius
03/02/2014 - 15:24 | Warnen spam
Am 03.02.2014 14:02, schrieb Stefan Ram:
Ich wollte folgende Folge nichtrekursiv definieren:

S( 0 ):= 0
S( n ):= 2 · S( n - 1 )+ 1 n > 0


. Mir fiel auf, daß man die binàre Darstellung eines
Folgenglieds erhàlt, indem man die binàre Darstellung des
vorigen Folgenglieds um 1 nach links verschiebt und rechts
mit 1 auffüllt

n S( n ) binàr
0 0
1 1
2 11
3 111
4 1111

. Ich wußte auswendig, daß sich diese binàre Folge als
2^n-1 schreiben làßt, so daß ich dadurch auf die Lösung

S( n )= 2^n - 1

kam. Wie würde man solche Aufgaben ohne Verwendung der
Binàrdarstellung lösen?





Man setzt

s_n = w_n - 1 = 2 s_(n-1)+ 1 = 2 w_(n-1) - 2 + 1 = 2 w_(n-1)

damit hat man eine homogene lineare Gleichung mit der allgemeinen Lösung

w_n = C 2^n

anolog zu

lim_(1->0,e->2) ( (w_(n+1) - w(n))/ 1 = w'(n) = w(n) :-)


Roland Franzius

Ähnliche fragen