> [!NOTE] Lemma > Let $a>0.$ Define $f: \mathbb{N}^{+}\to \mathbb{R}$ by $\sum_{i=1}^{n} a^{i}i.$If $a>1,$ then $f(n)$ is [[Big Theta Relation on Real Sequence|big theta]] of $a^{n} n$, i.e $f(n)=\Theta(a^{n}n).$ > If $a=1,$ then $f(n)=\Theta(a^{n}n).$ > If $0<a<1,$ then $f(n)=\Theta(1).$ **Proof**: Let $a>1.$ We have $f(n)\leq n \sum a^{i} \leq n a^{n+1} =a \cdot(na^{n}).$ Thus $f(n)=O(na^{n}).$ On the other hand, $f(n)\geq a^{n}\cdot n$ so $f(n)=\Omega(n \cdot a^{n})$ thus $f(n)=\Theta(na^{n}).$