$T(n) = 2T(\frac{n}{2}+17)+1$ prooving recurrences using induction I am very confused right now I have the following recurrence:
$$T(n)=2T(\frac{n}{2} + 17)+1$$
Now I know That this is evaluates to $O(n)$ but what if I try to prove it using induction for $O(\sqrt n)$:
Base step: $T(1)=2\cdot T(17.5) +1\le c_{1}\cdot \sqrt 1 \rightarrow c_1\gt19$
Assume  $T(k) \lt c_{1}\cdot\sqrt k$: $\forall k\lt n $
Prove for $n$:
$$T(n)=2\cdot T(\frac{n}{2}+17)+1 \le 2\cdot \sqrt{\frac{n}{2}+17}+1\le c_1\cdot \sqrt n$$
$$\sqrt{\frac{2n+68}{m}}+\frac{1}{\sqrt{m}}\lt c_1$$
We can find such $c_1$ and $n_0$ so $\forall n\gt n_0$ this will be true so: $$T(n)=O(\sqrt n)$$
which is total nonsense.
Please help me understand what am I doing wrong and how to prove it the right way (My attempt to prove it to $O(n)$ is identical)
 A: You're forgetting the $c_1$ from your induction hypothesis:
$$
T(n)=2\cdot T(\frac{n}{2}+17)+1 \le 2\cdot \color{red}{c_1} \sqrt{\frac{n}{2}+17}+1 \stackrel{\color{red}{??}}{\leq} c_1\cdot \sqrt n
$$
This complicates your argument. Here's a standard argument to show that the recurrence is $O(n)$.

We prove by induction on $n \in \mathbb N$ that there exist constants $c, d, n_0 \geq 1$ such that for all $n \geq n_0$, we have that:

$$T(n) \leq cn - d \tag{$\star$}$$

Base Case: I'll let you do this part.
Induction Hypothesis: Assume that $(\star)$ holds for all $n' < n$.
It remains to prove that $(\star)$ holds for $n' = n$. Indeed, observe that:
\begin{align*}
T(n)
&= 2T(\tfrac{n}{2} + 17) + 1 \\
&\leq 2(c(\tfrac{n}{2} + 17) - d) + 1 &\text{by the induction hypothesis} \\
&= 2(\tfrac{cn}{2} + 17c - d) + 1 \\
&= cn + 34c - 2d + 1 \\
&= (cn - d) + (34c - d + 1) \\
&\leq cn - d &\text{provided we choose $d \geq 34c + 1$ so that $34c - d + 1 \leq 0$}
\end{align*}
as desired. $~~\blacksquare$
