A and B play a game in which they alternate calling out positive integers less than or equal to n, according to the following rules:

- A goes first and always calls out an odd number.
- B always calls out an even number.
- Each player must call out a number which is greater than the previous number. (Except for A's first turn.)
- The game ends when one player cannot call out a number.

Some example games (for n = 8):

- 1, 8
- 3, 4, 5, 8
- 1, 2, 3, 4, 5, 6, 7, 8

The length of a game is defined as the number of numbers called out. For example, the game 1, 8, above, has length 2.

- How many different possible games are there?
- How many different possible games of length k are there?

Let g(n) denote the number of different games with upper bound n. If n = 1, there is only one game: 1. Similarly for n = 2, where the only game is: 1, 2. Hence g(1) = g(2) = 1. For n > 2, we establish a recurrence relation for g(n) by considering the following mutually exclusive cases, which encompass all possibilities:

- A's first move is 1.

Then B has the same number of games as would A were the upper bound equal to n − 1. (Calling out numbers from the range 2...n − 1, beginning with an even number, is equivalent to calling out numbers from the range 1...n, beginning with an odd number.)

Hence there are g(n − 1) possible games in this case. - A's first move is greater than or equal to 3.

This is equivalent to the upper bound being equal to n − 2.

Hence there are g(n − 2) possible games in this case.

Putting these two cases together, we conclude that g(n) = g(n − 1) + g(n − 2).

This is simply the Fibonacci sequence, which is defined by the recurrence equation F_{1} = 1, F_{2} = 1, F_{k} = F_{k−1} + F_{k−2}, for k > 2.

Hence g(n) = F_{n}.

A closed form formula for the Fibonacci sequence is F_{n} = (Phi^{n} − phi^{n}) /,

where Phi = (1 + )/2 and phi = (1 − )/2 are the roots of the quadratic equation x^{2} − x − 1 = 0.

Therefore, the number of different possible games is F_{n} = (Phi^{n} − phi^{n}) /.

Consider the sequence (game) of length k: 1 a_{1} < a_{2} < ... < a_{k} = n, where k and n necessarily have the same parity. (Both are odd or both are even.)

Since the kth number is fixed we may regard this as a sequence of k − 1 elements bounded by n − 1:

1 a_{1} < a_{2} < ... < a_{k−1} n − 1.

Let b_{i} = a_{i} − i + 1.

Then 1 b_{1} b_{2} ... b_{k−1} (n − 1) − (k − 1) + 1 = n − k + 1 is a sequence in which each element is odd.

Further, given each b_{i} we can recover a_{i}. (a_{i} = b_{i} + i − 1.)

So the number of games is equal to the number of ways of choosing k − 1 odd numbers from the odd numbers in the set {1, 3, ... , n − k + 1}, disregarding order and allowing repetition.

This set contains m = [½(n − k + 2)] = ½(n − k) + 1 elements, where [x] is the greatest integer less than or equal to x. (Recall that k and n have the same parity, so ½(n − k) is always an integer.)

The number of such ways of choosing the k − 1 odd numbers from the m-element set is known as a multichoose coefficient, and may be represented in terms of a binomial coefficient by means of the following argument.

Think of the m-element set as defining m − 1 dividing lines around which the k − 1 numbers must be distributed. For instance, if m = 4 and k − 1 = 5, one possible distribution is **|*||**, which corresponds to the sequence 1, 1, 3, 7, 7. The total number of such distributions is by definition given by the binomial coefficient .

Then we have m + k − 2 = ½(n − k) + 1 + k − 2 = ½(n + k) − 1.

Therefore, the number of possible games of length k is given by , where k must have the same parity as n.

Source: Inspired by Steven and Todd