Denksportaufgabe < Wettbewerbe < Schule < Mathe < Vorhilfe
|
Hallo Zusammen,
Diese Aufgabe entstammte einigen Fragen hier im Forum zu Summenformeln für Terme wie [m]\textstyle\sum_{i = 1}^n i[/m]. Ich denke, es wäre eine interessante Aufgabe:
Sei [mm] $\IQ_0 [/mm] := [mm] \IQ \cup \left\{ 0 \right\}$. [/mm] Zeige (oder widerlege):
[m]\forall z \in \mathbb{N}_0\;\exists a_i \in \IQ_0 :\sum_{k = 0}^n {k^z} = \sum_{i = 0}^{z + 1} {a_i n^i}[/m]
Sollte die Aussage gelten, so gib bitte auch eine Berechnungsvorschrift/Formel oder einen Algorithmus (nicht umgangssprachlich formuliert) zur Berechnung der [mm] $a_i$ [/mm] an.
Hier sind einige Artikel, wo ich das Obige schon verwendet habe.
Viel Spaß bei der Aufgabe
wünscht euch:
Karl
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:57 Mi 08.06.2005 | | Autor: | DaMenge |
Hallo Karl,
leider bin ich seit heut morgen um 4uhr wach, deshalb weiß ich nicht, ob folgende Überlegungen überhaupt ansatzweise richtig sind:
also deine rechte Seite sieht für mich aus wie eine Zahlendarstellung zur Basis n , das heißt, man kann sogar noch für alle i fordern, dass : [mm] $a_i [/mm] < n$
zur Existenz muss man sich nur überlegen, wie groß die höchste Zahl ist, die man rechts darstellen kann und das selbe auch links machen.
(Man sollte feststellen, dass links eine kleinere Zahl rauskommen muss, die dann in der Basis n eindeutig darstellbar ist.)
Sollte das bis hierhin nicht totaler Müll sein, muss man sich also noch einen Algo überlegen - aber ich behaupte mal, dass der greedy-mäßig zu finden ist, also - nimm die zahl N, die links rauskommt und schau ob das höchste [mm] n^i [/mm] darin ist (und auch wie oft - dies ist dann das höchste [mm] a_i [/mm] ), dann betrachte den Rest, den man noch hat und fahre mit kleinerem i so fort.
aber wie gesagt: ich bin langsam echt zu müde..
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:09 Fr 10.06.2005 | | Autor: | moudi |
Hallo Karl
In Wirklichkeit ist die Sache gar nicht so schwierig, und die Theorie dazu wohlbekannt.
Sei $p(x)$ ein Polynom vom Grad k, dann ist die Summenformel
[mm] $\sum_{i=1}^n [/mm] p(i)$ ein Polynom vom Grad $k+1$ in der Variablen $n$. Das ganze läuft unter dem Titel arithmetische Reihen höherer Ordnung. Wie du in einem Beitrag geschrieben hast, kann man die Koeffizienten des Polynoms der Summenformel durch ein geeignetes Gleichungssystem erhalten.
Es gibt aber noch eine andere Möglichkeit, die ich an einem Beispiel erläutern will.
Ich nehme das Polynom [mm] $p(x)=x^3-5x^2+2x+3$
[/mm]
Dann beginne ich mit der Folge p(1), p(2), p(3), p(4), p(5), ...
Darunte schreibe ich dann die Folge der Differenzen =
1. Differenzenfolge, dann darunter die Folge der Differenzen der
1. Differenzenfolge = 2. Differenzenfolge, etc.
Beginnt man mit einem Polynom vom Grad k, dann ist die k-te Differenzenfolge konstant.
[mm]\begin{array}{cccccccccccc}
\mathbf{3}& & 1 & & -5 & & -9 & & -5 & & 13 & \dots \\
& \mathbf{-2} & & -6 & & -4 & & 4 & & 18 & &\dots \\
&& \mathbf{-4} & & 2 & & 8 & & 14 & & \dots & \\
&&& \mathbf{6} & & 6 & & 6 & & \dots \\
\end{array}[/mm]
Jetzt sind die ersten Zahlen jeder Folge (fett) wichtig. Mit ihnen bildet man von oben beginnen folgendes Polynom:
[mm] $\mathbf{3}{n\choose 1}\mathbf{-2}{n\choose 2}\mathbf{-4}{n\choose 3}+ \mathbf{6}{n\choose 4}$
[/mm]
wobei [mm] ${n\choose k}=\frac{n(n-1)\dots(n-k+1)}{k!}$, [/mm] also in meinem Beispiel
[mm] $\mathbf{3}n\mathbf{-2}\frac{n(n-1)}{2}\mathbf{-4}\frac{n(n-1)(n-2)}{6}+ \mathbf{6}\frac{n(n-1)(n-2)(n-3)}{24}=\frac14 n^4-\frac{13}6 n^3-\frac{15}4n^2+\frac{7}6n$
[/mm]
Es gilt daher: [mm] $\sum_{i=1}^n i^3-5i^2+2i+3=\frac14 n^4-\frac{13}6 n^3-\frac{15}4n^2+\frac{7}6n$
[/mm]
mfG Moudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:24 Sa 11.06.2005 | | Autor: | Karl_Pech |
Hallo moudi,
Ich habe mir überlegt ein Gleichungssystem aufzustellen. Wir gehen zunächst vom rechten Term aus:
[m]f\left( n \right): = \sum\limits_{i = 0}^{z + 1} {a_i n^i } = a_{z + 1} n^{z + 1} + a_z n^z + \cdots + a_0[/m]
Jetzt interpolieren wir, wobei wir dann insgesamt [mm] $z+2\!$ [/mm] Werte einsetzen müssen, um unser Gleichungssystem aufzubauen:
[m]\begin{gathered}
f\left( 0 \right) = 0 \Rightarrow a_0 = 0 \hfill \\
f\left( 1 \right) = 1 \hfill \\
\vdots \hfill \\
f\left( {z + 1} \right) = \sum\limits_{k = 0}^{z + 1} {k^z } \hfill \\
\end{gathered}[/m]
Jetzt haben wir alle Werte und schreiben uns das System mal hin (Wegen [mm] $a_0 [/mm] = 0$ müssen wir uns jetzt aber nur noch [mm] $z+1\!$ [/mm] Werte aufschreiben):
[m]\pmat{
1 & 1 & \cdots & 1 &\vline & 1 \\
\vdots & {} & {} & {} &\vline & \vdots \\
{\left( {z + 1} \right)^{z + 1} } & {\left( {z + 1} \right)^z } & \cdots & {z + 1} &\vline & {\sum\limits_{k = 0}^{z + 1} {k^z } } \\
} \in \mathbb{Q}^{z + 1 \times z + 1}[/m]
Ab diesem Punkt wußte ich nicht weiter. Ich habe damals gedacht, daß man das Ganze mit den Determinanten lösen könnte. (Die erste Zeile des Systems sieht dafür sehr einladend aus, weil man nach ihr gut entwickeln kann.) Wie man so etwas formal aufschreibt, ist mir jedoch nicht bekannt. Hat man erstmal die Determinante, kann man nacheinander Die Ergebnisspalte in dieses System einsetzen, dann jeweils die neue Determinante bestimmen und durch den Kehrwert der Ersten teilen. So ungefähr müßte es jedenfalls auch für diesen allgemeinen Fall funktionieren. 
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:55 Sa 11.06.2005 | | Autor: | moudi |
Hallo Karl
Mathematisch gesehen musst du nur noch das Gleichungssystem lösen. Und dafür gibt es ja Lösungsalgorithmen.
Vielleicht noch etwas zur Koeffizientenmatrix des Systems: Es handelt sich um eine sogenannte Vandermondsche Matrix, und die Determinante ist dann eine Vandermondsche Determinante (wer hät's gedacht ).
Eine Vandermondsche Matrix der Dimension k sieht so (oder transponiert) aus:
[mm]\pmat{ x_1^0 & x_1^1 & x_1^2 & \dots & x_1^{k-1} \\
x_2^0 & x_2^1 & x_2^2 & \dots & x_2^{k-1} \\
x_3^0 & x_3^1 & x_3^2 & \dots & x_3^{k-1}\\
\vdots & \vdots & \vdots & \dots & \vdots \\
x_k^0 & x_k^1 & x_k^2 & \dots & x_k^{k-1}\\
}[/mm]
Die Determinante ist dann [mm] $\prod_{\{(i,j)\,|\,1\leq i
mfG Moudi
|
|
|
|
