# I cannot get the convolution of Jacobsthal(n) and 3^n using Convolve[], DiscreteConvolve[] or ListConvolve[]

I am working on a problem where I found that the system I am working with follows OEIS A094705 which is the: "Convolution of Jacobsthal(n) and 3^n". So I have tried using the recursive formula Jacobsthal(n) and 3^n (also Jacobsthal(n-1) and 3^(n-1) to make sure it was not a list issue on the starting term of the series), also the respective lists in the format:

{0, 1, 1, 3, 5, 11, 21, 43, 85, 171}


and,

{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683}


I would like to use the previous two sequences to generate OEIS A094705:

{0, 1, 4, 15, 50, 161, 504, 1555, 4750, 1442}


I have tried, for example, the following three methods when using ListConvolve:

ListConvolve[
{0, 1, 1, 3, 5, 11, 21, 43, 85, 171},
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683}
]
(*Out {14421} *)

ListConvolve[
{0, 1, 1, 3, 5, 11, 21, 43, 85, 171},
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683},
-1
]
(* Out:
{14421,43263,70741,153175,282381,551903,1006181,1778535,2796541,3370543}
*)

ListConvolve[
{0, 1, 1, 3, 5, 11, 21, 43, 85, 171},
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683},
1
]
(* Out:
{43263, 70741, 153175, 282381, 551903, 1006181, 1778535, 2796541, 3370543, 14421}
*)


I really hope that math concept convolution and Mathematica Convolve, DiscreteConvolveand ListConvolve are the same and not just using similar words.

Let's define Jacobsthal's numbers:

Clear[jacob]
jacob[n_Integer] := (2^n - (-1)^n)/3


Then, from the definition (which you demonstrated yourself in your first ListConvolve expression for one element):

Clear[a094705]
a094705[n_Integer] := First@
ListConvolve[
Table[jacob[i], {i, 0, n}],
3^Range[0, n]
]

Table[a094705[x], {x, 0, 10}]

(* Out: {0, 1, 4, 15, 50, 161, 504, 1555, 4750, 14421, 43604} *)

• What if Convolve-ing an expression with another expression? @MarcoB May 26, 2020 at 1:53
• @prog, Convolve[] uses integration and not summation, so quite likely not the function you're interested in for this case. May 26, 2020 at 12:59

I really hope that math concept convolution and Mathematica Convolve, DiscreteConvolve and ListConvolve are the same and not just using similar words.

Well, you are supposed to be checking that the definition Mathematica uses is the same as the definition you are using. Not just in this case, but any time you use nontrivial functionality.

In this particular case, the definition you seem to expect,

$$(f\ast g)(n)=\sum_{k=0}^n f(k)g(n-k)$$

and the definition used by Mathematica and Wikipedia,

$$(f\ast g)(n)=\sum_{k=-\infty}^\infty f(k)g(n-k)$$

surely aren't the same.

To get the finite version, then, you need to multiply by a UnitStep[] factor:

Table[DiscreteConvolve[UnitStep[k] (2^k - (-1)^k)/3, UnitStep[k] 3^k, k, n],
{n, 0, 20}]
{0, 1, 4, 15, 50, 161, 504, 1555, 4750, 14421, 43604, 131495, 395850, 1190281, 3576304,
10739835, 32241350, 96767741, 290390604, 871346575, 2614389250}


And, whenever you are in doubt, one can always go back to the classical definitions to check. Thankfully Mathematica lets you do this in this case:

(* explicit formula for convolution *)
Table[Sum[((2^k - (-1)^k)/3 3^(n - k)), {k, 0, n}], {n, 0, 20}]

(* series coefficient of product of generating functions *)
Table[SeriesCoefficient[x/((1 + x) (1 - 2 x) (1 - 3 x)), {x, 0, n}], {n, 0, 20}]


and both snippets should give the same result as the original.