How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction? This is recurrence $T(n)$ 
$ T(n) =
\begin{cases}
c,  & \text{if $n$ is 1} \\
2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1}
\end{cases}$
This is my attempt to show that $T(n) \in \Omega(n^{0.5})$ with proof by induction
Statement: The recurrence $T(n) \ge bn^{1/2}$ for all $n \gt n_0$
      Base case($n=1$) : $T(1) = c$
      Base case true as long as $c \ge $ b
Inductive hypothesis: Assume that $T(k) \ge bk^{0.5}$ for all $k\lt n$
Inductive step ($n\gt1$)
$T(n)=2T(\lfloor(n/4)\rfloor) + 16$
$2T(\lfloor(n/4)\rfloor) + 16\ge 2b(\lfloor(n/4)\rfloor)^{0.5} + 16$         By Inductive hypothesis 
$2b(\lfloor(n/4)\rfloor)^{0.5} + 16 \ge 2b(n/16)^{0.5} + 16$ 
$2b(n/16)^{0.5} + 16 = \frac{b\sqrt{n}}{2} + 16$

Now to complete the proof by induction, I have to show that $\frac{b\sqrt{n}}{2} + 16 \ge b\sqrt{n}$ 
Solving for b, I got $b\le\frac{32}{\sqrt{n}}$. 
My issue here is that I can't find an appropriate $b$ to use to meet the definition of $\Omega(n^{0.5})$ based off the inductive step because in the inductive step, $b$ is in terms of a variable $n$. Does anyone know of a way I can choose $b$ so that it is a constant, like $c$ to meet the definition?
 A: Direct Proof (my preferred way)  The way I think about it is as a tree--it is a direct approach.  It's hard to draw here, but I'll make my best effort: At the top of the tree, we have $n$ elements, which I'll just denote by $T_{n}$.  When we apply the recursion, we get 2 children each with $T_{n/4}$ operations to perform (because of the coefficient in front of the $T_{n/4}$) and an additional 16 operations.
$$\begin{array}{cccccc} & T_{n} & & & & \\
                     T_{n/4} & & T_{n/4} & & +16
\end{array}$$
On the next level down, each $T_{n/4}$ becomes two copies of $T_{n/16}$ and we get two additional $+16$ terms (one from each branch).  It looks like:
$$\begin{array}{ccccccc} & & T_{n} & & & & \\
                     & T_{n/4} & & T_{n/4} & & +16 \\
                     T_{n/16} & T_{n/16} &  & T_{n/16} & T_{n/16} & +2(16)
\end{array}$$
Now, we imagine this being carried out until we get down to $T_{1}$.  It takes $\log_{4}(n)$ iterations to get there.  Once we do, we can count the number of leaves (at that lowest level) and sum up all the $+16$'s on the previous levels that we used to get down.  The final operation count looks something like:
$$2^{\log_{4}(n)}T_{1} + 16(1+2+4+8+16+...+2^{\log_{4}(n)})$$
Note that $2^{\log_{4}(n)}=n^{\log_{4}(2)}=n^{1/2}$ and $1+2+4+...+2^{\log_{4}(n)}=2\cdot 2^{\log_{4}(n)}-1=2n^{1/2}-1$.
Putting this all together we have that $T_{n}\approx T_{1}n^{.5}+32n^{.5}-1=\Omega(n^{.5})$.
Inductive Proof (not my preferred way)
Try using a modified induction hypothesis (sometimes helps).
Inductive hypothesis: $T(k)\geq bk^{.5} + c$ for some constant $c$ for all $k<n$.  We'll solve for $c$ and $b$ later.
Then 
\begin{align*}
T(n) &= 2T(n/4)+16 \\
     &\geq 2(b(n/4)^{.5}+c)+16 \\
     &= bn^{.5}+2c+16 \\
     &= bn^{.5}+c &\star
\end{align*}
$\star$ Provided that $2c+16=c$, i.e. if $c=-16$.
The moral is that if you make the inductive hypothesis $T(k)\geq bk^{.5}-16$ then you can choose $b$ to be any positive constant you like... as long as it satisfies your base case(s).  The strategy works because if $c$ is a constant and $T(n)=\Omega(n^{.5}\pm c)$ then $T(n)=\Omega(n^{.5})$
