A weird convolution (recurrence relation)

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

 

[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

 

[rsq_a]

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.