Prove by induction: For $T(1)=1$, $T(n)=T(⌊\frac{n}{2}⌋)+T(⌈\frac{n}{2}⌉)+1=O(n)$ I only saw one problem involving induction so I am not sure what to do here. Here is what I tried and where I got stuck:
For $n=1$, $T(1)=1\leq 1*1$, so we are covered.
The hypothesis would be that for all $k<n$, $T(k)=O(k)$. From here I believe that we could say that for all $n$ larger than some $n_0$:
$T(⌊\frac{n}{2}⌋)\leq c*⌊\frac{n}{2}⌋$ and $T(⌈\frac{n}{2}⌉)\leq c*⌈\frac{n}{2}⌉$
I believe that I am supposed to choose the same $c$ for both of them, but not completely sure.
Now this is where I get stuck:
$T(n)=T(⌊\frac{n}{2}⌋)+T(⌈\frac{n}{2}⌉)+1\leq c*⌊\frac{n}{2}⌋+c*⌈\frac{n}{2}⌉+1=c*n+1$
When I was taught this method it was stressed that it is important to prove the case for $T(n)$ for the same $c$ from the hypothesis however it does not seem possible to me here.
How can I proceed? 
 A: Sometimes it's helpful to determine an appropriate value for $c$ to use. You're given that $T(1) = 1$ and
$$T(n) = T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + T\left(\left\lceil\frac{n}{2}\right\rceil\right) + 1 \tag{1}\label{eq1A}$$
Trying the next few values, you get
$$T(2) = T(1) + T(1) + 1 = 1 + 1 + 1 = 3 \tag{2}\label{eq2A}$$
$$T(3) = T(1) + T(2) + 1 = 1 + 3 + 1 = 5 \tag{3}\label{eq3A}$$
$$T(4) = T(2) + T(2) + 1 = 3 + 3 + 1 = 7 \tag{4}\label{eq4A}$$
$$T(5) = T(2) + T(3) + 1 = 3 + 5 + 1 = 9 \tag{5}\label{eq5A}$$
As you can see, you get $T(n) = 2n - 1$, which you can prove fairly easily by induction. However, to instead directly prove that $T(n) = O(n)$ by induction, you can use $c = 2$ and prove $T(n) \lt cn = 2n$ (although the technical definition is for $\le$, you can use just $\lt$ as that's more strict and, thus, included in $\le$). The base case is true, i.e., $T(1) = 1 \lt 2(1)$. Next, use strong induction to assume it's true for all $n \le k$ for some $k \ge 1$. Note since $T(n) \lt 2n$ for all $1 \le n \le k$, this means that $T(n) \le 2n - 1$ since it's values are all integral. Thus, using that $\left\lfloor\frac{k+1}{2}\right\rfloor \le k$ and $\left\lceil\frac{k+1}{2}\right\rceil \le k$, plus that $\left\lfloor\frac{k+1}{2}\right\rfloor + \left\lceil\frac{k+1}{2}\right\rceil = k + 1$ for all integers $k$, you have
$$\begin{equation}\begin{aligned}
T(k + 1) & = T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right) + T\left(\left\lceil\frac{k+1}{2}\right\rceil\right) + 1 \\
& \le \left(2\left\lfloor\frac{k+1}{2}\right\rfloor - 1\right) + \left(2\left\lceil\frac{k+1}{2}\right\rceil - 1\right) + 1 \\
& = 2\left(\left\lfloor\frac{k+1}{2}\right\rfloor + \left\lceil\frac{k+1}{2}\right\rceil\right) - 1 \\
& = 2(k + 1) - 1 \\
& \lt 2(k + 1)
\end{aligned}\end{equation}\tag{6}\label{eq6A}$$
This shows the inductive step also holds, confirming that $T(n) \lt 2n$ for all $n \ge 1$, meaning that $T(n) = O(n)$. Note since $T(n) \lt 2n$, it's also trivially true that $T(n) \le 2n$, meaning the definition of $O$ holds for any $c \ge 2$, i.e., you have $T(n) \le cn$.
