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)
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:
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$