<s>[INST] Prove using induction that $C(n) = C(n/5) + C(3n/4) + n$ is $O(n)$ I was hoping someone could take a look at my answer to this question and check if it's correct and offer some advice/help on how to correct if it's wrong.
Question:
Consider the function $C: \mathbb N \rightarrow \mathbb N$ defined by:
$C(n) \begin{cases} 1& \text{if } n \leq 5, \\
C(\lfloor \frac{n}{5} \rfloor) + C(\lfloor \frac{3n}{4} \rfloor) + n & \text{if } n > 5 \end{cases}$
Prove, by induction on n, that $C(n) = O(n)$.

My attempt:
For $C(n) = O(n), \exists c > 0, \exists n_o > 1$ such that $ C(n) \leq cn, \text{ } \forall n \geq n_o$
Base case: $n=6, C(6) =  C(\lfloor \frac{6}{5} \rfloor) + C(\lfloor \frac{3(6)}{4} \rfloor) + 5 = C(1) + C(4) + 6 = 1 + 1 + 6 = 8 $
So $c = 1, n_0 = 8$ will suffice for $C(5) = O(n)$
Inductive step: $n > 6$, we know from the inductive hypothesis that $\exists c>0, \exists n_0>1 $ such that $C(\lfloor \frac{n}{5} \rfloor) \leq \frac{cn}{5}$  and $C(\lfloor \frac{3n}{4} \rfloor) \leq \frac{3nc}{4}$ $\forall n \geq n_0$
So, $C(\lfloor \frac{n}{5} \rfloor) + C(\lfloor \frac{3n}{4} \rfloor) + n \leq \frac{cn}{5} + \frac{3nc}{4} + cn $ $\forall n \geq n_0$
Since $\frac{cn}{5} + \frac{3nc}{4} + cn = cn(\frac{1}{5} + \frac{3}{4} + 1) $
So, $C(n) = C(\lfloor \frac{n}{5} \rfloor) + C(\lfloor \frac{3n}{4} \rfloor) + n \leq c'n,$
where $c' = c \cdot (\frac{1}{5} + \frac{3}{4} + 1)$, $\forall n \geq n_0 $
Thus C(n) = O(n).

I have a feeling I'm doing something wrong here, so any help would be much appreciated.
 [/INST] 
I have a feeling I'm doing something wrong 

So, anyway, you have to be partially right and partially wrong. :-) But your feeling is right, because if we want to prove inductively the claim with $n_0$ we have to have also $\lfloor \frac{n}{5} \rfloor\ge n_0$ and $\lfloor \frac{3n}{4} \rfloor\ge n_0$, which makes the induction useless. 
A simple way to overcome such an obstacle is to prove inductively that $C(n)\le cn$ for all $n$. For the induction step it suffices to have $c\ge \frac c5+\frac {3c}4+1$, that is $c\ge 20$. For the base we need to have $c\ge 1$, so $c=20$ fits the proof. 
</s>