# A weird convolution (recurrence relation)

1. Apr 11, 2010

### rsq_a

The answer doesn't seem obvious to me:

If I set up

$$B_0 = 1$$ and $$B_n = n^2$$

Then let

$$A_n = \sum_{m=0}^n B_m B_{n-m} = 2B_0 B_{n} + 2B_1 B_{n-1} + \ldots$$

Then I almost expected $$A_n$$ to grow like $$n^2$$. Instead, I'm getting (numerically) that $$A_n \sim O(n^5)$$!! Why is that?

In general, it seems that if $$B_n \sim O(n^a)$$ then $$A_n \sim O(n^{2a+1})$$

Last edited: Apr 11, 2010
2. Apr 11, 2010

### zetafunction

for big m replace the sum by an integral

$$\sum_{m=0}^{n}B_{m}B_{n-m}\sym \int_{0}^{x}dtB(t)B(x-t)$$

the integral $$\int_{0}^{x}dt(x-t)^{2}t^{2}$$ using the Binomial theorem includes the integral of terms $$t^{4}$$ which is itself proportinal to $$x^{5}$$ this is the solution to your paradox

3. Apr 11, 2010

### rsq_a

Hmm...I sort of follow it. For large n, we can compare the growth of the sum to the growth of the integral, which is indeed $$O(n^5)$$.

It's difficult to see how this arises from the direct sum itself, though.