$T(n) = \begin {cases} 9T(n/3) - 1 \text{ if n > 1} \\ 1/4 \text{ if n ≤ 1} \end{cases}$
Prove with mathematical induction that this recursive equation has a time complexity of $O($ $n^2 + 1\over8$ $)$
My attempt:
Base case $n=1$ It is obvious that $1/4 \in O$
Recursive case: assume it is true for a given $n$, for $n+1$ we have
$$9T((n+1) / 3 ) - 1$$
Is this correct until now ? What should I do next ?
Any hint or help about what to do next would be very appreciated, because currently I'm a bit confused about what to do next
Thank you for your support
First, note $T(n) \in O\left(\frac{n^2+1}{8}\right)$ means, as stated in big O notation, there's a positive constant $C$ and real number $n_0$ (we can choose $n_{0} = 0$), such that
$$\lvert T(n)\rvert \le C\left(\frac{n^2+1}{8}\right) \; \forall \; n \ge n_{0} \tag{1}\label{eq1A}$$
Using induction on $n$ directly with the recursive equation has a problem that, unless $n$ is $\lt 3$ or an integral multiple of $3$, then the application of the first part will lead to using a function argument of $\frac{n}{3}$ which is non-integral and, thus, has not been handled by the induction process. Instead, we'll deal with all real $n \gt 1$ being related to its next lower integral power of $3$, i.e.,
$$n = 3^{k} + r, \;\; k \in \mathbb{Z}, \;\; k \ge 0, \;\; r \in \mathbb{R}, \;\; 0 \lt r \le 2(3^{k}) \tag{2}\label{eq2A}$$
We'll prove
$$T(n) = \frac{9(3^{k})^2 + 1}{8} \tag{3}\label{eq3A}$$
This can be done by applying $T(n) = 9T\left(\frac{n}{3}\right) - 1$ a total of $k + 1$ times, which gets to an argument $\le 1$, then sum the resulting geometric series and simplify, which is what I did initially. Instead, as you ask to prove this using induction, we'll start with the base case of $k = 0$. Then, since $n \gt 1$ and $\frac{n}{3} \le 1$, we have
$$T(n) = 9T\left(\frac{n}{3}\right) - 1 = 9\left(\frac{1}{4}\right) - 1 = \frac{5}{4} = \frac{10}{8} = \frac{9(1^0)^2 + 1}{8} \tag{4}\label{eq4A}$$
Assume for some integer $m \ge 0$ that \eqref{eq3A} is true for all $0 \le k \le m$. Then for $k = m + 1$, since \eqref{eq2A} gives that $\frac{n}{3} = 3^{k} + r_1$ with $0 \lt r_1 \le \frac{r}{3} \le \frac{2(3^{k+1})}{3} = 2(3^{k})$, then
$$T(n) = 9T\left(\frac{n}{3}\right) - 1 = 9\left(\frac{9(3^{k})^2 + 1}{8}\right) - 1 = \frac{9\left(9(3^{k})^2\right) + 9}{8} - 1 = \frac{9(3^{k+1})^2 + 1}{8} \tag{5}\label{eq5A}$$
so \eqref{eq3A} holds for $k = m + 1$. Thus, by induction, it's true for all $k \ge 0$.
Next, we have from \eqref{eq3A} that
$$T(n) \lt \frac{9(3^{k})^2 + 9}{8} = 9\left(\frac{(3^{k})^2 + 1}{8}\right) \lt 9\left(\frac{n^2 + 1}{8}\right) \tag{6}\label{eq6A}$$
Thus, $C = 9$ works for $n \gt 1$, and since $\frac{1}{4} \lt 9\left(\frac{0^2 + 1}{8}\right) \le 9\left(\frac{n^2 + 1}{8}\right)$ for $0 \le n \le 1$, we've proven \eqref{eq1A} to be true for all real $n \ge 0$.