|
We have:
(*) V(A,B) = [ V(A-1,B) + V(A, B-1) ] / 2
V(A,0) = A; V(0,B) = 0
for all positive integers: A,B.
I will conduct the demonstration in enough detail so that a reader can anticipate how a somewhat more general problem can be solved.
In order to produce a closed form expression for V(A,B), we have to repeatedly apply (*) until V(A,B) is expressed as a sum of terms, each including a factor of V with one null argument. V(A,B) can thus be expressed in the form
V(A,B) = ∑ cL V(L,0) + ∑ nM V(0,M)
where the sums go from 1 ≤ L ≤ A and 1 ≤ M ≤ B
In our case V(0,M) = 0, so we can ignore the terms in nM. We need a formula for calculating the cL. For this purpose I found it very helpful to refer to a Cartesian coordinate system with gridlines connecting lattice points. Start off with each lattice point indexed to 0, except for the point (A,B), which is indexed to 1. When we actuate (*) we introduce new terms corresponding to the lattice points (A-1,B) and (A,B-1). We record this outcome by incrementing the index of lattice points to the left and beneath (A,B). On the next iteration we increment each of the points to the left or beneath of either of the two previously actuated points. This results in (A-2,B) and (A,B-2) each sharing an index value of 1, while (A-1,B-1) is assigned an index of 2.
Continuing in this way, we see that the index at any lattice point (L,M) equals the number of direct routes connecting (L,M) with (A,B). (Note: each direct route consist of unit length horizontal and vertical segments consistently decreasing the distance to the destination). Observe that to ground (A,B) by connecting it to a point (L,0) we have to move first to (L,1), as (L,1) is the sole entrance point for landing on (L,0) without first transitting through another grounding point on the abscissa. A direct route between (L,1) and (A,B) entails partitioning (A-L)+(B-1) steps into A-L horizontal segments and B-1 vertical segments.
Another way to picture this, which will certainly be easier for some people, is to reflect that the diagonal of M+1 lattice points included by joining the points (A-M,B) with (A,B-M) are indexed sequentially with the binomial coeficients of (x+y)M.
Thus, we have
V(A,B) = ∑ L (A-L+B-1)! / [ 2A-L+B-1 (A-L)! (B-1)! ]
where L goes from 1 to A. Note that in addition to accounting for the number of direct routes, the expression accounts for the factor of 1/2
introduced each time we take a step from (A,B) toward (L,0). We have
V(A+1,A+1) = ∑ L (2A-L+1)! / [ 22A-L+1 (A+1-L)! (A)! ]
Writing K=A-L+1 we put this in the alternative form
V(A+1,A+1) = ∑ (A-K+1) (K+A)! / [K! A! 22A+2-L] summed from K=0 to L
= (A+1) 2-A-1 [hA - fA/2] where
hA ≡ ∑ (A+K)! / [K! A! 2K] summed from K=0 to A and fL ≡ ∑ (A+K)! / [(K-1)! (A+1)! 2K-1
summed from K=1 to A.
The expression for hA is a well known series expansion of 2A (you can readily reach this result by induction), and fA is easily expressible in terms of hA+1:
hA+1 = fA + (2A+1)!/[A! (A+1)! 2A] + (2A+2)!/[A!2 2A+1]
= fA + (2A+1)!/[A! (A+1)! 2A-1] = 2A+1 So that:
V(A+1,A+1) = (A+1) 2-A-1 [2A - 2A + (2A+1)!/[A! (A+1)! 2A-2]
= (2A+1)! / [A!2 22A+1] as desired.
Note:
This problem is the outcome of continuing work on the unresolved problem: Pick a card, any card.
|
