# Solving $A(x) = 2A(x/2) + x^2$ Using Generating Functions

Suppose I have the recurrence:

$$A(x) = 2A(x/2) + x^2$$ with $A(1) = 1$.

Is it possible to derive a function using Generating Functions? I know in Generatingfunctionology they shows show to solve for recurrences like $A(x) = 2A(x-1) + x$. But is it possible to solve for the above recurrence as well?

-
Can you change variables, $x=2^y$ so $x/2=2^{y-1}$, then use the method you mention? – GEdgar Nov 25 '11 at 1:54
@GEdgar: So you are assuming that y is an integer? I know how to solve this using that assumption, but I want to know if I can use generating functions. – Mark Nov 25 '11 at 1:59
No. He doesn't. – leo Nov 25 '11 at 2:27
Mark: As written, the recurrence makes sense only for $x$ a power of two (and GEdgar's comment makes sense for such an $x$). For a general $x$, one needs to tweak the equation using floors and ceilings appropriately. – Srivatsan Nov 25 '11 at 3:13
Let's take $x = 72$, something not a power of $2$. $A(72)$ is defined in terms of $A(36)$. $A(36)$ in terms of $A(18)$, which is based on $A(9)$. What next? [Unless $x$ is a power of $2$, repeated halving will always end up in an odd number bigger than $1$ for which the recurrence is not defined.] – Srivatsan Nov 25 '11 at 3:36

I am a little confused by the way you worded this question (it seems that you have a functional equation rather than a recurrence relation), so I interpreted it in the only way that I could make sense of it. If this is not what you are looking for, then please clarify in your original question or in a comment.

Let's assume that $A(x)$ is a formal power (or possibly Laurent) series, $A(x) = \sum_n a_n x^n$. Plugging this into your equation, we get $$\sum_n a_n x^n = 2 \sum_n a_n \frac{x^n}{2^n} + x^2$$ For $n\neq 2$, we get $a_n = 2^{1-n} a_n$, so if $n \neq 1,2$ we get $a_n = 0$. For $n=2$, we get $a_2 = a_2/2 + 1$, so $a_2 = 2$. Finally, the condition $A(1) = 1$ gives $a_1 = -1$, so we have $$A(x) = -x + 2x^2$$

Check: $$2 A(x/2) + x^2 = 2( -x/2 + x^2/2) + x^2 = -x + 2x^2 = A(x)$$

-
$A(x)$ is a sequence, not a generating function. The recurrence should perhaps be written $a_n = 2 a_{\lfloor n/2 \rfloor} + n^2$. – Qiaochu Yuan Nov 25 '11 at 4:10

As per Qiaochu's comment on the answer so far, consider

$$a_n = 2 a_{\lfloor n/2 \rfloor} + n^2$$

with $a_1 = 1$ and $a_n = 1, 6, 11, 28, 37, 58, 71, 120,\dots$ for $n = 1,2,\dots$. Then

$$a_{2n} = 2 a_n + 4n^2 \quad\quad\text{and}\quad\quad a_{2n+1} = 2 a_n + 4n^2 + 4n + 1$$

where both recurrences are valid for $n\ge 1$. Working with each recurrence we can use generating functions to obtain a system of functional equations. Let

$$f(z) = \sum_{n=1}^{\infty}a_n z^n$$

be the generating function for the sequence of $a_n$'s. Working with the first equation we multiply by $z^{2n}$, sum over all $n\ge 1$

$$\sum_{n=1}^{\infty}a_{2n}z^{2n} = 2\sum_{n=1}^{\infty}a_n(z^2)^n + \sum_{n=1}^{\infty}4n^2z^{2n}$$

and obtain

$$\frac{f(z) + f(-z)}{2} = 2f(z^2) + \frac{4 z^2 \left(1+z^2\right)}{\left(1-z^2\right)^3}$$

Working with the second equation, we multiply by $z^{2n+1}$, sum over all $n\ge 1$

$$\sum_{n=1}^{\infty}a_{2n+1}z^{2n+1} = 2z\sum_{n=1}^{\infty}a_n(z^2)^n + \sum_{n=1}^{\infty}(4n^2+4n+1)z^{2n+1}$$

and obtain

$$\frac{f(z)-f(-z)}{2} -z = 2zf(z^2)+\frac{z^3 \left(z^4-2 z^2+9\right)}{\left(1-z^2\right)^3}$$

We can obtain a solution by solving these functional equations.

EDIT: Adding the two equations together and simplifying we obtain

$$f(z) = \frac{z+z^2}{(1-z)^3} + 2(1+z)f(z^2)$$

We can iterate this equation to obtain better and better approximation of $f(z)$. I believe that if we iterate enough times to have $f(z^{2^t})$ as part of the approximation, then the approximation will be exact for the first $2^t-1$ coefficients.

-

Yes that would be possible but this would probably require $x$ to be an integer and then you have a problem with the $x/2$ term since the recursion only links the values of $A$ on a given set $S_k=\{(2k+1)2^n\mid k\geqslant0,\,n\geqslant 0\}$ and it can tell nothing about the values of $A$ in different sets $S_k$.

Assuming the recursion holds for every positive real number $x$, it is equivalent to $B(x)=B(x/2)$ with $$B(x)=(A(x)/x)-2x.$$ Hence the function $C:t\mapsto B(2^t)$ defined for every real number $t$ is $1$-periodic with the only condition that $C(0)=-1$.

The solutions of the original equation are $A : x\mapsto 2x^2-xa(x)$ where $a(1)=1$ and $a(2x)=a(x)$ for every $x$, for example, $a(x)=\cos(2\pi\log_2x)$.

-