Vtyjkyuk

While solving the recurrence
$$T(n) leq (n-1) +frac2n sum_i= n/2^n-1 T(i)$$
our professor directly went to the hypothesis step without showing the basis step. Here the hypothesis step is:

Assume inductively that $T(i) leq 4i$ for $i < n$.

Edit: Here is complete context:

Let $T(n, k)$ denote the expected time to find the $k$-th smallest in an array of size $n$, and let $T(n) = max_k T(n, k)$. We will show that $T(n) < 4n$.

First of all, it takes $n-1$ comparisons to split into the array into two pieces in Step 2. These pieces are equally likely to have size $0$ and $n-1$, or $1$ and $n-2$, or $2$ and $n-3$, and so on up to $n-1$
and $0$. The piece we recurse on will depend on $k$, but since we are only giving an upper bound, we can imagine that we always recurse on the larger piece.

What would be appropriate basis step for this recurrence ?

Thanks in advance.

$$T(i)le4itext for i<n,$$ for some $n$ which depends on the problem on hand (I cannot guess).

E.g. $$T(1)le4,T(2)le8.$$