- #1

- 112

- 1

[tex]

A_n = _{2n}C_n - \sum_{k=1}^{n-1} _{2n-2k}C_{n-k}A_k

[/tex]

where [tex]_{r}C_s[/tex] is the binomial coefficient 'r choose s'.

Starting with A_1 = 2, the pattern of A_n's continued 2, 4, 10, 28, 84, 264, etc. I didn't see a pattern in the numbers themselves, but eventually I thought about looking at the fraction of the total number of sequences of length 2n with n 1's and n 0's, and was surprised to see that

[tex]f_1 = \frac{A_1} { _{2} C_1} = 1[/tex]

[tex]f_2 = \frac{A_2} { _{4} C_2} = 1/3[/tex]

[tex]f_3 = \frac{A_3} { _{6} C_3} = 1/5[/tex]

[tex]f_4 = \frac{A_4} { _{8} C_4} = 1/7[/tex]

.....

[tex]f_n = \frac{A_n}{_{2n} C_n} = 1/(2n-1)

[/tex]

So my first question is....is this somehow obvious? With such a simple result, there must be some way to just 'see' the answer. If not, how might I go about showing that last formula to be generally true? What led me to consider the fraction rather than the absolute number of sequences was using the inclusion-exclusion formula for probabilities of disjunctions of events and considering all sequences with n 1's and n 0's to be equally likely. But that method took much more work than the recurrence relation method, which is already a lot to do by hand. I ran into this problem while trying to analyze what roulette players call the 'D'Alembert' betting system. I doubt the mathematician is responsible for it, but whatever...it sounds impressive. The idea is that, on even payout bets, you raise the bet one unit after each loss, and lower it one unit after each win. Hopefully *fingers crossed*, you will have a sequence of n wins and n losses before running out of money or encountering the min and max bets. If you succeed in this you will have gained n units. And then you start over. In the roulette manual I looked at, the author explained that this is a winning strategy, but only if you use 'good judgment'. That is, you have to know when your luck is about to run out.