4
$\begingroup$

I am studying a recursion below:

$$B_{N,0}=1$$

$$B_{N,k}=-\binom{N+k}{k}^{-1}\sum_{j=0}^{k-1}\binom{N+k}{j}B_{N,j}$$

Now I'm not great at writing in Mathematica. It's been a while since I've used it. So I looked up some old work and came across this method in Mathematica; it's a "memory" property in the code, or thats how I remember it being described to me. So I did it, and wrote the code below.

 B[0]=1

 B[k]=B[k_]:=Simplify[-1/(Binomial[N+k,k])*Sum[Binomial[N+k,j]*B[j]],{j,0,k-1}]

ANd it works! Just not great. So I get the first four or five pretty nicely. These are rational functions in the variable $N$. So the first 5, are posted below (I used Imgur, sorry)enter image description here

But then, the code breaks. I'm sure the recursion gets too difficult as the required computation is getting large. The next two numbers are given as (again, sorry for image)enter image description here

And so here's the question. How can I get it so that the 6th B[6], 7th B[7], ..., kth number B[k], are written or outputted in the elegant factored form as in the previous 5, without that clunky Binomial function in the denominator? I'm interested in the distribution of the denominator's factorization.

$\endgroup$
  • 2
    $\begingroup$ See [Functions That Remember Values They Have Found](https : // reference.wolframcloud.com/language/tutorial/ TransformationRulesAndDefinitions.html #202640595) $\endgroup$ – Bob Hanlon Nov 24 '20 at 4:38
  • $\begingroup$ The denominator looks to be $$\prod_{j=1}^{k}{\left(n+j\right)^{\lfloor\frac{k}{j}\rfloor}}$$. $\endgroup$ – wxffles Nov 25 '20 at 1:06
11
$\begingroup$
ClearAll[B];    
B[k_]:=B[k]=Simplify[FunctionExpand[-1/(Binomial[n+k,k])*Sum[Binomial[n+k,j]*B[j],{j,0,k-1}]]]

Works fine for me:

Table[{"B[" <> ToString[k] <> "]=", B[k]}, {k, 0, 7}] // TableForm

B[k]

Make sure to ClearAll[B] when changing the definition since the values are cached by B[k]:=B[k]. Computing B[k] up to k=7 took 0.02 seconds for me and up to k=42 it took 10.7 seconds. That seems reasonable to me.

$\endgroup$
7
$\begingroup$

Just pointing out the difference between OP's definition and N0va's:

Incorrect version

B[k] = B[k_] := <RHS>

Reading from left to right, the first assignment is single-equals (Set) while the second assignment is colon-equals (SetDelayed). Notice that in the GUI, k appears blue (assuming it is free). In pseudocode:

  1. Mathematica first sees B[k] = <expression1>, and says, "I will immediately evaluate <expression1> and assign the result to B[k]."
  2. Mathematica then sees <expression1>, which is B[k_] := <RHS>, and says, "I will now define B[k_] to be <RHS>, but I will delay the evaluation of <RHS> until I receive an actual value of k."

The second step returns Null, and it is this Null that gets immediately assigned to B[k]. Effectively this is the same as doing

B[k_] := <RHS>
B[k] = Null

i.e. an unmemorised definition followed by an immediate (but rather useless) assignment.

Correct version

B[k_] := B[k] = <RHS>

Reading from left to right, the first assignment is colon-equals (SetDelayed) while the second assignment is single-equals (Set). In pseudocode:

  1. Mathematica first sees B[k_] := <expression2>, and says, "I will now define B[k_] to be <expression2>, but I will delay the evaluation of <expression2> until I receive an actual value of k."

OK, so what happens when an actual value of k is received?

  1. Mathematica then evaluates <expression2>, which is B[k] = <RHS>, and says, "I will now immediately evaluate <RHS> and assign the result to B[k]." It is this second assignment which achieves the memorisation.
$\endgroup$
  • 1
    $\begingroup$ Good point: I overlooked/ \did not stress this! $\endgroup$ – N0va Nov 24 '20 at 14:14
  • $\begingroup$ This was really nice. My graduate advisor from years ago showed this to me (5-6 years ago) but i haven't seen him in a while and I couldn't remember how the memorization worked. This was a nice clear up. $\endgroup$ – Eleven-Eleven Nov 24 '20 at 14:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.