how do I prove that for a recurrence relation of the form $a(2 n)=2^k a(n), a(n)=c n^{k}$ for some constant $c$?

Question

if this is difficult, I am satisfied with an example for when $k=2$

in other words, how do I prove that for a recurrence relation of the form $a(2 n)=4 a(n), a(n)=c n^{2}$ for some constant c?

Answer 1

Not sure if this is proper induction, since all odd $n$ are like base cases;

Question

Given $a(2n)=2^{k}a(n)$, show that $a(n) = cn^k$.

Base Case: $n=1$ (ish; unsure here)

$$a(1) = c$$ Use this to define $c$.

Inductive step: Assume $a(n) = cn^k$, show $a(2n) = c(2n)^k$. Now from the recurrence relation $$\begin{aligned} a(2n) &= 2^ka(n)\\ &= 2^k cn^k\\ &= c(2n)^k\,. \end{aligned} $$

This at least proves it for $n = 2^i$, $i \in \mathbb{N}_0$.