Do we have to claim it? If so, at which point? I have to solve the recurrence relation
$$T(n)=\left\{\begin{matrix}
3T\left (\frac{n}{4} \right)+n & , n>1\\ 
1 &, n=1 
\end{matrix}\right.$$
and prove by induction that the solution I found is right.
I found that the solution of the recurrence relation is $T(n)=O(n)$.
I started proving it like that:


*

*$n=1: T(1)=1 \leq c \cdot 1 \checkmark \text{ for } c \geq 1$

*We suppose that for any $m$, $2 \leq m <n , n>2$: $T(m) \leq c \cdot m$.

*We want to show that the claim stands for $n$.


But, then I noticed that we do not have a formula for $T \left ( \frac{n}{4} \right)$ when $n<4$ and also when $n \neq 4^k$.
So, do we have to suppose that $n \geq 4$ and $n=4^k$ ? 
If so, at which point of the proof, do I have to claim it?
 A: By way of enrichment we  solve another closely related recurrence that
admits an exact  solution.  Suppose we have $T(0)=0$  and for $n\ge 1$
(this gives $T(1)=1$) 
$$T(n) = 3 T(\lfloor n/4 \rfloor) + n.$$
Furthermore let the base four representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$
Then we  can unroll the  recurrence to obtain the  following exact
formula for $n\ge 1$
$$T(n) = \sum_{j=0}^{\lfloor \log_4 n \rfloor} 
3^j \sum_{k=j}^{\lfloor \log_4 n \rfloor} d_k 4^{k-j}.$$
Now to get an upper bound consider a string of three digits which yields
$$T(n) \le \sum_{j=0}^{\lfloor \log_4 n \rfloor} 
3^j \sum_{k=j}^{\lfloor \log_4 n \rfloor} 3 \times 4^{k-j}
= 16\times 4^{\lfloor \log_4 n \rfloor} 
-\frac{27}{2} 3^{\lfloor \log_4 n \rfloor} + \frac{1}{2} .$$
Note that this bound is attained and cannot be improved.
The lower bound is for the case of a one digit followed by a string of
zeros and yields
$$T(n) \ge \sum_{j=0}^{\lfloor \log_4 n \rfloor} 
3^j \times 4^{\lfloor \log_4 n \rfloor-j}
= 4\times 4^{\lfloor \log_4 n \rfloor}
- 3\times 3^{\lfloor \log_4 n \rfloor}.$$
This bound too is attained.

Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$4^{\lfloor \log_4 n \rfloor}
\in \Theta\left(4^{\log_4 n}\right) 
= \Theta(n).$$
These are  in agreement with what the Master theorem would produce.

Here is another MSE link where some similar computations are carried out.
