Einen Beweis im Zusammenhang mit Fibonacci-Zahlen verstehen.

(Dies ist jetzt eine lange Antwort, aber Sie können nach jedem Abschnitt aufhören. Jeder Abschnitt verfolgt nur einen anderen Ansatz oder weist auf Ähnlichkeiten mit anderen Arten von Problemen hin.)

Wenn Sie das zum ersten Mal sehen, erscheint es angesichts der Reihenfolge, in der die Dinge normalerweise gelehrt werden, willkürlich. Es wird klarer, wenn Sie sehen, wie sich die Rekursion entweder in der linearen Algebra oder in erzeugenden Funktionen verhält.

Sie können natürlich direkt beweisen, dass die Formel wahr ist. Wenn$g_n$ ist die Formel, die du nur zeigen musst $g_0=0,g_1=1,$ und $g_{n+1}=g_n+g_{n-1}.$

Aber das ist kein befriedigender Grund, warum es diese Form annimmt.

Wenn wir eine erzeugende Funktion definieren:

Dann erhältst du mit Partialbrüchen aus der Infinitesimalrechnung, wenn $r_1,r_2$ sind die Wurzeln von $y^2-y-1=0,$ dann für einige $a_1,a_2$:

Wenn das Polynom im Nenner sich wiederholende Nullstellen hat, wie es bei Partialbrüchen üblich ist, lautet Ihr allgemeiner Term, wenn der Grad einer Nullstelle $r_i$ im Polynom ist $d_i,$

Der Ansatz der linearen Algebra ist zu beachten:

Also wenn $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ du hast:

Die Matrix $A$ hat charakteristisches Polynom $x^2-x-1,$ die zwei verschiedene Wurzeln hat, also gibt es eine Matrix $S$ so dass:

So können wir die Einträge von ausdrücken $A^n$ jeder wie $a_{ij}r_1^{n}+b_{ij}r_2^n,$ und damit ähnlich für $f_n.$

Wie bei Partialbrüchen wird die Form der Matrix, die Sie erhalten, wenn das Polynom wiederholte Nullstellen hat, komplizierter. Sie können im Allgemeinen keine Diagonalmatrix erhalten, sondern nur eine Matrix in Jordan-Normalform.

Eine dritte Möglichkeit, es sich vorzustellen, ist der Vektorraum aller Folgen $\mathbf a=(a_i)_{i=0}^\infty$ und der lineare Operator:

Dann bedeutet unsere Wiederholung, dass wenn $\mathbf f=(f_i)$ dann $(D^2-D-I)\mathbf f=0,$ Hier $I$ ist der Identitätsoperator $I\mathbf a=\mathbf a.$

Schreibe das um als:

Dann lass

Dann seit $(D-r_1I)\mathbf e =0$, du bekommst das $e_i=r_1^ie_0.$

Ähnlich, $d_i=f_{i+1}-r_1f_i$ gibt $d_i=r_2^id_0,$ so

So

Dann benutze das

Und

Und deshalb lassen $c_1=e_0,c_2=d_0,$ du erhältst:

Gegeben $r_i=\frac{1\pm\sqrt 5}{2},$ $2r_i-1=\pm\sqrt 5$ und $d_0=e_0=1,$ du erhältst:

Im allgemeineren Fall, wenn $p(x)$ ein Polynom ohne wiederholte Nullstelle ist, dann $\gcd(p(x),p’(x))=1.$ (Im Fall von Fibonacci, $p(x)=x^2-x-1$ und $p’(x)=2x-1.$) Dann:

Dann wenn $p(D)\mathbf a=0,$ du erhältst $p_j(D)\mathbf a$ ist eine geometrische Reihe mit gemeinsamem Verhältnis $r_j,$ und

Aber die GCD-Anforderung bedeutet, dass wir eine Lösung für Folgendes haben:

(Bei Fibonacci, $u(x)=(2x-1)/5, v(x)=4/5,$ nach (2).)

Das bedeutet also:

Und das gibt Ihnen:

Diese Technik funktioniert bis (3) mit wiederholten Wurzeln, außer Sie erhalten $p’(x)=\sum_j d_ip_i(x).$ Aber in (3) ist das Beste, was Sie bekommen können:

Dieser letzte Ansatz bezieht sich auf die lineare Differentialgleichung, bei der Ihnen oft zuerst beigebracht wird: „Hey, versuchen wir es einfach mit bestimmten Lösungen der Form try $e^{rx},$“ ohne viel Motivation.

Im Vektorraum unendlich differenzierbarer Funktionen erhalten wir einen linearen Operator $D$ definiert als

Dann können lineare Differentialgleichungen geschrieben werden als $p(D)f=0$ für ein Polynom $p.$

Wie zuvor, wenn $p(x)$ keine wiederholten Wurzeln hat, erhalten Sie: $g_i=p_i(D)f$ ist eine Wurzel von $(D-r_i)g_i=0$ oder $g_i’(x)=r_ig_i(x),$ die eine bekannte Lösungsmenge hat $g_i(x)=C_ie^{r_ix}.$

Dann

Im Wesentlichen finden wir Lösungen für $p(D)f=0$ in Bezug auf bekannte Eigenvektoren $v_i$ des linearen Operators $D$ für Eigenwerte $r_i,$ und es wird immer komplizierter, wenn es wiederholte Wurzeln gibt.

Sogar der Ansatz der linearen Algebra funktioniert auf diese Weise.

$A$ befriedigt $p(A)=0,$ also ein beliebiger Vektor $\mathbf v$ wir bekommen $\mathbf v_i=p_i(A)\mathbf v$ ist ein Eigenvektor von $A$ für Eigenwert $r_i.$

So

Und:

Im Fibonacci-Fall ist $\mathbf v=(1,0)^t$ und $\mathbf v_i=(1-r_{3-i},1)^t=(r_i,1)$ und $u(r_i)=(2r_i-1)/5=\pm\frac{1}{\sqrt5}.$.

Wenn Sie jemals Differentialgleichungen studiert haben, sind Sie wahrscheinlich auf etwas Ähnliches gestoßen, bei dem eine Lösung einer bestimmten Form vorgeschlagen wird und dann funktioniert. Dies ist kein Zufall, da die Theorien der Differentialgleichungen und der Rekursionen einige Gemeinsamkeiten aufweisen. In beiden Situationen ist es üblich, dass sich die Schüler unzufrieden fühlen, wenn sie zum ersten Mal auf diese Art von Argumentation stoßen.

Einige Dinge, die psychologisch helfen können:

1. es musste lange warten, bis der erste Mensch auf die Lösung stieß, die Schulbuchautoren heute so selbstverständlich präsentieren. Ich weiß nicht, wie diese spezielle Lösung zuerst gefunden wurde; vielleicht ist jemand mit einschlägiger Erfahrung auf das Problem gekommen, vielleicht aus dem Studium von Differentialgleichungen; vielleicht war viel Trial-and-Error im Spiel; vielleicht hatten sie glück.
2. es gibt sehr ähnliche Probleme, bei denen diese Lösungsmethode nicht funktioniert, zumindest nicht ohne Modifikation. Erwägen$f_n=2f_{n-1}-f_{n-2}$. Das Verfahren versagt hier, weil die Säkulargleichung eine Doppelwurzel hat. Ich bin mir sicher, dass Brualdi die für diesen Fall erforderlichen Modifikationen diskutiert, obwohl ich das Buch nicht zur Hand habe, um das zu überprüfen. (Es beinhaltet das Setzen$nq^n$als zweite Lösung.) Der Punkt ist, dass die Vermutung nicht so offensichtlich ist, dass sie einfach funktionieren muss. Es muss nicht haben zu arbeiten, aber es ist ein Versuch wert, und geschieht , erfolgreich zu sein.

Nun zu einigen möglichen Motivationen für eine solche Vermutung.

1. Dies ist eine zweizeitige Wiederholung. Vielleicht sollte man versuchen, einzeitige Wiederholungen zu lösen, bevor man sich damit befasst. Wie wäre es mit $$f_n=3f_{n-1}?$$ Diese Gleichung besagt nur, dass jeder Term $3$ mal so groß wie der vorhergehende Term, so dass einfach eine exponentielle Lösung herausspringt: $f(n)=C\cdot3^n$. Um auf den Fall der zwei Terme zurückzukommen, könnte man sich fragen, was passieren würde, wenn Sie dies noch einmal versuchen würden, aber es ist nicht klar, welche Basis der Exponentialfunktion Sie versuchen sollen, also machen wir dies zu einem Parameter. Nach ein oder zwei Schritten der Algebra erkennen Sie, dass die$n$-Abhängigkeit hebt sich auf, was gut sein muss. Also pflügen wir weiter, um zu sehen, wie weit wir kommen können...
2. Wir haben bereits Differentialgleichungen erwähnt. Wenn du die Differentialgleichung hast$f'(x)=kf(x)$ das kennst du vielleicht $q^x$ löst das, wo $q=e^k$. Sie können die Verallgemeinerung gesehen haben oder nicht: $$a_nf^{(n)}(x)+a_{n-1}f^{(n-1)}(x)+\ldots+a_1f'(x)+a_0f(x)=0$$ kann durch posten gelöst werden $f(x)=Ce^{kx}$ und dann Lösen einer Polynomgleichung, um Werte von zu finden $k$ die Lösungen geben.
3. Wenn der oben erwähnte Trick zur Behandlung des oben erwähnten Doppelwurzelfalls unmotiviert erscheint, können Sie untersuchen, wie das analoge Problem im Fall der Differentialgleichungen gehandhabt wird. Die Fragen rund um die Herrschaft von l'Hôpital sind hier relevant. Der Punkt hier ist, dass die Lösungsmethode mit einer Menge anderer Mathematik verknüpft ist.

Ich denke, indem ich betrachte $f_n=q^n$ wir bekommen $f_n-f_{n-1}-f_{n-2}=0 \Rightarrow q^n-q^{n-1}-q^{n-2}=0 \Rightarrow q^n(q^2-q-1)=0$. Daher können wir durch Lösen der quadratischen Gleichung eine Vorstellung davon bekommen$f_n$.

$\begin{bmatrix} f_n\\ f_{n-1} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\begin{bmatrix} f_{n-1}\\ f_{n-2} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^{n-1}\begin{bmatrix} f_1\\ f_0 \end{bmatrix}$ Dann können Sie die Eigenwerte berechnen.

Einen Beweis dafür findet man hier in meiner Arbeit.
https://www.ssmrmh.ro/2021/04/12/metallic-numbers/
Beachten Sie jedoch, dass wenn

Ich habe diesen Ansatz schon einmal gedacht und komme zu dem Schluss, dass:

Kommen wir zu deiner Frage, sagten wir $f_n=q^n$ weil wir das wissen $f_n$bedeuten, dh eine Zahl darstellt. Darüber hinaus können wir sehen, dass jede Zahl durch Spielen der Begriffe wie$a \times q^n$. Dank dieser Eigenschaft können wir gegebene Gleichungen erfüllen, so dass$f_n=f_{n-1} +f_{n-2} +f_{n-3}$ usw.

Noch klarer, sagen wir das $q=2$ und wir wollen auch etwas rekursion wie $f_n=f_{n-1} +f_{n-2} +f_{n-3}$ , dh, $2^n=2^{n-1} + 2^{n-2} +2^{n-3}$. Wir können es durch eine rationale Zahl erfüllen$a,b,c,d$ so dass $a2^n=b2^{n-1} + c2^{n-2} +d2^{n-3}$. Wir finden diese rationalen Zahlen auch durch Anfangsbedingungen

Wie Sie verstehen, dank Exponentialfunktionen wie such $q^n$ , können wir unsere rekursiven Beziehungsgleichungen erfüllen. Aus diesem Grund wählen wir sie aus, um sie zu verwenden.

HINWEIS = Soweit ich verstanden habe, fragen Sie sich, warum wir uns entschieden haben $f_n=q^n$am Anfang. Tatsächlich kann dies aus der vorstehenden Erläuterung leicht geschlossen werden. Denn das ist offensichtlich$f_n$ ist eine rationale Zahl und wir können sie durch Exponentialwerte angeben wie $57 = 57^1$ oder $1/16 = (1/2)^4$

Der Standardansatz, um mit linearen rekursiven Folgen wie der Fibonacci-Folge zu arbeiten, ist wie folgt: Betrachten wir eine Abbildung $\mathbb{Z}^{+} \mapsto \mathbb{R}$ wo sagst du $R$ ein beliebiger Ring ist, nehmen wir an, dass die der Abbildung entsprechende Folge dargestellt wird als $\{u_j\}_{\ge 1}^{\infty}$,

Angenommen, die rekursive Relation hat die Form $u_{n+k}=\sum_{j=1}^{k}a_{(n+k-j)}\,u_{j}$ ,wo $a_j \in \mathbb{R}$

Dann können wir der Folge ein Polynom zuordnen $p(\xi ) \in \mathbb{R}[\xi]$ die Vertretung haben

Wenn $\{\phi_j:1\le j \le k\}$ ist die Nullmenge von $p(\xi)$ mit $\phi_j$ist verschieden, dann ist der allgemeine Begriff von general $\{u_j\}_{\ge 1}^{\infty}$ hat Form

ANMERKUNG: Für eine weniger strenge Darstellung der Theorie linearer rekursiver Sequenzen schlage ich vor, den klassischen sowjetischen Text REKURSIONSSEQUENZEN von Prof. Aleksei Ivanovich Markushevich . durchzugehen