# Infinite sums with factorials **URL:** \ **Category:** Factual Questions\ **Created:** [September 12, 2016, 5:52am UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744 "2016-09-12T05:52:30Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![Kimble](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/kimble/32/19185_2.png) [@Kimble](https://boards.straightdope.com/u/Kimble)\ **Post date:** [September 12, 2016, 5:52am UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744/1 "2016-09-12T05:52:30Z")
So, I was doing 538’s puzzle of the week ([The Riddler](http://fivethirtyeight.com/features/who-keeps-the-money-you-found-on-the-floor/)) 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: > [@](#): > > You and four statistician colleagues find a $100 bill on the floor of your department’s faculty lounge. None of you have change, so you agree to play a game of chance to divide the money probabilistically. The five of you sit around a table. The game is played in turns. Each turn, one of three things can happen, each with an equal probability: The bill can move one position to the left, one position to the right, or the game ends and the person with the bill in front of him or her wins the game. You have tenure and seniority, so the bill starts in front of you. What are the chances you win the money? > > Extra credit: What if there were N statisticians in the department? 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: > [@](#): > > Part[Inverse[ToeplitzMatrix[Join[PadRight[{3,-1},N-1],{-1}]]],1,1] where N = 5 Change the number at the end to match the number of statisticians; for N = 5, the answer is 5/11. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [September 12, 2016, 6:46am UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744/2 "2016-09-12T06:46:57Z")
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) ---
**Author:** ![Kimble](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/kimble/32/19185_2.png) [@Kimble](https://boards.straightdope.com/u/Kimble)\ **Post date:** [September 12, 2016, 8:05am UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744/3 "2016-09-12T08:05:37Z")
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.) ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [September 12, 2016, 11:18am UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744/4 "2016-09-12T11:18:52Z")
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. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [September 12, 2016, 8:46pm UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744/5 "2016-09-12T20:46:36Z")
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](https://en.wikipedia.org/wiki/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 = ```auto 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 = ```auto 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](https://en.wikipedia.org/wiki/Fibonacci_number#Binet.27s_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](https://oeis.org/A004146)) (b\_n) = 1, 3, 8, 21, 55, … ([the alternate Fibonacci numbers](https://oeis.org/A001906)) ---
**Author:** ![mcgato](https://avatars.discourse-cdn.com/v4/letter/m/ac8455/32.png) [@mcgato](https://boards.straightdope.com/u/mcgato)\ **Post date:** [September 13, 2016, 11:48am UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744/6 "2016-09-13T11:48:36Z")
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. ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [September 13, 2016, 5:35pm UTC](https://boards.straightdope.com/t/infinite-sums-with-factorials/765744/7 "2016-09-13T17:35:50Z")
It’s complex, unfair, and inscrutable. Sounds like academic perfection to me. 🙂