Let
$$T(n):=\begin{cases} 3 & \text{if }n=1\\ 4 \cdot T(n/4) + 3 & \text{if }n>1\end{cases}$$
Prove that $T(n) = 4n − 1$ for all $n \geq 1$.
Base case: When $n = 1$, LHS $= T(1) = 3$, RHS $= 4 \cdot 1 − 1 = 3$. Therefore, LHS = RHS
LHS = Left hand side RHS = right hand side
Can somebody explain to me how RHS has been transformed into RHS $= 4 \cdot 1 − 1 = 3$ from $T(1) = 4 \cdot T(n/4) + 3$ ? Thanks
For $n=1$ we have that $T(1)=3=4\cdot 1-1$. Thus the two definitions agree and hence the induction start holds.
Now assume the claim to be true for all indexes up to $\;n\;$, and go for $\;n+1\;$ :
$$T(n+1):=4T\left(\frac{n+1}4\right)+3\stackrel{\text{Ind. Hypot.}}=4\left(4\frac{n+1}4-1\right)+4=$$
$$=4n+4-4+3=4n+3=4(n+1)-1$$