Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A weird convolution (recurrence relation)

  1. Apr 11, 2010 #1
    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: Apr 11, 2010
  2. jcsd
  3. Apr 11, 2010 #2
    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
  4. Apr 11, 2010 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook