Let $(u_n)$ be the sequence defined as follows
$$u_0=1$$ $$u_n=u_{\left\lfloor \tfrac n 2 \right\rfloor} + u_{\left\lfloor \tfrac n 3 \right\rfloor} + u_{\left\lfloor \tfrac n 6 \right\rfloor}$$ ($n \in \mathbb{N}^*$)
First question asks to prove that for all naturals $n$ , $$u_n \ge n+1 $$ Strong induction seems to do the job.
Second question asks to find a constant $C>0$ such that for all naturals $n$
$$u_n \le C(n+1)$$
I'm stuck with this question. Could anyone give it a try. thanks.
Firstly, It can be proven by induction that $\forall n\in\mathbb{N}: u_{n}\leq u_{n+1}$.
Now, We'll notice that for $\forall n\in\mathbb{N}$ : $$u_n=u_{\lfloor\frac{n}{2}\rfloor}+u_{\lfloor\frac{n}{3}\rfloor}+u_{\lfloor\frac{n}{6}\rfloor}=u_{\lfloor\ \frac{\lfloor\frac{n}{2}\rfloor}{2}\ \rfloor}+u_{\lfloor\ \frac{\lfloor\frac{n}{2}\rfloor}{3}\ \rfloor}+u_{\lfloor\ \frac{\lfloor\frac{n}{2}\rfloor}{6}\ \rfloor}+u_{\lfloor\frac{n}{3}\rfloor}+u_{\lfloor\frac{n}{6}\rfloor}$$ From the above inequality: $$\leq u_{\lfloor\frac{n}{4}\rfloor}+u_{\lfloor\frac{n}{6}\rfloor}+u_{\lfloor\frac{n}{12}\rfloor}+u_{\lfloor\frac{n}{3}\rfloor}+u_{\lfloor\frac{n}{6}\rfloor}=\dots\quad(*)$$ We can continue dividing $u_{\lfloor\frac{n}{4}\rfloor}, u_{\lfloor\frac{n}{6}\rfloor}, u_{\lfloor\frac{n}{12}\rfloor}, u_{\lfloor\frac{n}{3}\rfloor}$ iteratively. This process will halt once we reach $u_0$ for each element. Now, we'll notice that we split each element from (*) into 3 elements and that the process of splitting one element is bounded by $\log_{3}({n})$ steps, since for every $m\geq3$: $\log_{m}({n})\leq\log_{3}({n})$.
We get the following: $$(*)\ \leq 3^{\log_{3}({n})}+3^{\log_{3}({n})}+3^{\log_{3}({n})}+3^{\log_{3}({n})}+3^{\log_{3}({n})} =\\ =5\cdot n\leq 5(n+1)$$ Thus, we have proven $\forall n\in\mathbb{N}: u_n\leq 5(n+1)$.
Note: This answer is most definitely not the most efficient bound, as I believe this should be true for even C = 3.