So I am working on my assignment and have gotten stuck. For previous questions I was able to use Master Theorem to get $\Theta$, but can't use the theorem for this question..
I know to get $\Theta$ I need to prove $O$ and $\Omega$, but I am not sure how to approach it. By this I mean I have solved the recurrence and gotten an $O$, what needs to be done differently to get $\Omega$?
Maybe I'll try and explain with an example. Say we have the recurrence: $T(n) = T(n-1) + 1$. I would approach this question by expanding: $$ \begin{align*} T(n) &= T(n-1) + 1 \\ &= (T(n-2) + 1) + 1 \\ &= (T(n-3) + 1) + 2 \\ &\ldots \end{align*} $$ which implies $O(n)$.
How would I go about the above differently to get Θ?
Your example is a very bad one, since your expansion actually shows that $T(n) = n + T(0) = \Theta(n)$. In general, if you use $\leq$ in your expansion then you only get an $O(\cdot)$ bound, while if you use $\geq$ in your expansion then you only get an $\Omega(\cdot)$ bound. If you get a formula for $T(n)$ then it is usually easy to obtain $\Theta(\cdot)$ asymptotics.
Perhaps it's best if you tell us the actual example that's stumping you, what you tried, and where you got stuck.