Prove by induction T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n

Question

Prove by induction on n that T(n)=O(n), where T(0)=1, T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n

So far I have,

Base Case: n = 1

[1/2] + [7/16] + 1

T(1) = 1

Induction hypothesis: Assume that for arbitrary n, T(n) ≤ n Prove T(n+1) ≤ (n+1)?

Answer 1

Actually, this is true if $T(n) =an + \sum_{j=1}^m T(\lfloor b_j n \rfloor) $ where $a, b_j > 0$ and $\sum_{i=1}^m b_j < 1 $. The proof is almost identical to the following proof for the coefficients in the original problem.

Suppose $T(k) \le ck $ for $\lfloor 7n/16 \rfloor \le k < n$.

Then $T(n) =T(n/2)+T(7n/16)+n \le c(n/2+7n/16)+n = n(1+15c/16) $ and this is $\le cn$ if $1+15c/16 \le c $ or $1\le c/16 $ or $c \ge 16 $.

Note that this is where $\sum b_j < 1$ would come in.

Therefore, if we can find a $c \ge 16$ such that $T(k) \le ck$ for $\lfloor 7n/16 \rfloor \le k \le n-1$, then $T(n) \le cn$ for all larger $n$.

So choose a $c$ that works once $n > 4$, say.