Induction proof that $g(n) = 2g(\frac{n}{2}) + an^2 = 2an^2 -an$

Question

Let $g: \mathbb{N} \rightarrow \mathbb{R^+}$, $g(1) = a$ and $g(n) = 2g(\frac{n}{2}) + an^2$. I found the closed form $g(n)= 2an^2 -an$. No i want to proof it by induction. So the Base case and den induction hypothese are clear. I don't know how i can do the induction Step.

Answer 1

Let $P(n)$ be the statement that $g(n)=2an^2-an$. Seeing as how the given expression of $g(n)$ is in terms of $g(\frac{n}{2})$, I believe that induction can only go so far as to prove $P(n)$ to be true $\forall n=2^{k-1}, \ k\in\mathbb{Z^+} $.

Base case: \begin{align*} g(1) &= 2a(1)^2 - a(1) \\ &= 2a - a \\ &= a \quad \therefore P(1) \text{ is true} \end{align*}

Assume that $g(x) = 2ax^2-ax$ for some $x\in\mathbb{Z}^+$ \begin{align*} g(2x) &= 2g(\tfrac{2x}{2})+a(2x)^2\\ &= 2g(x)+4ax^2\\ &=2[2ax^2-ax]+4ax^2\\ &=8ax^2-2ax\\ &=2a(2x)^2-a(2x) \quad \therefore P(x) \text{ is true} \implies P(2x) \text{ is true} \end{align*}

Then by mathematical induction, $P(n)$ is true $\forall n=2^{k-1}, \ k\in\mathbb{Z^+} $.

Answer 2

Simple: lets assume the formula is right for $g(\tfrac{n}{2})$, then $$ 2g(\tfrac{n}{2}) + an^2 = 2(\tfrac{an^2}{2}-\tfrac{an}{2}) +an^2 = 2an^2 -an = g(n) $$ P.S.:g.j. finding the closed form!