To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

I have done the proof until the point when $T(n) \leq cn^{\log7}$.

But when it comes to finding the value of constant $c$, I am getting stuck.

The given recurrence relation is $T(n) = 7T(n/2) + n^2$.

Since we already calculated the solution above which is $cn^{\log 7}$.

Inductive step:

Now we have to prove that $T(n) \leq c n^{\log7}$ where $c$ is a positive constant.
If we consider that the solution holds good for $n/2$ then we can prove that it works for $n$ also:
$$T(n/2) \leq c(n/2)^{\log7}.$$
Substituting these values in the recurrence relation:

$$
\begin{align*}
T(n) &\leq 7c/(2)^{\log7} \times (n)^{\log7} + n^2 \\
&\leq cn^{\log7}, \text{ since $7/(2)^{\log7}$ is constant so can be ignored and $cn^{\log7} \gg n^2$ for large $n$} \\
&\leq cn^{\log7} \text{ assuming $c$ is a constant $\geq 1$.}
\end{align*}
$$

Finally to find constant $c$,

$$(7/(2)^{\log7}) \times cn^{\log7} + n^2 \leq cn^{\log7}. $$

I am not able to find appropriate $c$ for which the condition holds true.

You're headed in the right direction, but you need an intermediate step. Permit me to simplify things a bit by defining $\lg n = \log_2n$.

A Dead End

Your substitution method, where you want to establish that $T(n) \le cn^{\lg7}$ inductively, using the assumption $T(n/2)\le c(n/2)^{\lg 7}$ runs into problems, as you've already seen. Here's what happens:
$$\begin{align}
T(n) &= 7T\left(\frac{n}{2}\right)+n^2&\text{by definition}\\
&\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]+n^2&\text{by the inductive assumption}\\
&=7\left[c\frac{n^{\lg7}}{7}\right]+n^2&\text{since $2^{lg 7}=7$}\\
&=c\,n^{\lg7}+n^2
\end{align}$$
and you'll obviously never be able to find a $c$ for which $c\,n^{\lg7}+n^2\le c\,n^{\lg 7}$.

A Way Out

The problem is that the $n^2$ term is messing you up. If it weren't there, then substitution would work. Suppose, for instance, that we had the simpler recurrence $S(n)=7\,S(n/2)$. Now life would be easy, since then the proof above would go through nicely. Assume that $S(n)\le c\,n^{\lg7}$. Then we'd have
$$\begin{align}
S(n) &= 7S\left(\frac{n}{2}\right)&\text{by definition}\\
&\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]&\text{by the inductive assumption}\\
&=7\left[c\frac{n^{\lg7}}{7}\right]\\
&=c\,n^{\lg7}&\text{as required}
\end{align}$$
and if you do this again and again, driving $n$ down to $1$, you'll find that you can choose any $c\ge S(1)$.

Transforming the Dead End Into the Way Out

Let's make the $n^2$ term go away. Let $S(n) = T(n)+k\,n^2$. Then from
$$
T(n)=7\,T(n/2)+n^2
$$
we have, substituting and simplifying,
$$\begin{align}
S(n)-k\,n^2&=7\,[S(n/2)-k(n/2)^2]+n^2&\text{and so}\\
S(n) &= 7\,S(n/2)+n^2(k-7k/4+1)
\end{align}$$
and it's not hard to see that $k=4/3$ will make the $n^2$ term vanish, giving the $S$ recurrence we just solved above. Putting these together we have
$$
T(n)+\frac{4}{3}n^2=S(n)\le c\,n^{\lg7}
$$
and so
$$
T(n)\le c\,n^{\lg7}-\frac{4}{3}n^2

• It always applies to recurrences of the form $S(n)=p\,S(n/q)$ as long as $q\ne0$

• A useful tool to have in your kit is knowing that sometimes you can transform a complicated recurrence into a simple one by suitable addition (or, sometimes, multiplication).

StackExchange Computer Science Q#23892, answer score: 4