Das hätte auch gut als Zusatzaufgabe auf einem meiner Übungsblätter in den ersten zwei Semestern im Mathestudium stehen können. Eine Lösung, die für mathematische Laien oder Zehntklässler verständlich ist, die vermutlich Logarithmen, Summen- und Produktzeichen und vollständige Induktion nicht kennen, habe ich leider nicht gefunden. Ich bin gespannt, wie die Musterlösung das macht.
---Herangehensweise---
Hier habe ich auch erstmal den Computer bemüht, um einschätzen zu können, wie schnell diese Folge wächst. Dafür habe ich die ersten 10 Millionen Folgenglieder berechnet und in einem halb und einem beidseitig logarithmischen Plot dargestellt. Polynomielles Wachstum würde im beidseitig logarithmischen Plot eine Gerade sein, exponentielles Wachstum im halb logarithmischen. Die eigentliche Kurve wuchs dann im loglog-Plot schneller als eine Gerade, aber im semilog-Plot deutlich langsamer, es handelt sich also (wie mein Bauchgefühl vorher schon sagte) um subexponentielles Wachstum, also schneller als polynomiell, langsamer als exponentiell. Ich habe dann versucht, den Loglog-Plot mit einer quadratischen Funktion anzunähern, und festgestellt, dass das sehr gut funktioniert. Wenn log(f(exp(x)) in etwa ax^2+bx+c ist, dann bedeutet das, f(x) ist etwa exp(a log(x)^2 + b log(x) + c). Mit den Parametern des Fits habe ich dann eine ganz gute Näherung gefunden, diese bei 2025^5 ausgewertet und kam auf ein Ergebnis, das klar im Bereich der Antwortmöglichkeit 5 liegt.
Das ist aber natürlich kein Beweis, die Abschätzung könnte ja auch bei größeren n völlig daneben liegen. Also habe ich mir, nachdem ich 5 angekreuzt hatte, den Hinweis mit den Zweierpotenzen angeschaut. Genauer gesagt habe ich mir erst einmal die ersten Werte für a_(2^n) angeschaut und wie diese wachsen. Ich wusste ja schon, dass f(2^n) in etwa exp(a n^2) sein wird für irgendein a, also wird der Quotient f(2^(n+1))/f(2^n) immer noch exponentiell wachsen, der Quotient aus zwei aufeinanderfolgenden Quotienten a_(2^(n+2))a_(2^n)/(a_(2^(n+1)))^2 sollte allerdings in etwa konstant sein, und tatsächlich schien dieser Wert sich langsam von unten an 2 anzunähern. Wenn a_(2^(n+1))/a_(2^n)) in jedem Schritt um etwa k wächst, hätte man a_(2^0) = a0, a_(2^1) = k a0, a_(2^2) = k * k^2 * a0, a_(2^n) = k^(n(n+1)/2) * a0, dies würde einem Wert von a = log2(k)/2 in a_n ~= 2^(a log2(n)^2 + b log2(n) + c) entsprechen. Da der reale Wert irgendwo über sqrt(2) anfängt und sich von unten an 2 annähert, erschienen mir log2(sqrt(2))/2 =1/4 und log2(2)/2 = 1/2 hier als sinnvolle Ansätze für eine untere und obere Schranke. Das Ergebnis meines Fits war übrigens etwa f(n) = 2^(0.45*log2(n)^2 - 0.73*log2(n) + 8.14), also sollten 1/4 und 1/2 als Schranken funktionieren, wobei letzteres eine engere Schranke sein sollte.
Immer noch kein Beweis. Dass Zweierpotenzen für die Rekursionsformel hilfreich sein könnten, liegt aber nahe, denn a_(2^n) = a_(2^n-1) + 2 a_(2^(n-1)). Will ich hier eine geschlossene Form bekommen, die nur Zweierpotenzen enthält, muss ich aber noch a_(2^n-1) loswerden, dies ist a_(2^n-2) + 2 a_(2^(n-1)). Das hat mich auf die Idee gebracht, die Rekursionsformel so oft anzuwenden, dass der erste Summand bei a_(2^(n-1)) ankommt.
---Eigentliche Lösung ab hier---
Wiederholtes Anwenden der Rekursionsformel liefert:
a_(2^n) = a_(2^n-1) + 2*a_(2^(n-1))
= a_(2^n-2) + 2*a_(2^(n-1)) + 2*a_(2^(n-1))
= a_(2^n-3) + 2*a_(2^(n-1)-1) + 4*a_(2^(n-1))
= a_(2^n-4) + 4*(a_(2^(n-1)-1) + a_(2^(n-1)))
= ...
= a_(2^(n-1)+2) + 4*(a_(2^(n-2)+2) + ... + a_(2^(n-1)))
= a_(2^(n-1)+1) + 2*a_(2^(n-2)+1) + 4*(a_(2^(n-2)+2) + ... + a_(2^(n-1)))
= a_(2^(n-1)) + 4*(a_(2^(n-2)+1) + ... + a_(2^(n-1)))
Man kann dies nun nach oben und unten abschätzen, indem man alle Terme in der Summe (2^(n-2)+1 bis 2^(n-1) sind 2^(n-1)-2^(n-2)=2^(n-2) Zahlen) durch jeweils den höchsten oder den niedrigsten Summanden ersetzt (bzw nach unten den nächstkleineren, um weiterhin nur Zweierpotenzen zu haben.)
Nach oben: a_(2^n) <= a_(2^(n-1)) + 4*2^(n-2)*a_(2^(n-1)) = a_(2^(n-1)) * (1 + 2^n)
Nach unten: a_(2^n) > a_(2^(n-1)) + 4*2^(n-2)*a_(2^(n-2)) = a_(2^(n-1)) + 2^n * a_(2^(n-2))
Für die obere Schranke habe ich dann auch eine simple geschlossene Form gefunden:
Aus wiederholtem Anwenden von a^(2^n) <= a_(2^(n-1)) * (1 + 2^n) <= a_(2^(n-1)) * 2^(n+1)
folgt a^(2^n) <= a_(2^(n-1)) * 2^(n+1) <= a_(2^(n-2)) * 2^n * 2^(n+1) <= ... <= a_(2^0) * (2^2 * ... * 2^(n+1)) = 2^((n+2)(n+1)/2 - 1) = 2^((n^2+3n)/2)
Damit habe ich auch wie oben gewünscht ein Polynom mit n^2/2 im Exponenten.
Für die untere Schranke habe ich per vollständiger Induktion gezeigt, dass a_(2^n) >= 2^((n^2+2n)/4) für alle n. (Wieso ich etwas mit n^2/4 im Exponenten haben wollte, habe ich oben erklärt, und den Term 2n/4 musste ich hinzufügen, damit der Induktionsschritt funktioniert.)
Sei dies gültig für a_(2^(n-2)) und a_(2^(n-1)). Dann:
a_(2^n) > a_(2^(n-1)) + 2^n*a_(2^(n-2))
>= 2^(((n-1)^2+2(n-1))/4) + 2^n * 2^(((n-2)^2+2(n-2))/4)
= 2^((n^2-1)/4) + 2^((n^2+2n)/4)
> 2^((n^2+2n)/4)
Als Induktionsstart ist a(2^0) = 1 = 2^((0^2+2*0)/4) und a(2^1) = 3 > 2^(3/4) = 2^((1^2+2*1)/4).
Damit weiß ich für beliebige n:
2^((n^2+2n)/4) < a_(2^n) < 2^((n^2+3n)/2)
log2(2025^5) = 5 log2(2025) ist etwa 54.9, also
2^((54^2+2*54)/4) < a_(2^54) < a_(2025^5) < a_(2^55) < 2^((55^2+3*55)/2)
log2(a_(2025^5)) ist also zwischen (54^2+2*54)/4 = 756 und (55^2+3*55)/2 = 1595
log2(10^202.5) = 202.5*log2(10) ist etwa 672, log2(2.025^2025) = 2025*log2(2.025) > 2025
Also folgt 10^202.5 < a_(2025^5) < 2.025^2025.
Mein Fit von oben liefert übrigens in etwa 2^1328 für a_(2025^5). Ich bin gespannt, ob die Musterlösung einen genauereren Wert hat.
---Herangehensweise---
Hier habe ich auch erstmal den Computer bemüht, um einschätzen zu können, wie schnell diese Folge wächst. Dafür habe ich die ersten 10 Millionen Folgenglieder berechnet und in einem halb und einem beidseitig logarithmischen Plot dargestellt. Polynomielles Wachstum würde im beidseitig logarithmischen Plot eine Gerade sein, exponentielles Wachstum im halb logarithmischen. Die eigentliche Kurve wuchs dann im loglog-Plot schneller als eine Gerade, aber im semilog-Plot deutlich langsamer, es handelt sich also (wie mein Bauchgefühl vorher schon sagte) um subexponentielles Wachstum, also schneller als polynomiell, langsamer als exponentiell. Ich habe dann versucht, den Loglog-Plot mit einer quadratischen Funktion anzunähern, und festgestellt, dass das sehr gut funktioniert. Wenn log(f(exp(x)) in etwa ax^2+bx+c ist, dann bedeutet das, f(x) ist etwa exp(a log(x)^2 + b log(x) + c). Mit den Parametern des Fits habe ich dann eine ganz gute Näherung gefunden, diese bei 2025^5 ausgewertet und kam auf ein Ergebnis, das klar im Bereich der Antwortmöglichkeit 5 liegt.
Das ist aber natürlich kein Beweis, die Abschätzung könnte ja auch bei größeren n völlig daneben liegen. Also habe ich mir, nachdem ich 5 angekreuzt hatte, den Hinweis mit den Zweierpotenzen angeschaut. Genauer gesagt habe ich mir erst einmal die ersten Werte für a_(2^n) angeschaut und wie diese wachsen. Ich wusste ja schon, dass f(2^n) in etwa exp(a n^2) sein wird für irgendein a, also wird der Quotient f(2^(n+1))/f(2^n) immer noch exponentiell wachsen, der Quotient aus zwei aufeinanderfolgenden Quotienten a_(2^(n+2))a_(2^n)/(a_(2^(n+1)))^2 sollte allerdings in etwa konstant sein, und tatsächlich schien dieser Wert sich langsam von unten an 2 anzunähern. Wenn a_(2^(n+1))/a_(2^n)) in jedem Schritt um etwa k wächst, hätte man a_(2^0) = a0, a_(2^1) = k a0, a_(2^2) = k * k^2 * a0, a_(2^n) = k^(n(n+1)/2) * a0, dies würde einem Wert von a = log2(k)/2 in a_n ~= 2^(a log2(n)^2 + b log2(n) + c) entsprechen. Da der reale Wert irgendwo über sqrt(2) anfängt und sich von unten an 2 annähert, erschienen mir log2(sqrt(2))/2 =1/4 und log2(2)/2 = 1/2 hier als sinnvolle Ansätze für eine untere und obere Schranke. Das Ergebnis meines Fits war übrigens etwa f(n) = 2^(0.45*log2(n)^2 - 0.73*log2(n) + 8.14), also sollten 1/4 und 1/2 als Schranken funktionieren, wobei letzteres eine engere Schranke sein sollte.
Immer noch kein Beweis. Dass Zweierpotenzen für die Rekursionsformel hilfreich sein könnten, liegt aber nahe, denn a_(2^n) = a_(2^n-1) + 2 a_(2^(n-1)). Will ich hier eine geschlossene Form bekommen, die nur Zweierpotenzen enthält, muss ich aber noch a_(2^n-1) loswerden, dies ist a_(2^n-2) + 2 a_(2^(n-1)). Das hat mich auf die Idee gebracht, die Rekursionsformel so oft anzuwenden, dass der erste Summand bei a_(2^(n-1)) ankommt.
---Eigentliche Lösung ab hier---
Wiederholtes Anwenden der Rekursionsformel liefert:
a_(2^n) = a_(2^n-1) + 2*a_(2^(n-1))
= a_(2^n-2) + 2*a_(2^(n-1)) + 2*a_(2^(n-1))
= a_(2^n-3) + 2*a_(2^(n-1)-1) + 4*a_(2^(n-1))
= a_(2^n-4) + 4*(a_(2^(n-1)-1) + a_(2^(n-1)))
= ...
= a_(2^(n-1)+2) + 4*(a_(2^(n-2)+2) + ... + a_(2^(n-1)))
= a_(2^(n-1)+1) + 2*a_(2^(n-2)+1) + 4*(a_(2^(n-2)+2) + ... + a_(2^(n-1)))
= a_(2^(n-1)) + 4*(a_(2^(n-2)+1) + ... + a_(2^(n-1)))
Man kann dies nun nach oben und unten abschätzen, indem man alle Terme in der Summe (2^(n-2)+1 bis 2^(n-1) sind 2^(n-1)-2^(n-2)=2^(n-2) Zahlen) durch jeweils den höchsten oder den niedrigsten Summanden ersetzt (bzw nach unten den nächstkleineren, um weiterhin nur Zweierpotenzen zu haben.)
Nach oben: a_(2^n) <= a_(2^(n-1)) + 4*2^(n-2)*a_(2^(n-1)) = a_(2^(n-1)) * (1 + 2^n)
Nach unten: a_(2^n) > a_(2^(n-1)) + 4*2^(n-2)*a_(2^(n-2)) = a_(2^(n-1)) + 2^n * a_(2^(n-2))
Für die obere Schranke habe ich dann auch eine simple geschlossene Form gefunden:
Aus wiederholtem Anwenden von a^(2^n) <= a_(2^(n-1)) * (1 + 2^n) <= a_(2^(n-1)) * 2^(n+1)
folgt a^(2^n) <= a_(2^(n-1)) * 2^(n+1) <= a_(2^(n-2)) * 2^n * 2^(n+1) <= ... <= a_(2^0) * (2^2 * ... * 2^(n+1)) = 2^((n+2)(n+1)/2 - 1) = 2^((n^2+3n)/2)
Damit habe ich auch wie oben gewünscht ein Polynom mit n^2/2 im Exponenten.
Für die untere Schranke habe ich per vollständiger Induktion gezeigt, dass a_(2^n) >= 2^((n^2+2n)/4) für alle n. (Wieso ich etwas mit n^2/4 im Exponenten haben wollte, habe ich oben erklärt, und den Term 2n/4 musste ich hinzufügen, damit der Induktionsschritt funktioniert.)
Sei dies gültig für a_(2^(n-2)) und a_(2^(n-1)). Dann:
a_(2^n) > a_(2^(n-1)) + 2^n*a_(2^(n-2))
>= 2^(((n-1)^2+2(n-1))/4) + 2^n * 2^(((n-2)^2+2(n-2))/4)
= 2^((n^2-1)/4) + 2^((n^2+2n)/4)
> 2^((n^2+2n)/4)
Als Induktionsstart ist a(2^0) = 1 = 2^((0^2+2*0)/4) und a(2^1) = 3 > 2^(3/4) = 2^((1^2+2*1)/4).
Damit weiß ich für beliebige n:
2^((n^2+2n)/4) < a_(2^n) < 2^((n^2+3n)/2)
log2(2025^5) = 5 log2(2025) ist etwa 54.9, also
2^((54^2+2*54)/4) < a_(2^54) < a_(2025^5) < a_(2^55) < 2^((55^2+3*55)/2)
log2(a_(2025^5)) ist also zwischen (54^2+2*54)/4 = 756 und (55^2+3*55)/2 = 1595
log2(10^202.5) = 202.5*log2(10) ist etwa 672, log2(2.025^2025) = 2025*log2(2.025) > 2025
Also folgt 10^202.5 < a_(2025^5) < 2.025^2025.
Mein Fit von oben liefert übrigens in etwa 2^1328 für a_(2025^5). Ich bin gespannt, ob die Musterlösung einen genauereren Wert hat.