I am preparing for my exam in algorithm & data structures by working myself through some assignments handed out by our professor.
One of the assignments and its solution in particular confuse me.
The assignment is to prove, that $U(n) = \mathcal{O}{(4^n)}$, where $$ U(n) = \begin{cases} 1, & \text{if 1 $\leq$ n $\leq$ 2} \\ U(n-2) + 2U(n-1) + 1 & \text{if n > 2} \end{cases} $$
By using the definition for $\mathcal{O}$, I figured out, that I had to proof that: $$ U(n) \leq 4^n $$
Inserting the definition of $U$, I get stuck here: $$ \begin{align} U(n) & \leq U(n-2) + 2 * U(n-1) + 1 \\ & \leq 4^{n-2} + 2 * 4^{n-1} + 1 \end{align} $$
At this point I am stuck; the proposed solution, however, goes further: $$ \begin{align} U(n) & \leq \ldots \\ & \leq 4^{n-2} + 2 * 4^{n-1} + 1 \tag{1}\label{1}\\ & \leq 4^{n-1} + 2 * 4^{n-1} + 4^{n-1} \tag{2}\label{2}\\ & \leq 4*4^{n-1} = 4^n. \ \end{align} $$
Why am I allowed to simply replace the addends $4^{n-2}$ and $1$ from equation $\ref{1}$ simply with $4^{n-1}$ resulting in equation $\ref{2}$?
What is the general rule behind it? Can I replace any addend with a bigger addend in this class of proofs?
For any $n\geq 1,$ it's obvious that $1\leq 4^{n-1}.$ Also, $$4^{n-2}\leq 4^{n-1}$$ for any $n$. So, they just bounded the terms in (1) by the above in order to combine everything together to get $4^n$, like you wanted. Since the inequalities hold, doing this process is valid (to answer your final question). Just be careful that you don't get overzealous and bound by something too large!