Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = (\log_2{10})^{(n-3)}$.
I'm not quite sure how to proceed. I was having problems with another problem trying to figure out what it means to raise a logarithm to an exponent. For example, in another problem, I was trying to show that $(n * \log_2{(n+1)})^2 \le C * n^2$, but I got stuck at $n^2 * (\log_2{(n+1)})^2$.
Take $a=\log_2 10$. Then $s(n)=\frac{a^n}{(\log_2 10)^3}$; can you conclude from there using the definition of $\Theta(\cdot)$?
Incidentally, regarding your second (embedded) question: you will not be able to find any constant $C$ such that $(n\log_2(n+1))^2 \leq Cn^2$. Indeed, $\frac{(n\log_2(n+1))^2}{n^2} = (\log_2(n+1))^2 \xrightarrow[n\to\infty]{} \infty$.