Beweis mit O-Notation (Informatik)

Folgende Aufgabenstellung habe ich:

Sei ${\displaystyle \mathrm{i<mspace\; width="0.12em"></mspace>}\ge 1}$ eine natürliche Zahl. Wir definieren die Funktion ${\displaystyle {\mathrm{f<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}}$ als ${\displaystyle {\mathrm{f<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}\left(\mathrm{n<mspace\; width="0.12em"></mspace>}\right)=\sum _{\mathrm{k<mspace\; width="0.12em"></mspace>}=0}^{\mathrm{n<mspace\; width="0.12em"></mspace>}}{\mathrm{k<mspace\; width="0.12em"></mspace>}}^{\mathrm{i<mspace\; width="0.12em"></mspace>}}}$. Beweisen Sie, dass für jedes ${\displaystyle \mathrm{i<mspace\; width="0.12em"></mspace>}}$ die Funktion ${\displaystyle {\mathrm{f<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}}$ in ${\displaystyle \mathrm{\Theta <mspace\; width="0.12em"></mspace>}\left({\mathrm{n<mspace\; width="0.12em"></mspace>}}^{\mathrm{i<mspace\; width="0.12em"></mspace>}+1}\right)}$ liegt.

Ich habe zuerst nach einer Formel gesucht, um die Summe umzuformen. Dabei ist dann folgendes rausgekommen:

${\displaystyle \frac{1}{\mathrm{i<mspace\; width="0.12em"></mspace>}+1}\sum _{\mathrm{m<mspace\; width="0.12em"></mspace>}=0}^{\mathrm{i<mspace\; width="0.12em"></mspace>}}(\begin{array}{c}\mathrm{i<mspace\; width="0.12em"></mspace>}+1\\ \mathrm{m<mspace\; width="0.12em"></mspace>}\end{array}){(\mathrm{n<mspace\; width="0.12em"></mspace>}+1)}^{\mathrm{i<mspace\; width="0.12em"></mspace>}-\mathrm{m<mspace\; width="0.12em"></mspace>}+1}{\mathrm{B<mspace\; width="0.12em"></mspace>}}_{\mathrm{m<mspace\; width="0.12em"></mspace>}}}$

Leider kann ich damit nichts mehr anfangen. Hoffentlich könnt ihr mir helfen.

Hi, danke für die Tipps.

Herr Hempel hat aber auch ausdrücklich in der Vorlesung gesagt, dass wir uns bei den Aufgaben helfen lassen dürfen... Wo ich mir helfen lass dürfte ja dann mir überlassen sein, denke ich. Ich will ja auch keine vorgefertigte Lösung aufm Silbertablett, sondern eher so den passenden Schubs in die richtige Richtung.