Hi,
First I want to apologize as this question is out of the far left field. I
will attempt to describe what I was working on before jumping into the
maxima problem incase I made a mistake which I keep overlooking.
I found two formulas which I believe to be identical and numerically they
appear to be identical, though I derived them differently. The thing I was
analyzing was the number of nodes expanded by the IDA* algorithm. It works
in an iterative deepening fashion. Assuming a constant branching factor b
we have the following tree:
1 node from the root
b nodes from the next layer
b^2 nodes from the next layer
b^n nodes at the depth of n.
The total number of nodes expanded is then
the tree at height 1 +
the tree at height 2 +
the tree at height 3 + ...
the tree at height k
assume(k>=0, b>1)
So one can arrive at the following in one of two ways:
alt1: sum( (k+1-i)*b^(i), i, 1, k), simpsum;
alt2: radcan( sum(sum(b^k,k,1,i),i,1,k) ),simpsum;
alt1 is simply b^k + 2*b^(k-1) + 3*b^(k-2) + ... b*k (we don't count the
root). Clearly the nodes from the tree at height one is summed as many
times as the tree is deep, so k times. The next level on the tree is summed
k-1 times, but as b^2 nodes. That is where alt1 comes from.
The first summation in alt2 calculates the total nodes in the tree (not
counting the root). The second summation sums over various sized trees.
Logically, these two seem the same to me. Numerically these two appear the
same over what I've tested. However, I cannot find a way to make Maxima
simplify alt1 into the closed form expression generated by alt2.
Thus, I am asking something along the lines of "How do I make Maxima
simplify alt1 into alt2's non-summation form?"