Induction Proof (relating two recurrences)

Question

Let $L(n) = n + 2 L\left(\frac{n}{2}\right), \, L(1) = 1,$

and $U(n) = 9n + 2U\left(\frac{n}{2}\right), \, U(1) = 9.$

Prove by induction that $U(n) = 9L(n)$ where $n = 2^k$.

I attempted to prove this question but I did not get the correct end result to prove it.

Can someone please help me with this induction proof? Help would greatly be appreciated.

Thank you.

Answer 1

Assume $U(n)=9L(n)$, you already have the base case established. This also means it holds for all $k<n$, namely $\frac{n+1}{2}<n$. Then,

$U(n+1) = 9(n+1) + 2U(\frac{n+1}{2}) = 9n + 9 + 9*2L(\frac{n+1}{2})$.

But,

$L(n+1) = (n+1) + 2L(\frac{n+1}{2}) $

$\Rightarrow 2L(\frac{n+1}{2}) = L(n+1)-n-1$.

Then, since $\frac{n+1}{2}<n$, we have

$U(n+1) = 9n + 9 + 9(L(n+1)-n-1) = 9L(n+1)$,

as desired.

Answer 2

As an additional observation that may be helpful one sees that if $$n = \sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k$$ is the binary representation of $n$ then the two recurrences can be solved exactly for all $n$ (not just powers of two) by putting $L(0)=0$ and $U(0)=0$ and otherwise $$L(n) = \sum_{k=0}^{\lfloor\log_2 n\rfloor} \sum_{j=k}^{\lfloor\log_2 n\rfloor} d_j 2^{j-k} \quad\text{and}\quad U(n) = 9\times \sum_{k=0}^{\lfloor\log_2 n\rfloor} \sum_{j=k}^{\lfloor\log_2 n\rfloor} d_j 2^{j-k}.$$ This is immediate from the two recurrences. At that point there is nothing left to prove.