I've just finished an induction equation, however i'm a little hit and miss about whether its actually right on not. Mainly in my working out, I'd really appreciate if you could have a look at it and tell me whether I went wrong or not.
The questions is: T(n) = 3T(Ln/4_|) + n^2 //Note the L and _| are for round down let T(0) = 0 & T(1) = 1
T(n) = cn^3 T(n/4) = c(n/4)^2
T(n) = 3(n/4)^2 + n^2 <= cn^2
3n^2/16 + n^2 <= cn^2
(3/16)n^2 + n^2 <= cn^2
(3/16) + 1 <= cn^2
(19/16) <= cn^2
~ 1.1875 <= c
T(0) = 3(L0/4_|) + 0^2 = 0
T(0) <= c(0)^2
0 <= c
T(1) = 3(L1/4_|) + 1^2 = 1
T(1) <= c(1)^2
1 <= c
Now I dont really know where to go from here but I assume the above equation is proved because T(1) has a similar answer to the above induction.
P.S Sorry if its a bit rough by the title, I wasn't to sure what to call it, but wanted people to be able to find it so I went with that, hope its not too vague
You're given a function $T(n)$ defined recursively by $T(0)=0, T(1)=1$, and $$ T(n) = 3\,T(\lfloor n/4\rfloor)+n^2\quad\text{for $n>1$} $$ and I presume you wish to show that there exists a $c$ such that $T(n)\le c(n/4)^2$ for all integers $n\ge 0$. (Since showing equality here is actually not possible.)
Discovery phase. Let's try to find a $c$ value that might work here. If we're going to have $T(n)\le c(n/4)^2$, then we'll have to have $$ \begin{align} T(n) &= 3\,T(\lfloor n/4\rfloor)+n^2\\ &\le 3c(\lfloor n/4\rfloor/4)^2+n^2\\ &\le 3c(n/16)^2+n^2\\ &\le \frac{3c}{256}n^2\\ &=\frac{3c+256}{256}n^2 \end{align} $$ and if this is going to be less than or equal to $c(n/4)^2$ we'll have to have $$ \begin{align} \frac{3c+256}{256}\le \frac{c}{16} \end{align} $$ so it looks like we'll need $c\ge 256/13$. From this, an induction proof is easy.
Claim. For the function $T$ defined above, we have $T(n)\le (256/13)(n/4)^2=(16/13)n^2$. Obviously, we'll induct on $n$:
Base. $T(0) = 0 \le (16/13)\,0^2$ and $T(1)=1\le (16/13)\,1^2$
Induction. Suppose that the claim is true for all $0\le k < n$. Then $$ \begin{align} T(n) &= 3\,T(\lfloor n/4\rfloor)+n^2 &\text{by definition}\\ &\le 3\cdot \frac{16}{13}\left\lfloor \frac{n}{4}\right\rfloor^2+n^2 &\text{by assumption}\\ &\le\frac{3}{13}n^2+n^2 &\text{since $\lfloor x \rfloor \le x$ for any $x$}\\ & = \frac{16}{13}n^2 &\text{as required} \end{align} $$