I have been working on this problem but have had a hard time understanding how to prove it as True, which I believe it is.
[ Summation of k=1 to n of sqrt(2^k) ]= Θ(sqrt(2)^n);
I know you can change sqrt(2^k) to 2^(k/2), and sqrt(2)^n to 2^(n/2) Which, with the summation, becomes
2^(1/2)+2^1+2^(3/2)+2^2+... 2^(n/2) = Θ 2^n/2
So, by definition of Big Θ,
C1 2^(n/2) ≤ x ≤ C2 2^(n/2)
where I'm going to say
x = 2^(1/2)+2^1+2^(3/2)+2^2+... 2^(n/2)
How can I prove this?
Let $a=\sqrt2$ then $a\gt1$ hence $x_n=\sum\limits_{k=1}^na^k$ is such that $$ a^n\leqslant x_n\leqslant a^n\sum_{i=0}^\infty a^{-i}=\frac{a}{a-1}a^n. $$ This shows that $$ x_n=\Theta(a^n). $$