Find a recurrence relation that gives a formula for the number of arrangements of wins and losses for aN (you stop playing at 3 losses in a row).

Question

Problem

Since it’s a wise idea to have a stopping condition when gambling, a gambler decides to play a game until they lose three times in a row. Let W and L denote wins and losses respectively, and let aN denote the number of arrangements of wins and losses over N games. Here are the possibilities for the arrangements of wins and losses for the first values of aN:

a3 = 1 (LLL)

a4 = 1 (WLLL)

a5 = 2 (WWLLL, LWLLL)

a6 = 4 (WWWLLL, WLWLLL, LWWLLL, LLWLLL)

etc…

Bearing in mind that any sequence of N games must start with the arrangement W, LW, or LLW, find a recurrence relation that gives a formula for the number of arrangements of wins and losses for aN.

Solution

So, I know that for N > 3, the arrangement of wins and losses must end with WLLL.

There are two arrangements of 5 games (WWLLL, LWLLL), four arrangements of 6 games (WWWLLL, WLWLLL, LWWLLL, LLWLLL), seven arrangements of 7 games, thirteen arrangements of 8 games, and 24 arrangements of 9 games. I am trying to find a pattern based on the total number of arrangements of wins and losses minus the arrangements with three L's in a row. I have: 2^(N-4) arrangements for N > 3 (subtract 4 from N because you will always end with WLLL), but am having difficulty finding the number of arrangements with 3 L's.

Any ideas?

Thank you

Answer 1

Building from what lulu wrote in the comments, we have: $$ a_N=a_{N-1}+a_{N-2}+a_{N-3} $$ so you simply add the three previous figures. The reason is as lulu stated:

• Good strings of length $N$ starting with $W$ can be formed from good strings of length $N-1$ by prepending $W$.
• Good strings of length $N$ starting with $LW$ can be formed from good string of length $N-2$ by prepending $LW$.
• Good string of length $N$ starting with $LLW$ can be formed from good strings of length $N-3$ by prepending $LLW$.

That's all. Thanks to lulu.