# Recurrence relation and induction

I have this given recurrence relation:

$$T(n) = 3T(\lfloor n/2 \rfloor)$$

Initial value: $$T(1) = 1$$

and I should show that $$T(n) = O(n^{\alpha})$$ and $$\alpha = log_2(3)$$

to solve that I should define: $$P(n) :\Leftrightarrow T(n) \leq n^{\alpha}$$ and $$P(n)$$ holds for all $$n \geq 1$$ and I should show that by induction.

But I don't understand what that $$P(n) :\Leftrightarrow T(n) \leq n^{\alpha}$$ means?

Is $$P(n) = T(n)$$?

solution:

Base:

$$n \geq 1$$ and $$n = 1$$

$$3T(\lfloor 1/2 \rfloor) \leq 1^{log_2(3)}$$

$$\lfloor 3/2 \rfloor \leq 1^{log_2(3)}$$

$$1 \leq 1$$

Hypothesis:

$$3T(\lfloor n/2 \rfloor) \leq n^{log_2(3)}$$

Step:

$$T(n) = 3T(\lfloor \frac{n}{2} \rfloor) \\ \leq (\frac{n}{2})^{log_2(3)} \\ = 3^{log_2(\frac{n}{2})} \\ = 3^{log_2(n)- log_2(2)} \\ = 3^{log_2(n)- 1} \\ \leq 3^{log_2(n)} = n^{log_2(3)}$$

is that right?

• $P(n)$ is not a function but $T(n)$ is, $P(n)$ is a proposition. Dec 27 '19 at 16:15
• ok but how should I define P(n)? Is it not possible to do the induction on T(n)? Dec 27 '19 at 16:17
• I don't think it is the best way to prove it, moreover $T(n)=\mathcal{O}(n^{\alpha})$ doesn't mean that $T(n)\leqslant n^{\alpha}$, it means that there exists $C>0$ such that $T(n)\leqslant C n^{\alpha}$ for all $n\in\mathbb{N}$. I would suggest to study $u_p=T(2^p)$ that verifies $u_{p+1}=3u_p$, show by induction that $T$ is increasing, then use $T(n)\leqslant u_{1+\lfloor \log_2(n)\rfloor}$. Dec 27 '19 at 16:23
• ok thanks I think now I get it Dec 27 '19 at 16:25

Prove, by induction on the number of binary digits of $$n$$, that $$T(n)=3^{\lfloor\log_2n\rfloor}$$. Since $$3^{\log_2n}=n^{\log_23}$$, $$\frac13n^{\log_23}\lt T(n)\le n^{\log_23}$$.
• @ArminZierlinger For $j\in\{0,\,1\}$, $T(2n+j)=3T(n)$. Apart from the factor of $3$, we've deleted the last binary digit of $T$'s argument. Now repeat. The first such digit is $1$.