A weird convolution (recurrence relation)

  • Thread starter rsq_a
  • Start date
  • #1
107
1

Main Question or Discussion Point

The answer doesn't seem obvious to me:

If I set up

[tex]B_0 = 1[/tex] and [tex]B_n = n^2[/tex]

Then let

[tex]A_n = \sum_{m=0}^n B_m B_{n-m} = 2B_0 B_{n} + 2B_1 B_{n-1} + \ldots[/tex]

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

In general, it seems that if [tex]B_n \sim O(n^a)[/tex] then [tex]A_n \sim O(n^{2a+1})[/tex]
 
Last edited:

Answers and Replies

  • #2
391
0
for big m replace the sum by an integral

[tex] \sum_{m=0}^{n}B_{m}B_{n-m}\sym \int_{0}^{x}dtB(t)B(x-t) [/tex]

the integral [tex] \int_{0}^{x}dt(x-t)^{2}t^{2} [/tex] using the Binomial theorem includes the integral of terms [tex]t^{4} [/tex] which is itself proportinal to [tex] x^{5} [/tex] this is the solution to your paradox
 
  • #3
107
1
for big m replace the sum by an integral

[tex] \sum_{m=0}^{n}B_{m}B_{n-m}\sym \int_{0}^{x}dtB(t)B(x-t) [/tex]

the integral [tex] \int_{0}^{x}dt(x-t)^{2}t^{2} [/tex] using the Binomial theorem includes the integral of terms [tex]t^{4} [/tex] which is itself proportinal to [tex] x^{5} [/tex] 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 [tex]O(n^5)[/tex].

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

Related Threads for: A weird convolution (recurrence relation)

  • Last Post
Replies
3
Views
2K
Replies
1
Views
1K
Replies
1
Views
630
Replies
6
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
7
Views
740
  • Last Post
Replies
1
Views
2K
Top