0

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?

alosapien
  • 1
  • See this guide for how to mark up math nicely on this site. I don't understand from your definition $a(2n)=4a(n)$ how $a(3)$ would be defined - can you explain? – Frentos Jan 22 '16 at 10:47
  • If you are the person who proposed an anonymous edit to your own question, I suggest that you merge your accounts. Better yet, make the edit under the alosapien account. – N. F. Taussig Jan 22 '16 at 10:55
  • You cannot prove it, because it's wrong. Consider $$a\bigl(2^r(2m+1)\bigr):=2^{kr}\qquad(r\geq0,\ m\geq0)\ .$$ – Christian Blatter Jan 22 '16 at 16:14

1 Answers1

0

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$.

Steve
  • 127