Hallo Eren,
Könnt ihr mir BITTE erklären wie man bei der rekursiven vorgeht
'rekursiv' bedeutet, dass in einer Folge auf Grund der vorhergehenden Zahlen auf das nächste Element geschlossen werden kann. Ein einfaches Beispiel ist die Folge der natürlichen Zahlen: $$1,\, 2,\, 3,\, 4,\, 5, \dots$$Ist irgendeine natürlich Zahl \(d_n\) gegeeben, so kann man daraus direkt auf die nächste schließen$$d_{n+1} = d_n +1$$das ist trivial. Oder die ungeraden Zahlen$$1,\, 3,\, 5,\, 7,\, 9,\, \dots$$Hier addiert man \(2\) und kommt zur nächsten ungeraden Zahl$$u_{n+1} = u_n + 2$$Bei den Quadratzahlen könnte man es genauso machen. Die \(n\)'te Quadratzahl sei \(q_n\); dann ist die nächste:$$q_{n+1} = \left( \sqrt{q_n} + 1\right)^2$$Beispiel: ist \(q_n=289\) so ist die nächste Quadratzahl \(q_{n+1}\)$$q_{n+1} = \left( \sqrt{289} + 1\right)^2 = \left( 17 + 1\right)^2 = 324$$Jetzt ist das aber das mit der Wurzel ein wenig umständlich. Es gibt auch eine andere Möglichkeit. Und zwar kann man die nächste Zahl der Folge auch ohne Wurzel und Quadrat aus seinen beiden Vorgängern \(q_n\) und \(q_{n-1}\) berechnen.
Grundsätzlich solte man sich bei jeder Folge die Differenzen und die Quotienten der Nachbarglieder anschauen. Die Folge der Quadratzahlen ist$$1, \, 4,\, 9,\, 16,\, 25,\, 36,\, \dots$$ und die Folge der Differenzen ist \(4-1=3\), \(9-4=5\) usw.: $$3,\, 5,\, 7,\, 9,\, 11,\, \dots$$und das ist die Folge der ungeraden Zahlen und die unterscheiden sich jeweils um \(2\). D.h. die nächste Quadratzahl \(q_{n+1}\) berechnet sich aus dem Vorgänger \(q_n\) erhöht um die Differenz der beiden Vorgänger \(q_n-q_{n-1}\) plus \(2\), da die nächste Differenz um \(2\) größer sein muss.$$q_{n+1} = q_n + (q_n - q_{n-1}) +2 = 2q_n -q_{n-1} +2$$
Formal käme man da auch mit folgendem Ansatz hin. Man nimmt an, dass $$q_{n+1} = a \cdot q_n + b \cdot q_{n-1} + c$$Aber wie groß sind nun \(a\), \(b\) und \(c\)? Dazu bemühen wir die explizite Darstellung - wir wissen ja dass$$q_n = n^2$$Das setze ich oben in die (Probier)Gleichung ein:$$(n+1)^2 = a \cdot n^2 + b \cdot (n-1)^2 + c$$Die Faktoren \(a\), \(b\) und \(c\) müssen nun so bestimmt werden, dass die Gleichung für jedes(!) \(n\) aufgeht. Dazu multipliziere ich aus und sortiere nach den Potenzen von \(n\)$$\begin{aligned}n^2 + 2n +1 &= an^2 + b(n^2 - 2n + 1) +c \\ n^2 + 2n +1 &= an^2 + bn^2 - 2bn + b +c \\ 0&= n^2 \cdot \underbrace{(a+b-1)}_{=0} + n\cdot \underbrace{(-2b - 2)}_{=0} + \underbrace{(b+c-1)}_{=0}\end{aligned}$$Damit die Gleichung für jedes \(n\) stimmt, müssen die Faktoren vor \(n^2\), \(n\) und \(n^0\) alle identisch 0 sein.
Aus dem mittleren Term \(-2b-2 = 0\) folgt \(b=-1\) und damit ist \(a=2\) und \(c=2\). Also $$q_{n+1} = 2q_n - q_{n-1} + 2$$Probieren wir das mit \(q_{n-1} = 289\) und \(q_n=324\) dann kommt raus:$$q_{n+1} = 2 \cdot 324 - 289 + 2 = 361 = 19^2$$Gruß Werner
