A Golden Penney Game

Issa Dababneh University of Bridgeport Bridgeport, CT 06604 USA

                     essadababneh2@gmail.com

Mark Elmer SUNY Oswego Oswego, NY 13126 USA

                      mark.elmer@oswego.edu

Ryan McCulloch Elmira College Elmira, NY 14901 USA

                      rmcculloch@elmira.edu

Abstract

Penney’s game (also known as Penney ante) is a counter-intuitive coin flip game that has attracted much attention due to Gardner’s Scientific American column. We concern ourselves with just one case of Penney’s game: player I choosing HHH vs. player II choosing HT H. If a trick golden penny is minted to have the probability of heads equal to 1/φ, where φ is the golden ratio, then neither player has an advantage in this game.

We discover that counting the number of winning player I sequences in this game that have exactly n number of tails and k number of heads appearing before the final HHH is equivalent to counting the n-tilings of a board using exactly k fences. We derive combinatorial identities related to this counting formula, all of which are fascinating and many of which appear to be new. Some of the sequences that we encounter along the way are Pascal’s triangle and a related Pascal-like triangle, the Fibonacci sequence, the Jacobsthal sequence, the golden rectangle numbers, the squared Fibonacci numbers, and more.

1 Motivation

In 1969, Penney introduced his coin flip game, Penney’s game [5]. Penney’s game was publicized by Gardner in 1974 in his Scientific American column “Mathematical Games” [4]. Since then, numerous articles have been written on the paradoxical nature of this coin flip game and on winning strategies for the game, see, for example, the papers of Barratt and Schwartz [1], Reed [6], Shuster [7], and there are many others.

The focus of this paper will be different, in that the entirety of this paper will be concerned with just one case of Penney’s game and in the interesting combinatorial relationships that arise from that one case.

Craswell’s 1973 paper, “An Interesting Penny Game” [2], concerned Penney’s game. We focus on what Craswell called the “three-face game”. This is a two player game, in which first player I selects one of the eight possible sequences of three coin flips,

{HHH, HHT, HT H, HT T, T HH, T HT, T T H, T T T }.

Then player II selects one of the eight options. A coin is flipped repeatedly, and the winner is the player whose sequence appears first. No matter what player I chooses, player II can choose an outcome so that the odds of winning are in the favor of player II. This is what makes Penney’s game counter-intuitive.

Craswell worked out the winning probabilities for the different cases of this game, assuming a fair coin. He introduced a memory state machine for finding winning probabilities. The memory state machine is dependent upon the initial choices of the players. The memory changes states in accordance with outcomes that will lead to a win for either of the players. The entirety of this paper will focus on the specific game of player I choosing HHH vs. player II choosing HT H. (It should be noted that this choice of player II is not optimal; the optimal choice would be T HH.) The figure below appeared in Craswell’s 1973 paper.

− H HH HT HHH HT H T H H H T H T T

Figure 1: A memory state machine illustrating HHH vs. HT H in Penney’s game.

Let P_{S} denote the probability that player I eventually wins, given that the current state of the memory is state S. Note that if state S leads to states S_{1} and S_{2}, then P_{S} = \frac{1}{2}P_{S_{1}} + \frac{1}{2}P_{S_{2}}.

P_{HHH} = 1
P_{HT H} = 0
P_{HH} = \frac{1}{2}P_{HHH} + \frac{1}{2}P_{HT} = \frac{1}{2} + \frac{1}{2}P_{HT} .
P_{HT} = \frac{1}{2}P_{HT H} + \frac{1}{2}P_{−} = \frac{1}{2}P_{−}.
P_{HH} = \frac{1}{2} + \frac{1}{4}P_{−}.
P_{H} = \frac{1}{2}P_{HH} + \frac{1}{2}P_{HT} = \frac{1}{4} + \frac{1}{8}P_{−} + \frac{1}{4}P_{−} = \frac{1}{4} + \frac{3}{8}P_{−}.
P_{−} = \frac{1}{2}P_{−} + \frac{1}{2}P_{H} = \frac{1}{2}P_{−} + \frac{1}{8} + \frac{3}{16}P_{−} = \frac{1}{8} + \frac{11}{16}P_{−}.
P_{−} = \frac{2}{5}.

Thus, the probability that player I wins this game is 0.4.

Suppose that the coin is not necessarily fair, and that the probability of heads is x and the probability of tails is 1 − x. Let us use Craswell’s memory state machine to determine the probability that player I wins the game.

P_{HHH} = 1
P_{HT H} = 0
P_{HH} = xP_{HHH} + (1 − x)P_{HT} = x + (1 − x)P_{HT} .
P_{HT} = xP_{HT H} + (1 − x)P_{−} = (1 − x)P_{−}.
P_{HH} = x + (1 − x)^{2}P_{−}.
P_{H} = xP_{HH} + (1 − x)P_{HT} = x^{2} + x(1 − x)^{2}P_{−} + (1 − x)^{2}P_{−} = x^{2} + (1 + x)(1 − x)^{2}P_{−}.
P_{−} = (1 − x)P_{−} + xP_{H} = (1 − x)P_{−} + x^{3} + x(1 + x)(1 − x)^{2}P_{−}.
P_{−} = \frac{x^{3}}{1 − (1 − x) − x(1 + x)(1 − x)^{2}} = \frac{x^{3}}{x^{2} + x^{3} − x^{4}} = \frac{x}{1 + x − x^{2}} .

Proposition 1. Consider Penney’s game of player I choosing HHH vs. player II choosing HT H. Let x denote the probability of heads and let 1 − x denote the probability of tails. The probability that player I wins is x/(1 + x − x^{2}).

Which coin probability will give a fair game for both players in this game? By setting x/(1 + x − x^{2}) = 1/2, we see that x = 1/φ, the reciprocal of the golden ratio! (One should also read Vallin [8], where these derivations were done using martingales.)

2 Relationship to board tilings

An n-board is a board of size n × 1 composed of 1 × 1 cells. We tile an n-board with two types of tiles, a square, which is a 1 × 1 tile, and a fence, which is a tile composed of two subtiles (called posts) of size 1 × 1 separated by a gap of size 1 × 1. A tiling of a board that consists of n tiles is known as an n-tiling.

S S F S

S S S S

S S F F

Table 1: Examples of tilings by squares and fences.

The first example above shows a 4-tiling of a 5-board using three squares and one fence. The second example shows a 4-tiling of a 4-board using four squares, and the third example shows a 4-tiling of a 6-board using two squares and two fences.

A fence with a square inside, like F S in the first example, is known as a filled fence and the square inside is called a captured square. An interlocking of fences, like F F in the third example, is known as a bifence. A square that is not captured is called a free square.

Define \left⟨{n \atop k}\right⟩ to be the number of n-tilings that contain exactly k fences. By convention, \left⟨{0 \atop 0}\right⟩ = 1.

Proposition 2. Consider Penney’s game of player I choosing HHH vs. player II choosing HT H. The number of winning player I sequences of the form (a_{1}a_{2} ⋯ a_{r}HHH) that have exactly n number of tails and exactly k number of heads in (a_{1} ⋯ a_{r}) is equal to \left⟨{n \atop k}\right⟩.

Proof. Let s = (a_{1} ⋯ a_{r}). We explain how tails in s correspond to tiles, and how heads in s indicate the tiles that are fences. Note that if some a_{i} = H and a_{i+1} = H are in s, then since HHH and HT H cannot appear in s, we have that a_{i+2} = T and a_{i+3} = T. And so a_{i+2}a_{i+3} corresponds to a bifence. And if some a_{i} = H in s with a_{i−1} and a_{i+1} not equal to H, then since HT H cannot appear in s, we have a_{i+1} = T and a_{i+2} = T. And so a_{i+1} corresponds to a fence that is filled with the captured square corresponding to a_{i+2}. All other tails in s correspond to free squares.

Corollary 3. Consider Penney’s game of player I choosing HHH vs. player II choosing HT H. Let x denote the probability of heads and let 1 − x denote the probability of tails. The probability that player I wins is

x^{3} ∑_{n=0}^{∞} ∑_{k=0}^{n} \left⟨{n \atop k}\right⟩x^{k}(1 − x)^{n}.

Combining Proposition 1 and Corollary 3, we evaluate an infinite series:

Theorem 4. For each real number x ∈ (0, 1), we have

∑_{n=0}^{∞} ∑_{k=0}^{n} \left⟨{n \atop k}\right⟩x^{k}(1 − x)^{n} = \frac{1}{x^{2} + x^{3} − x^{4}} .

The analogue to Theorem 4 using the binomial coefficients is a simple geometric series. Note that

∑_{k=0}^{n} \binom{n}{k}x^{k}(1 − x)^{n} = (1 − x)^{n} ∑_{k=0}^{n} \binom{n}{k}x^{k} = (1 − x)^{n}(1 + x)^{n} = (1 − x^{2})^{n}.

Thus,

∑_{n=0}^{∞} ∑_{k=0}^{n} \binom{n}{k}x^{k}(1 − x)^{n} = ∑_{n=0}^{∞}(1 − x^{2})^{n} = \frac{1}{1 − (1 − x^{2})} = \frac{1}{x^{2}}

if and only if |1 − x^{2}| < 1, i.e., if and only if x ∈ (−\sqrt{2}, 0) ∪ (0, \sqrt{2}).

The binomial coefficients, \underline{A007318}, satisfy the following recursive definition:

1. \binom{n}{0} = 1 for all n ≥ 0.

2. \binom{n}{n} = 1 for all n ≥ 0.

3. \binom{n}{k} = \binom{n−1}{k−1} + \binom{n−1}{k} for all n > k ≥ 1. In [3], it was proven combinatorially that the \left⟨{n \atop k}\right⟩ integers satisfy a similar recursive

definition:

1. \left⟨{n \atop 0}\right⟩ = 1 for all n ≥ 0. [3, Identity 15]

2. \left⟨{n \atop n}\right⟩ = 1 for all even n ≥ 0. [3, Identity 17]

3. \left⟨{n \atop n}\right⟩ = 0 for all odd n > 0. [3, Identity 17]

4. \left⟨{n \atop k}\right⟩ = \left⟨{n−1 \atop k−1}\right⟩ + \left⟨{n−1 \atop k}\right⟩ for all n > k ≥ 1. [3, Identity 25] Note that the recursive definition for \left⟨{n \atop k}\right⟩ differs from \binom{n}{k} only in one of the initial conditions.

We display the first few rows of integers \left⟨{n \atop k}\right⟩ in a triangle similar to Pascal’s triangle:

n = 0:  1
n = 1:  1  0
n = 2:  1  1  1
n = 3:  1  2  2  0
n = 4:  1  3  4  2  1
n = 5:  1  4  7  6  3  0
n = 6:  1  5  11  13  9  3  1
n = 7:  1  6  16  24  22  12  4  0
n = 8:  1  7  22  40  46  34  16  4  1
n = 9:  1  8  29  62  86  80  50  20  5  0
n = 10: 1  9  37  91  148  166  130  70  25  5  1

Table 2: A Pascal-like triangle.

The \left⟨{n \atop k}\right⟩ integer sequence is \underline{A059259}.

3 Identities involving \left⟨{n \atop k}\right⟩

A few of the identities in this section overlap with those derived in [3], and we indicate those as such. Our proofs differ from the combinatorial proofs in [3]. Many of the identities in this section appear to be novel. Proposition 5. For each n ≥ 0, we have

\left⟨{n \atop k}\right⟩ = ∑_{i=0}^{k}(−1)^{i}\binom{n − i}{k − i}.

Proof. Let

f(n, k) = ∑_{i=0}^{k}(−1)^{i}\binom{n − i}{k − i} = ∑_{i=0}^{k} \frac{(−1)^{i}(n − i)!}{(k − i)!(n − k)!}.

We show that f(n, k) satisfies the recursive definition 1. f(n, 0) = 1 for all n ≥ 0.

2. f(n, n) = 1 for all even n ≥ 0.

3. f(n, n) = 0 for all odd n > 0.

4. f(n, k) = f(n − 1, k − 1) + f(n − 1, k) for all n > k ≥ 1.

Conditions (1), (2), and (3) are straight-forward to verify. To see condition (4), note that for n > k ≥ 1, we have

f(n − 1, k − 1) + f(n − 1, k)

= ∑_{i=0}^{k−1} \frac{(−1)^{i}(n − i − 1)!}{(k − i − 1)!(n − k)!} + (∑_{i=0}^{k−1} \frac{(−1)^{i}(n − i − 1)!}{(k − i)!(n − k − 1)!} + \frac{(−1)^{k}(n − k − 1)!}{(0)!(n − k − 1)!})

= (∑_{i=0}^{k−1} (\frac{(−1)^{i}(n − i − 1)!}{(k − i − 1)!(n − k)!} · \frac{k − i}{k − i} + \frac{(−1)^{i}(n − i − 1)!}{(k − i)!(n − k − 1)!} · \frac{n − k}{n − k} )) + (−1)^{k}

= ∑_{i=0}^{k} \frac{(−1)^{i}(n − i)!}{(k − i)!(n − k)!} = f(n, k).

Thus, f(n, k) = \left⟨{n \atop k}\right⟩.

Corollary 6 ([3, Identity 24]). For each n ≥ k > 0, we have

\binom{n}{k} = \left⟨{n − 1 \atop k − 1}\right⟩ + \left⟨{n \atop k}\right⟩.

Proof. By Proposition 5, we have

\left⟨{n − 1 \atop k − 1}\right⟩ + \left⟨{n \atop k}\right⟩ = ∑_{i=0}^{k}(−1)^{i}\binom{n − i − 1}{k − i − 1} + ∑_{i=0}^{k}(−1)^{i}\binom{n − i}{k − i} = \binom{n}{k}.

The Vandermonde identity, attributed to Vandermonde but known to Chinese mathematicians as far back as the 14^{th} century, states that for fixed r one has the identity

\binom{n}{k} = ∑_{i=0}^{k} \binom{n − r}{k − i}\binom{r}{i}.

A combinatorial proof of the identity can be found by partitioning a group of objects of size n into two groups of size n − r and r, and by considering the ways of choosing k objects out of this group.

Corollary 7. For each n ≥ k ≥ 0, we have

\left⟨{n \atop k}\right⟩ = ∑_{i=0}^{k} \binom{n − k}{k − i}\left⟨{k \atop i}\right⟩ = ∑_{i=0}^{k} \left⟨{n − k \atop k − i}\right⟩\binom{k}{i}.

Proof. By Proposition 5, we have

∑_{i=0}^{k} \binom{n − k}{k − i}\left⟨{k \atop i}\right⟩ = ∑_{i=0}^{k} \binom{n − k}{k − i} (∑_{j=0}^{i}(−1)^{j}\binom{k − j}{i − j}) .

By distributing and rearranging, we have

∑_{i=0}^{k} \binom{n − k}{k − i} (∑_{j=0}^{i}(−1)^{j}\binom{k − j}{i − j}) = ∑_{j=0}^{k}(−1)^{j} (∑_{i=0}^{k−j} \binom{n − j − (k − j)}{k − j − i}\binom{k − j}{i}) .

By Vandermonde’s identity, we have

∑_{j=0}^{k}(−1)^{j} (∑_{i=0}^{k−j} \binom{n − j − (k − j)}{k − j − i}\binom{k − j}{i}) = ∑_{j=0}^{k}(−1)^{j}\binom{n − j}{k − j}.

By Proposition 5, we have

∑_{j=0}^{k}(−1)^{j}\binom{n − j}{k − j} = \left⟨{n \atop k}\right⟩.

Hence, we have that

\left⟨{n \atop k}\right⟩ = ∑_{i=0}^{k} \binom{n − k}{k − i}\left⟨{k \atop i}\right⟩.

The proof that

\left⟨{n \atop k}\right⟩ = ∑_{i=0}^{k} \left⟨{n − k \atop k − i}\right⟩\binom{k}{i}

is similar. Lemma 8. For each m > 0 and k ≥ 0, we have

∑_{i=0}^{k} \binom{m + i}{k − i}\binom{k − i}{i} = ∑_{i=0}^{k} \binom{m + i − 1}{k − i}\binom{k − i + 1}{i}.

Proof. The proof is by induction on k. When k = 0 we have that

\binom{m}{0}\binom{0}{0} = \binom{m − 1}{0}\binom{1}{0} = 1,

since m > 0.

Suppose k > 0. By twice factoring out common terms and applying Pascal’s identity we obtain

∑_{i=0}^{k} \binom{m + i}{k − i}\binom{k − i}{i} − ∑_{i=0}^{k−1} \binom{m + i − 1}{k − i − 1}\binom{k − i}{i} + ∑_{i=0}^{k−1} \binom{m + i}{k − i − 1}\binom{k − i − 1}{i}

= ∑_{i=0}^{k} \binom{m + i − 1}{k − i}\binom{k − i + 1}{i}.

By induction, we have

∑_{i=0}^{k−1} \binom{m + i}{k − i − 1}\binom{k − i − 1}{i} = ∑_{i=0}^{k−1} \binom{m + i − 1}{k − i − 1}\binom{k − i}{i},

and the result follows.

We obtain a Vandermonde analogue for the \left⟨{n \atop k}\right⟩ integers.

Proposition 9 ([3, Identity 22]). For each n ≥ k ≥ 0, we have

\left⟨{n \atop k}\right⟩ = ∑_{i=0}^{⌊ \frac{k}{2} ⌋} \binom{n − k + i}{k − i}\binom{k − i}{i}.

Proof. We apply the same proof strategy as in Proposition 5: to show that the formula satisfies the recursive definition for the \left⟨{n \atop k}\right⟩ integers.

Conditions (1), (2), and (3) are straight-forward to verify (for conditions (2) and (3),

note that i < k − i when i < \frac{k}{2}). In regard to condition (4), suppose that n > k ≥ 1, and note that by factoring out common terms and applying Pascal’s identity we obtain

∑_{i=0}^{⌊ \frac{k−1}{2} ⌋} \binom{n − k + i}{k − i − 1}\binom{k − i − 1}{i}+∑_{i=0}^{⌊ \frac{k}{2} ⌋} \binom{n − k + i − 1}{k − i}\binom{k − i}{i} = ∑_{i=0}^{⌊ \frac{k}{2} ⌋} \binom{n − k + i − 1}{k − i}\binom{k − i + 1}{i}.

Applying Lemma 8 with m = n − k, and noting that i > k − i when i > \frac{k}{2}, we obtain

∑_{i=0}^{⌊ \frac{k}{2} ⌋} \binom{n − k + i − 1}{k − i}\binom{k − i + 1}{i} = ∑_{i=0}^{⌊ \frac{k}{2} ⌋} \binom{n − k + i}{k − i}\binom{k − i}{i}

and this completes the proof.

The \left⟨{n \atop k}\right⟩ integers appear as coefficients in the Maclaurin series expansions for certain functions. Proofs are left to the reader.

Proposition 10. Let n ≥ 0 be an integer and let f(x) = \frac{1}{(1 + x)(1 − x)^{n+1}} . Then ∑_{k=0}^{∞} \left⟨{n + k \atop k}\right⟩x^{k}

is the Maclaurin series expansion for f(x).

Proposition 11. Let b be any real number and let g(x) = \frac{x}{1 − bx − (b + 1)x^{2}} . Then

∑_{n=0}^{∞} ∑_{k=0}^{n} \left⟨{n \atop k}\right⟩b^{n−k}x^{n+1} is the Maclaurin series expansion for g(x).

Polynomials of the form ∑_{k=0}^{n} \left⟨{n \atop k}\right⟩x^{k} can be regrouped as polynomials over x + x^{2}.

\begin{matrix}n & ∑_{k=0}^{n} \left⟨{n \atop k}\right⟩x^{k} \\ 0 & 1 \\ 1 & 1 \\ 2 & 1 + (x + x^{2}) \\ 3 & 1 + 2(x + x^{2}) \\ 4 & 1 + 3(x + x^{2}) + (x + x^{2})^{2} \\ 5 & 1 + 4(x + x^{2}) + 3(x + x^{2})^{2} \\ 6 & 1 + 5(x + x^{2}) + 6(x + x^{2})^{2} + (x + x^{2})^{3} \\ 7 & 1 + 6(x + x^{2}) + 10(x + x^{2})^{2} + 4(x + x^{2})^{3} \\ 8 & 1 + 7(x + x^{2}) + 15(x + x^{2})^{2} + 10(x + x^{2})^{3} + (x + x^{2})^{4} \\ 9 & 1 + 8(x + x^{2}) + 21(x + x^{2})^{2} + 20(x + x^{2})^{3} + 5(x + x^{2})^{4} \\ 10 & 1 + 9(x + x^{2}) + 28(x + x^{2})^{2} + 35(x + x^{2})^{3} + 15(x + x^{2})^{4} + (x + x^{2})^{5} \end{matrix}

Table 3: A regrouping of ∑_{k=0}^{n} \left⟨{n \atop k}\right⟩x^{k}.

The coefficients over (x+x^{2}) are the diagonals in Pascal’s triangle from the bottom left to the top right. It is well known that the sums of these numbers give the Fibonacci sequence, \underline{A000045}.

\begin{matrix}n & \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − k}{k} & F_{n+1} \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 2 & 1 + 1 & 2 \\ 3 & 1 + 2 & 3 \\ 4 & 1 + 3 + 1 & 5 \\ 5 & 1 + 4 + 3 & 8 \\ 6 & 1 + 5 + 6 + 1 & 13 \\ 7 & 1 + 6 + 10 + 4 & 21 \\ 8 & 1 + 7 + 15 + 10 + 1 & 34 \\ 9 & 1 + 8 + 21 + 20 + 5 & 55 \\ 10 & 1 + 9 + 28 + 35 + 15 + 1 & 89 \end{matrix}

Table 4: Some sums of diagonals in Pascal’s triangle.

Proposition 12. For each n ≥ 0, we have

∑_{k=0}^{n} \left⟨{n \atop k}\right⟩x^{k} = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − k}{k}(x + x^{2})^{k}.

Proof. We have

\begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − k}{k}(x + x^{2})^{k} = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} ∑_{i=0}^{k} \binom{n − k}{k}\binom{k}{i}x^{k+i} = ∑_{k=0}^{n} \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − k + i}{k − i}\binom{k − i}{i}x^{k}.

By Proposition 9 we have

\left⟨{n \atop k}\right⟩ = \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − k + i}{k − i}\binom{k − i}{i}.

Let φ = (1 + \sqrt{5})/2 be the golden ratio. Note that x + x^{2} = 1 when x = −φ or x = 1/φ.

Corollary 13. For each n ≥ 0, we have

∑_{k=0}^{n}(−1)^{k}\left⟨{n \atop k}\right⟩φ^{k} = ∑_{k=0}^{n} \frac{\left⟨{n \atop k}\right⟩}{φ^{k}} = F_{n+1}.

Using the identity ∑_{k=0}^{n} \binom{n}{k} x^{n−k}y^{k} = (x + y)^{n} with x = 1 and y = 1 we obtain

Proposition 14. For each n ≥ 0,

∑_{k=0}^{n} \binom{n}{k} = 2^{n}.

The Jacobsthal sequence, \underline{A001045}, is defined recursively as J_{0} = 0, J_{1} = 1, and J_{n} = J_{n−1} + 2J_{n−2} for n > 1. Note that the powers of two, \underline{A000079}, satisfy 2^{0} = 1, 2^{1} = 2, and 2^{n} = 2^{n−1} + 2 · 2^{n−2} for n > 1. And so the powers of two and the Jacobsthal numbers have a similar recursive definition aside from the initial conditions.

Proposition 15 ([3, Theorem 6]). For each n ≥ 0, we have

∑_{k=0}^{n} \left⟨{n \atop k}\right⟩ = J_{n+1}.

We leave it to the reader to prove Proposition 15.

Using Proposition 12 with x = 1 we obtain

Corollary 16. For each n ≥ 0, we have

\begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − k}{k} 2^{k} = J_{n+1}.

Using the identity ∑_{k=0}^{n} \binom{n}{k} x^{n−k}y^{k} = (x + y)^{n} with x = 1 and y = −1 we obtain

Proposition 17. For each n ≥ 1, we have

∑_{k=0}^{n}(−1)^{k} \binom{n}{k} = 0.

Using Proposition 12 with x = −1 we obtain

Proposition 18. For each n ≥ 0, we have

∑_{k=0}^{n}(−1)^{k} \left⟨{n \atop k}\right⟩ = 1.

We quote the well-known result

Proposition 19. For each n ≥ 0, we have

\begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − k}{k} = F_{n+1}.

We leave it to the reader to prove the following analogue to \left⟨{n \atop k}\right⟩:

Proposition 20. For each n ≥ 0, we have

\begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \left⟨{n − k \atop k}\right⟩ = (F⌈_{\frac{n+1}{2}}⌉)(F⌈_{\frac{n+2}{2}}⌉).

The relevant sequence in Proposition 20 is \underline{A006498}, of which the even terms are the golden rectangle numbers (the product of two successive Fibonacci numbers), \underline{A001654}, and the odd terms are the squared Fibonacci numbers, \underline{A007598}. This was proven combinatorially in [3]. It is interesting to note that in [3], the identity was derived in regards to the number of tilings of an n-board that contain exactly k fences. Here we have an analogous identity for the number of n-tilings that contain exactly k fences.

References

[1] C. Barratt and P. M. Schwartz, Analysis of the Penney-ante game using difference equations: development of an optimal and a mixed-strategies protocol, J. Math. Res. 4 (2012), 1–11.

[2] K. J. Craswell, An interesting penny game, Coll. Math. J. 4 (1973), 18–25.

[3] K. Edwards and M. A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Integer Seq. 24 (2021), Article 21.3.8.

[4] M. Gardner, Mathematical games: on the paradoxical situations that arise from nontransitive relations, Sci. Am. 231 (1974), 120–125.

[5] W. Penney, Problem 95: Penney-Ante, J. Recreat. Math. 2 (1969), 241.

[6] R. J. Reed, An intransitive example of a Markov chain, Math. Gaz. 80 (1996), 411–416.

[7] J. J. Shuster, Using a two-player coin game paradox in the classroom, Am. Stat. 60 (2006), 68–70.

[8] R. W. Vallin, Making the unfair fair, Recreat. Math. Mag. 7 (2020), 9–26.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11B65, 11B39. Keywords: Penney’s game, Penney ante, golden ratio, Fibonacci sequence, binomial coefficient, Pascal’s triangle, n-tiling, combinatorial identity.

(Concerned with sequences \underline{A000045}, \underline{A000079}, \underline{A001045}, \underline{A001654}, \underline{A006498}, \underline{A007318}, \underline{A007598}, and \underline{A059259}.)

Received December 18 2020; revised version received May 15 2021; May 16 2021. Published in Journal of Integer Sequences, May 17 2021.

Return to Journal of Integer Sequences home page.