Infinite sums with factorials

Factual Questions
1

So, I was doing 538’s puzzle of the week (The Riddler) and came up with a nasty (to me, anyway) infinite sum as part of my answer:

Σ [k=0 to inf] [sub]2k[/sub]C[sub]k[/sub]/3[sup]2k+1[/sup]

I have no idea how to solve that. Googling didn’t help – I found answers for 1/[sub]2n[/sub]C[sub]n[/sub] and a few other sums with factorials scattered about, but nothing that seemed useful to me. Wolfram Alpha gave me an answer, 1/√5, but there doesn’t seem to be an option for a step-by-step calculation (which I couldn’t use anyway because I’m not a Pro subscriber).

Now that the deadline for submitting solutions has passed, I thought I’d ask if any of you had ideas or suggestions for solving that sum. Here’s the question, if you’re curious but don’t want to go to a new page to read it:

I got 1/√5 as the limit as N approaches infinity; I have a lovely “answer” for N>2 that you can plug into Wolfram Alpha:

Change the number at the end to match the number of statisticians; for N = 5, the answer is 5/11.

2

Are you familiar with generating functions? The generating function for the central binomial coefficients is:

1/sqrt(1 - 4x) = Σ [k=0 to inf] [sub]2k[/sub]C[sub]k[/sub] x^k

By substituting x/9 for x and dividing everything by 3 we get:

1/sqrt(9 - 4x) = Σ [k=0 to inf] [sub]2k[/sub]C[sub]k[/sub]/3[sup]2k+1[/sup] x^k

If we let x = 1 we get:

1/sqrt(5) = Σ [k=0 to inf] [sub]2k[/sub]C[sub]k[/sub]/3[sup]2k+1[/sup]

There’s some tricky algebra in the middle step, but it is just algebra.

Here’s my solution:

p(n) = (1/sqrt(5)) * (((3 + sqrt(5))/2)^n - ((3 - sqrt(5))/2)^n) / (((3 + sqrt(5))/2)^n + ((3 - sqrt(5))/2)^n - 2)

3

Thanks for the reply!

I wasn’t familiar with generating functions; after reading a few webpages about them, I sort of see what they do, but not so well that I could actually do anything interesting with them. It turns out that I had found your first equation while searching, but I didn’t recognize it as the key to the solution. (Also, I hadn’t messed with infinite sums in a while, so I wasn’t quite sure how to manipulate them.) I think I get the required algebra in the middle step, but it’s the kind of thing that I’d mess up while doing just from lack of practice.

I’m impressed by your solution. (I’m almost as impressed by your typing it out properly!) Is it derived from solving a system of equations along the lines of W[sub]1[/sub] = (1 + W[sub]2[/sub] + W[sub]n[/sub])/3 and W[sub]k[/sub] = (0 + W[sub]k-1[/sub] + W[sub]k+1[/sub])/3, where W[sub]k[/sub] is the probability of you (in chair 1) winning when the bill is in front of chair k? If there’s anything interesting about how you made it and it wouldn’t be too much of a typing exercise, I’d be interested in hearing it; if not, I have no problem waiting for the official answer in 4 days, which is generally explained well.

(If it wasn’t clear, my “answer” generates and inverts the matrix of coefficients of the aforementioned SoE. Since the matrix of constants is simply (1 0 0 … 0)[sup]τ[/sup], the answer is just the element at row 1, column 1 of the inverted matrix.)

4

Interesting answers. I played around with a few test cases for this problem and found that the probabilities for each person were related to the Fibonacci numbers (when n is odd) and the Lucas numbers (when n is even). But I couldn’t formalize or prove it. The fact that √5 is involved in the infinite limit probably has to do with the fact that the ratios of consecutive numbers in both sequences approach (1 + √5)/2 (the golden ratio) as the sequences go to infinity.

5

I too used the matrix representation of a system of equations and recognized that the answer I was looking for was the value in the upper left corner of the inverse of that matrix. Since I only needed one element of the inverse, I did not invert the whole matrix I used properties adjugate matrix to calculate the value I desired directly. In this case I just needed the determinant of the 1,1 minor divided by the determinant of the whole matrix.

Let’s look at the case for n = 4.

Let A =


 3 -1  0 -1
-1  3 -1  0
 0 -1  3 -1
-1  0 -1  3

Let B be the 1,1 minor of A =


 3 -1  0
-1  3 -1
 0 -1  3

We get det(B) = 21 and det(A) = 45 so the probability of winning the game with four players is 21/45 = 7/15.

Now we can define A_n to be the appropriate matrix for the n case and define B_n similarly. Furthermore define sequences a_n and b_n to bet det(A_n) and det(B_n) respectively.

From the structure of the matrices, we can determine linear recurrences for the sequences a_n and b_n and we can manually determine the first few terms.

a_n = 4 a_{n-a} - 4 a_{n-2} + a_{n-3}
b_n = 3 b_{n-1} - b_{n-2}

When we have a linear recurrence and seed values we can derive explicit formulas. I won’t go into details here but look for a derivation of Binet’s Formula to get the idea.

a_n = (((3 + sqrt(5))/2)^n + ((3 - sqrt(5))/2)^n - 2)
b_n = (1/sqrt(5)) * (((3 + sqrt(5))/2)^n - ((3 - sqrt(5))/2)^n)

From here you can get my formula for p_n = b_n / a_n.

Interestingly…

(a_n) = 1, 5, 16, 45, 121, … (the alternate Lucas numbers - 2)

(b_n) = 1, 3, 8, 21, 55, … (the alternate Fibonacci numbers)

6

It doesn’t say much for the statistics faculty at that school if the other four statisticians thought that was a good way to decide who gets the $100.

7

It’s complex, unfair, and inscrutable. Sounds like academic perfection to me. :slight_smile: