\(\begingroup\)\(\usepackage{setspace}\)
Immer wieder mal kann man von bestimmten gegebenen Zahlenfolgen eine Rekursionsgleichung erstellen und sucht dann eine Darstellung des allgemeinen Gliedes. Für die Fibonacci-Folge:
c_(n+1) = c_n + c_(n-1) und c_0 = c_1 = 1
ergibt sich z.B.:
c_n=sqrt(5)/(5*2^(n+1))\.((1+sqrt(5))^(n+1)-(1-sqrt(5))^(n+1))
Doch wie kommt man auf sowas?
Angeben kann ich hier nur die Lösung für eine sehr eingeschränkte
Klasse von rekursiv gegebenen Zahlenfolgen, wer Lösungen auch für
andere Klassen kennt, fühle sich frei, diesen Artikel um den
entsprechenden Beitrag zu bereichern.
Gegeben sei die folgende Zahlenfolge:
c_(n+1)= p*c_n + q*c_(n-1)
mit c_0 = a und c_1 = b und a, b, p, q sowie c_n \el\ \IK,
wobei \IK ein beliebiger Körper mit char(\IK)!=2 ist.
Als Lösungsansatz nehmen wir c_n = C^(n+1), das führt auf die
folgende quadratische Gleichung:
C^2=pC+q mit den Lösungen C_1,2 = p/2 +- sqrt(p^2/4 + q)
Um jetzt weiter zu kommen, betrachten wir nun allerdings den
Ausdruck \alpha = sqrt(p^2/4 + q), der ja nicht notwendig Element
von \IK ist, als das zu adjungierende Element eines einfachen
Erweiterungskörpers \IK(\alpha), dessen Elemente x+y\alpha mit
x,y \el\ \IK sind. Die Lösungen der obigen quadratischen Gleichung
seien damit
s=p/2 + \alpha
t=p/2 - \alpha
Der weitere Lösungsansatz für c_n lautet nun:
c_n=As^(n+1)+Bt^(n+1) mit A,B \el\ \IK(\alpha) ! D.h.
A = A_1 + A_2 \alpha
B = B_1 + B_2 \alpha
Die Konstanten A_1 , A_2 , B_1 , B_2 \el\ \IK werden aus dem
folgenden Gleichungssystem bestimmt:
c_0 = As + Bt = a
c_1 = As^2 + Bt^2 = b bzw.
(A_1 +A_2 \alpha)(p/2 + \alpha)+(B_1 +B_2 \alpha)(p/2 - \alpha)=a
(A_1 +A_2 \alpha)(p/2 + \alpha)^2+(B_1 +B_2 \alpha)(p/2 - \alpha)^2=b
und das führt für p^2/4 +q!=0 über einen Koeffizientenvergleich zu
B_1 = A_1
B_2 = -A_2
pA_1+2\alpha^2\.A_2 =a
2(p^2/4 + \alpha^2)\.A_1+2p\alpha^2\.A_2=b bzw.
(p,2\alpha^2;2(p^2/4 + \alpha^2),2p\alpha^2)\.(A_1 ;A_2 )=(a;b)
mit der Lösung für A_1 , A_2 - unter der Ausnutzung von \alpha^2=p^2/4 + q
(A_1 ;A_2)=-1/(2q\alpha^2)\.(p\alpha^2,-\alpha^2;-(p^2/4 + \alpha^2),p/2)\.(a;b)
also
A_1 = (b-ap)/(2q)
A_2 = (a-pA_1 )/(2\alpha^2)
Wir haben also als allgemeine Darstellung für c_n :
c_n = (A_1 +(a-pA_1 )/2\alpha)(p/2 +\alpha)^(n+1) + (A_1 -(a-pA_1 )/2\alpha)(p/2 -\alpha)^(n+1)
mit
\alpha = sqrt(p^2/4 +q)
A_1 = (b-ap)/(2q)
Sollte \IK=\IR sein, so ist dies für p^2/4 +q >0 schon das Ergebnis.
Für den Fall, dass p^2/4 +q < 0 ist, erhalten wir daraus über
x+iy=\rho\.e^i\phi und \alpha '=sqrt(abs(q)-p^2/4):
c_n =abs(q)^((n+1)/2)\.(2A_1 cos(n+1)\phi + (a-pA_1 )/(\alpha ')\.sin(n+1)\phi)
mit
\phi = arctan((2\alpha ')/p)
A_1 = (b-ap)/(2q)
Für den Fall p^2/4 +q=0 erhält man zuguterletzt
c_n = (p/2)^(n-1)\.(nb-(n-1)/2\.ap)
Im übrigen gilt für A_1=0 bzw. b=ap, sowie p^2/4 +q!=0 für c_n die besonders einfache
Darstellung:
c_n = a*(s^(n+1)-t^(n+1))/(s-t)
viel Freude Jens Koch (trunx)
Immer wieder mal kann man von bestimmten gegebenen Zahlenfolgen eine Rekursionsgleichung erstellen und sucht dann eine Darstellung des allgemeinen Gliedes. Für die Fibonacci-Folge:
c_(n+1) = c_n + c_(n-1) und c_0 = c_1 = 1
ergibt sich z.B.:
c_n=sqrt(5)/(5*2^(n+1)).((1+sqrt(5))^(n
\(\begingroup\)Hi trunx,
Als ergänzung zu deinem Artikel habe ich noch folgendes pdf 😄
www.wias-berlin.de/~stephan/folgen.pdf
Dort wird dein Verfahren noch weiter erläutert und auf weitere Rekursionsfolgen verallgemeinert.
Alex\(\endgroup\)
\(\begingroup\)Hi Alex,
vielen Dank für deinen Link. Wichtig war mir in meinem Artikel der Weg über die Körpererweiterung, weil man so auch allgemeiner die Fälle erreicht, in denen keine reelen Nullstellen existieren (sprich, in denen a nicht in IK ist), das wird in dem von dir angegebenen Artikel nicht so gemacht, dennoch auch ein sehr schöner Artikel. 😄
bye trunx\(\endgroup\)
\(\begingroup\)Hallo an alle,
da es nach dem Fundamentalsatz der Algebra zu jedem Polynom k-ten Grades insgesamt genau k (i.a. komplexe, mehrfache) Nullstellen ζi gibt, ist der obige Ansatz zur expliziten Darstellung rekursiv gegebener Zahlenfolgen auf folgende Klasse von rekursiven Zahlenfolgen
cn+k = akcn+k-1 + ak-1cn+k-2 + ... + a2cn+1 + a1cn
mit gegebenen cj, j=0,...,k-1 und k>2 erweiterbar (der Fall k=2 ist oben beschrieben).
Die allg. Lösung lautet dafür:
c_n = sum(\zeta_i ^n\.sum(A_ij\.\alpha^j,j=0,g-1),i=1,k)
wobei g der Körpergrad von K(α), dem Zerfällungskörper des zugeh. Polynoms ist. Da dieser dabei im allgemeinen ≥ k ist, wird natürlich das Gleichungssystem für die Aij entsprechend größer.
bye trunx
EDIT: das ist leider so nicht korrekt, siehe besser hier.\(\endgroup\)
\(\begingroup\) für den Fall:
c_(n+1)=p*c_n+q*c_(n-1)+k
hilft die Substitution
d_n=c_n+k/(p+q-1) weiter, vorausgesetzt, dass p+q-1!=0 ist.
für p+q=1, setze man in
c_(n+1) - c_n =-q(c_n -c_(n-1) )+k
d_n = c_(n+1) -c_n und berechnet
d_n = -qd_(n-1) +k zu
d_n = (-q)^n *d_o +k*(1-(-q)^n)/(1+q)
was zurücktransformiert wiederum
c_n = c_o +(1-(-q)^n)/(1+q)*(c_1 -c_o) +k/(1+q)*(n- (1-(-q)^n)/(1+q))
ergibt, hierbei sollte natürlich q!=-1 sein.
für diesen Fall \(also q=-1 und p=2\) wiederum ist
d_n = d_o +n*k, was zurücktransformiert
c_n = c_o +n*(c_1 -c_o) +k*n/2 *(n-1)
ergibt
bye trunx
\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
