# A weird convolution (recurrence relation)

## Main Question or Discussion Point

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:

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

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