I am asked to solve the following recurrence relation by what we call "substitution" in my class, where you assume a solution, and then show that it is true by induction. I have $$t(n) = 2t(n/2) + 1$$ I have shown by other methods that this is $\mathcal{O}(n)$ and for this method, I do the following:
Assume $t(n) = \mathcal{O}(n)$ then given $t(n/2) \leq cn/2$ we want to show that $t(n) \leq cn$. Note that this has to be the $same$ $c$. I have used this method to prove other recurrence relations. However, for some reason, my algorithms prof told me that this one needs some kind of trick... I have checked Cormen's (he said there is an example in there) and can't find anything in the relevant section. Here is an example of how such a proof works for another example.
$$t(n) = 2t(n/2) + n\log(n)$$ Since we know that the recurrence relation for mergesort is given by $t(n) = 2t(n/2) + n$ has the solution $t(n) = \mathcal{O}(n\log n)$, we might assume that $t(n) = 2t(n/2) + n\log(n)$ has the solution $t(n) = \mathcal{O}(n\log^2(n))$. We will attempt to show this by substitution. \begin{align*} t(n) &= 2t(n/2) + n\log n \\ \mathrm{guess }\ t(n) &= \mathcal{O}(n\log^2n) \\ \mathrm{assume }\ t(n/2) &\leq c(n/2)log^2(n/2) \\ \mathrm{show} \ t(n) &\leq cn\log^2(n) \\ t(n) &= 2t(n/2) + n\log n \\ t(n) &\leq 2(c(n/2)\log^2(n/2)) + n\log n \\ &= cn(\log^2n - 2\log(n)\log(2) + \log^2n) + n\log n \\ &= cn\log^2n -cn(\log(n)\log(2) -\log^2(2)) + n\log n \end{align*} Recall that we wanted to show $$t(n) \leq cn\log^2n$$ so we get \begin{align*} cn\log^2n-cn(\log(n)\log(2)-log^2(2)) + n\log n &\leq cn\log^2n \\ cn(\log(n)\log(2) - log^2(2)) &\geq n\log n \end{align*} Which is true for sufficiently large $c$.
Attempting such a solution here gives the following problem: Let us make a conjecture that $t(n)$ is $\mathcal{O}(n)$. Then we will try to prove this by induction.\ We begin by assuming that by the definition of $\mathcal{O}(n)$ that $t(n/2) \leq cn/2$. Then we need to show that $t(n) \leq cn$. \begin{align*} t(n) &=2t(n/2) + 1 \\ t(n) &\leq 2(cn/2) + 1 \\ &=cn + 1 \end{align*} we want to show that $t(n) \leq cn$ so we get $$cn+1 \leq cn$$
This is obviously a contradiction. Does anyone know how to proceed from here?
Try to prove that $t(n) \leq \frac{1}{2} c n+n-1$
So $t(n)\leq 2t(n/2)+1 \leq 2(\frac{1}{2}c n/2+n/2-1)+1= \frac{1}{2}c n+n-2+1= \frac{1}{2}c n+n-1$.
And then its easy to prove that $t(n) \leq \frac{1}{2}c n +n-1 \leq c n$
Whenever $c\geq2$, since its $O(n)$ we can put $c>2$.