Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
1  
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

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
$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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.