Re: Strange Min/Max result
- To: mathgroup at smc.vnet.net
- Subject: [mg62382] Re: Strange Min/Max result
- From: Maxim <m.r at inbox.ru>
- Date: Tue, 22 Nov 2005 04:42:48 -0500 (EST)
- References: <dlp3ah$1lu$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
On Sun, 20 Nov 2005 05:58:41 +0000 (UTC), <neillclift at msn.com> wrote:
> While playing with a equation for addition chains I wanted to
> manipulate something like this:
>
> n = 2i + Sum[Min[i - j, 2^(d - r + 1 - j)], {j, 0, r - 3}]
>
> Now Mathematica doesn't seem to be able to do much with equations like
> this.
> I had no clue but Mathematica knows much more than me. I happened to be
> flipping
> though The Mathematica Guidebook for Symbolics and saw this being used:
>
> max[x_, y_] := 1/2(x + y + Sqrt[(x - y)^2])
>
> Very smart. So I thought I could do:
>
> min1[x_, y_] := 1/2(x + y - Sqrt[(x - y)^2])
>
> This gives the wrong results though:
>
> n = 2i + Sum[min1[i - j, 2^(d - r + 1 - j)], {j, 0, r - 3}]
>
> n = 2^(2+d-2r)(-4+2^r) + 2i
>
> I can see its wrong with something like this:
>
> n = 2i + Sum[min1[
> i - j, 2^(d - r + 1 - j)], {j,
> 0, r - 3}] /. d -> 8 /. r -> 4 /. i -> 16
> n = 80
>
> The real answer is
> n = 2i + Sum[Min[
> i - j, 2^(d - r + 1 - j)], {j,
> 0, r - 3}] /. d -> 8 /. r -> 4 /. i -> 16
> n = 63
>
> So whats going on here and is there any way to manipulate equations
> with Min and Max in them?
> Thanks.
> Neill.
>
Mathematica applies PowerExpand to the summand here:
In[2]:= Sum[Sqrt[(k - n)^2], {k, 0, n}]
Out[2]= -n*(1 + n)/2
In[3]:= Trace[Sum[Sqrt[(k - n)^2], {k, 0, n}], _PowerExpand,
TraceInternal -> True]
Out[3]= {{{{{{{{{{{{HoldForm[PowerExpand[Sqrt[(K$55 - n)^2]]]}}}}}}}}}}}}
You can evaluate such sums if you rewrite Sqrt[x^2] as Abs[x] and use
PiecewiseSum ( http://library.wolfram.com/infocenter/MathSource/5117/ ):
In[4]:= PiecewiseSum[Abs[k - n], {k, 0, n},
Assumptions -> n ~Element~ Integers]
Out[4]= If[0 < n, (n + n^2)/2, 0]
PiecewiseSum can handle summands involving Min/Max as well:
In[5]:= PiecewiseSum[Min[k, n - k], {k, 0, n},
Assumptions -> n ~Element~ Integers && n > 0] // FullSimplify
Out[5]= (-1 + n)*n/2 + Floor[n/2]*(1 - n + Floor[n/2])
PiecewiseSum cannot evaluate your sum though. The equation i - j == 2^(d -
r + 1 - j) can be solved, but Reduce won't be able to determine which of
the solutions lie within the summation range. So we have to do part of the
work by hand:
In[6]:= Solve[i - j == 2^(d - r + 1 - j), j]
Out[6]= {{j -> i + ProductLog[(-2^(1 + d - i - r))*Log[2]]/Log[2]}}
In[7]:= bp[k_] = j /. %[[1]] /. ProductLog -> (ProductLog[k, #]&);
Only the branches with k = 0 and k = -1 can be real, and only if the
argument of ProductLog is greater or equal to -1/E (and also less than
zero for ProductLog[-1, x], but that condition is satisfied for all values
of the parameters). Further, for large j (i - j) < 2^(d - r + 1 - j).
Therefore, the sum is equal to
In[8]:= 2*i + If @@ {-2^(d - r + 1 - i)*Log[2] < -1/E,
PiecewiseSum[i - j, {j, 0, r - 3}],
PiecewiseSum[If[a <= j <= b, 2^(d - r + 1 - j), i - j],
{j, 0, r - 3}] /. {a -> bp[-1], b -> bp[0]}}
In[9]:= % /. {d -> 8, r -> 4, i -> 16}
Out[9]= 63
In[8] returns a (rather messy) closed form result, which will be correct
for all values of d,r,i, not only integers. So PiecewiseSum still proved
to be useful here -- we didn't have to consider all possible positions of
bp[-1] and bp[0] with respect to the points j = 0 and j = r - 3 separately.
Maxim Rytin
m.r at inbox.ru