<s>[INST] Prove $T(n) = T(\lfloor n/2 \rfloor) * T(\lfloor n/2 \rfloor) \leq 2^n$ I am stuck on the below problem.
Here is what I have so far, and I have highlighted the area that I am not understanding, particularly in the induction step when we start evaluating for k+1.
$T(n) = T(\lfloor \frac{n}{2} \rfloor) * T(\lfloor \frac{n}{2} \rfloor)$
Where $T(1) = 1$.
Show that $T(n) \leq 2^n$ by induction.
To prove that $T(n) \leq 2^n$, given that $T(1) = 1$, you can again use induction. Here's how you can do this for the given recurrence relation:
First, we need to show that the upper bound holds for the base case.
Base Case
In this case, the base case is $n = 1$, and we know that $T(1) = 1$. Since $1 <= 2^1$, the upper bound holds for the base case.
Next, we need to show that if the upper bound holds for a given value of $n$, it must also hold for the next value of $n$. To do this, we can assume that the upper bound holds for some arbitrary value of n and then show that it follows that the upper bound must also hold for $n + 1$.
Induction Step - problem I'm having below
For example, suppose we assume that the upper bound holds for $n = k$. This means that $T(k) <= 2^k$. We can then evaluate $T(k+1)$ as follows:
$T(k+1) = T(\frac{k+1}{2}) * T(\frac{k+1}{2})$
$= T(\frac{k}{2}) * T(\frac{k}{2})$ // WHY ARE THESE TWO THINGS EQUAL?
Since we know that $T(\frac{k}{2}) <= 2^{\frac{k}{2}}$, we can substitute this into the above equation to get:
$T(k+1) \leq 2^{(k/2)} * 2^{(k/2)}$
$= 2^{k/2 + k/2}$
$\leq 2^k$
Since $2^k \leq 2^{k+1}$, the upper bound holds for $n = k + 1$.
Therefore, by induction, we have shown that the upper bound $T(n) <= 2^n$ holds for all values of $n$.
How can we derive that:
$T(k+1) = T(\frac{k+1}{2}) * T(\frac{k+1}{2})$
$= T(\frac{k}{2}) * T(\frac{k}{2})$
 [/INST] You've begun well with your base step, but there are a couple of issues with your induction step. First, the problem uses the floor function for the RHS of the function definition, i.e.,
$$T(n) = T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)\times T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \tag{1}\label{eq1A}$$
but you don't have this. Second, with the floor function being used, note that $T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right)\times T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right) = T\left(\left\lfloor\frac{k}{2}\right\rfloor\right)\times T\left(\left\lfloor\frac{k}{2}\right\rfloor\right)$ is only necessarily true in general if $k$ is even since then $\left\lfloor\frac{k+1}{2}\right\rfloor = \left\lfloor\frac{k}{2}\right\rfloor$. Nonetheless, with $T(1) = 1$, note we can prove (e.g., by induction) that $T(n) = 1 \; \forall \; n \ge 1$, so that statement is then always true.
Instead, to more generally support any $0 \le T(1) \le 2$, I suggest using strong induction so that, for some $k \ge 1$, we have all $1 \le n \le k$ satisfying the requested inequality, i.e.,
$$T(n) \le 2^n \tag{2}\label{eq2A}$$
Next, note $\left\lfloor\frac{k+1}{2}\right\rfloor \ge 1$, and consider $k - \left\lfloor\frac{k+1}{2}\right\rfloor$. If $k$ is even, we get $k - \frac{k}{2} = \frac{k}{2} \gt 0$, and if $k$ is odd we then get $k - \frac{k+1}{2} = \frac{2k-(k+1)}{2} = \frac{k-1}{2} \ge 0$. Thus, the arguments in the RHS of \eqref{eq1A} for $T(k+1)$ will always be $\ge 1$ and $\le k$, i.e., \eqref{eq2A} will be true for $n = \left\lfloor\frac{k+1}{2}\right\rfloor$.
There are now $2$ cases to consider. First, $k + 1$ being even gives that
$$\begin{equation}\begin{aligned}
T(k+1) & = T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right)\times T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right) \\
& = T\left(\frac{k+1}{2}\right)\times T\left(\frac{k+1}{2}\right) \\
& \le 2^{\frac{k+1}{2}} \times 2^{\frac{k+1}{2}} \\
& = 2^{k+1}
\end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Second, $k + 1$ being odd results in
$$\begin{equation}\begin{aligned}
T(k+1) & = T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right)\times T\left(\left\lfloor\frac{k+1}{2}\right\rfloor\right) \\
& = T\left(\frac{k}{2}\right)\times T\left(\frac{k}{2}\right) \\
& \le 2^{\frac{k}{2}} \times 2^{\frac{k}{2}} \\
& \lt 2^{k+1}
\end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Therefore, in both cases, we've proven the induction step that if $T(k) \le 2^{k}$, then $T(k+1) \le 2^{k+1}$. Thus, by strong induction, we've shown that $T(n) \le 2^{n}$ (i.e., \eqref{eq2A}) is true for all $n \ge 1$.
</s>