Can I use Mathematica to simplify this recursive function definition
- To: mathgroup at smc.vnet.net
- Subject: [mg131117] Can I use Mathematica to simplify this recursive function definition
- From: nathan at icecreambreakfast.com
- Date: Wed, 12 Jun 2013 05:39:52 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- Delivered-to: l-mathgroup@wolfram.com
- Delivered-to: mathgroup-outx@smc.vnet.net
- Delivered-to: mathgroup-newsendx@smc.vnet.net
Here's my recursive function with its terminating conditions:
d[n_, 0, a_] := 1
d[n_, 1, a_ ] := n - a + 1
d[n_, k_, a_ ] :=
Sum[ Binomial[ k, j ] d[Floor[n/( m^j)], k - j,
m + 1 ], {j, 1, k}, {m, a, n^(1/k)}]
And what I'm interested in is explicit / non-recursive expressions for d[n,2,2], d[n,3,2], d[n,4,2], d[n,5,2], d[n,6,2], and so on for positive integer values of k > 1, with "a" always 2. Is there a way to make Mathematica give me that?
If I type "d[n,2,2]" or "d[n,3,2]" into Mathematica, I immediately get a stack overflow, so that's no help.
If I manually work through the recursion for d[n,2,2] by hand and do a fair bit of simplifying, I am eventually left with
1 - Floor[ n^(1/2)]^2 + 2 Sum [ Floor[ n/m], {m, 2, Floor[n^(1/2)]}]
And if I manually work through d[n,3,2] by hand (and do a huge amount of simplifying - it's a pain to do), I arrive at
-1 + Floor[ n^(1/3)]^3 +
3 Sum[ Floor[ n/(m^2)] - Floor[ Floor[n/m]^(1/2)]^2 +
2 Sum[ Floor[Floor[n/m]/j], {j, m + 1,
Floor[Floor[n/m]^(1/2)]}], {m, 2, Floor[n^(1/3)]}]
So that's the sort of output I'm looking for. I'd like to be able to get expressions like that for integers k between 2 and, say, 10 (the number of terms is 2^k, so there are limits here).
If it's any help, d is a recursive definition of one generalization of the Dirichlet hyperbola method - in fact, d[n,2,1] computes D(x), the sum at the heart of the Dirichlet Divisor problem. But I'm interested in counting divisors that exclude 1, hence "a" set to 2 in the function definition.
Thanks!