In CLRS, it works through an example going through a recurrence relation proof using the substitution method.We have the recurrence $$T(n) = 2T(\lfloor n/2 \rfloor) + n \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \   (4.19)$$It claims:We guess that our solution is $T(n) = O(n \lg(n)).$We assume that $T(m) \leq cm\lg(m)$ for all $m < n$ (in particular, for $m = \lfloor(n/2) \rfloor$, and need to show that $T(m) \implies T(n).$I'm fine with this; this seems like a standard case of strong induction, but what I don't understand is the explanation of the base case (which we also need to prove):Could someone explain this paragraph to me?More specifically:What are boundary conditions?How do we know the base case? We're only given $T(n)$ recursively; there's no initial case when $n$ is, for example, $1$. How, then, do we know that $T(1) = 1$?I don't understand what the paragraph is getting at.  How do we determine the base case in the general case?Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof; that is, they assume the inductive hypothesis, and prove that (for all $m<n$), $T(m) \leq \text{something} \implies T(n) \leq \text{something}$, but they leave it at that, as though that were sufficient for the proof.In fact, these proofs don't even explicitly state the inductive hypothesis. For example, in the case of (4.19), they would write something like:$$ \begin{align} T(n)  \leq c\lfloor( n/2) \rfloor \lg(\lfloor n/2\rfloor) \end{align} \\  \leq \ ... \\ \leq cn\lg(n) \ .$$Is this acceptable, or would that constitute a sloppy proof?
What exactly is going on in a proof by induction of a recurrence relation?
proof techniques;recurrence relation
What are boundary conditions?The boundary condition here refers to the base case(s) of the induction. This makes more sense in an intuitive manner if we consider, for instance, a 2D case: Suppose $T(m,n)$ is the running time of an algorithm where the input parameters are $m$ & $n$ are non-negative integers. Now, assume we have a recurrence relation of the form, say, $T(m,n) = T(m-1,n)+T(m,n-1)$ Arguably, the boundary condition that needs to be supplied for an inductive proof of $T(m,n)$ would be $T(m,0)\ \forall\ m \geq 0 $ & $T(0,n)\ \forall\ n \geq 0$. Thus, the set of $ (m,0),\ m \geq 0$ along with $ (0,n),\ m \geq 0$ can be thought of as a boundary(identifiable with the first quadrant axes). Thus, coming back to the question at hand, the boundary conditions are nothing but the specification of the values of the recurrence at the edge of its applicable domain. This in 1D turns out to be point(s) at the end of the interval.How do we know the base case? We're only given T(n) recursively; there's no initial case when n is, for example, 1. How, then, do we know that T(1)=1?When setting up a recurrence relation, it is always a good practice to specify the domain of applicability of the relation. This as we just saw above can help identify the boundary of validity of the relation. Now, the next step of how we come to know the exact values taken by the function at the  boundary is often a problem of understanding the algorithm for which we have setup the recurrence relation for. In this particular case of $T(1) = 1$, we obtain $T(1)$ by manually computing(using the algorithm) the (worst-case)time it will take to work on an input of size 1.How do we determine the base case in the general case?This is where the understanding of the algorithm(and its correctness) becomes crucial. Knowing the boundary of domain of the recurrence relation and the approximations we want to use to bound the range of the recurrence on a given size of input determines the cases for which we will need to supply the starting terms of the recurrence relation. For instance, even though the natural boundary point for the example in your question is the input of size 1, due to the approximation being used namely $cnlg(n)$, we need to perturb the boundary in order to get a new domain such that the approximation will work on all possible inputs for the new domain of the recurrence. This is why the input $1$ is discarded and the boundary(in 1D it usually a single point if the interval is finite in a direction) and a new boundary point, $n_0 = 2$ is chosen.Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof;...In fact, these proofs don't even explicitly state the inductive hypothesis...Is this acceptable or sloppy proof?You are correct in stating that a base case as well as explicit verification using the inductive hypothesis is needed for the proof of induction to be complete and valid. However, in most treatments of this nature, when the base case/inductive hypothesis is not explicitly invoked, it is usually a passive call to action on the reader that they have been supplied with enough information to figure that out for themselves.