<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\usepackage{tikz}
\usepackage{colortbl}
\usetikzlibrary{shapes}
\usetikzlibrary{positioning}
\usetikzlibrary{decorations.markings}
\usetikzlibrary{arrows}
\tikzstyle{subgroup}=[scale=1]

\newcommand{\langl}{\begin{picture}(4.5,7)
\put(1.1,2.5){\rotatebox{60}{\line(1,0){5.5}}}
\put(1.1,2.5){\rotatebox{300}{\line(1,0){5.5}}}
\end{picture}}
\newcommand{\rangl}{\begin{picture}(4.5,7)
\put(.9,2.5){\rotatebox{120}{\line(1,0){5.5}}}
\put(.9,2.5){\rotatebox{240}{\line(1,0){5.5}}}
\end{picture}}

\newcommand{\bracknom}{\genfrac{\langle}{\rangle}{0pt}{}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
A Golden Penney Game
}
\vskip 1cm
Issa Dababneh\\
University of Bridgeport\\
Bridgeport, CT 06604\\
USA \\
\href{essadababneh2@gmail.com}{\tt essadababneh2@gmail.com}\\
\ \\
Mark Elmer\\
SUNY Oswego\\ 
Oswego, NY 13126 \\
USA \\
\href{mark.elmer@oswego.edu}{\tt mark.elmer@oswego.edu}\\
\ \\
Ryan McCulloch\\
Elmira College\\
Elmira, NY 14901\\
USA \\
\href{mailto:rmcculloch@elmira.edu}{\tt rmcculloch@elmira.edu}\\
\end{center}

\vskip .2 in

\begin{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 \textit{Scientific
American} column.  We concern ourselves with just one case of Penney's
game: player I choosing $HHH$ vs.\ player II choosing $HTH$.  If a
trick golden penny is minted to have the probability of heads equal to
$1/\varphi$, where $\varphi$ 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.
\end{abstract}


\section{Motivation}

In 1969, Penney introduced his coin flip game, Penney's game \cite{Pen69}.  Penney's game was publicized by Gardner in 1974 in his \textit{Scientific American} column ``Mathematical Games'' \cite{Gard74}.  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 \cite{Bar12}, Reed \cite{Reed96}, Shuster \cite{Shu06}, 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'' \cite{Cra73}, 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, HTH, HTT, THH, THT, TTH, TTT \}.$$  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 $HTH$.  (It should be noted that this choice of player II is not optimal; the optimal choice would be $THH$.)  The figure below appeared in Craswell's 1973 paper.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}[node distance = 1.8cm, auto]
\tikzset{every loop/.style={min distance=10mm,in=60,out=150,looseness=10}}
\node[draw,circle,minimum size=0.7cm,inner sep=0pt] (A) {$-$};
\node[draw,circle,minimum size=0.7cm,inner sep=0pt, right of=A] (B) {$H$};
\node[draw,circle,minimum size=0.7cm,inner sep=0pt, above right=of B] (C) {$HH$};
\node[draw,circle,minimum size=0.7cm,inner sep=0pt, below right=of B] (D) {$HT$};
\node[draw,circle,minimum size=0.7cm,inner sep=0pt, right=of C] (E) {$HHH$};
\node[draw,circle,minimum size=0.7cm,inner sep=0pt, right=of D] (F) {$HTH$};
\node [label={[xshift=-0.3cm, yshift=1.1cm]T}] {};
\draw [-latex] (A) -- (B) node [midway, above, sloped] (T1) {H};
\draw [-latex] (A) edge[loop below] ();
\draw [-latex] (B) -- (C) node [midway, above, sloped] (T2) {H};
\draw [-latex] (C) -- (E) node [midway, above, sloped] (T3) {H};
\draw [-latex] (B) -- (D) node [midway, above, sloped] (T4) {T};
\draw [-latex] (D) -- (F) node [midway, above, sloped] (T5) {H};
\draw [-latex] (D) -- (A) node [midway, below, sloped] (T6) {T};
\draw [-latex] (C) -- (D) node [midway, above, sloped] (T7) {\rotatebox[origin=c]{270}{T}};
\end{tikzpicture}
\caption{A memory state machine illustrating $HHH$ vs.\ $HTH$ in Penney's game.}
\end{center}
\end{figure}

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}$.
\begin{align*}
P_{HHH} &amp;= 1 \\
P_{HTH} &amp;= 0 \\
P_{HH} &amp;= \frac{1}{2}P_{HHH} + \frac{1}{2}P_{HT} = \frac{1}{2} + \frac{1}{2}P_{HT}.\\
P_{HT} &amp;= \frac{1}{2}P_{HTH} + \frac{1}{2}P_{-} = \frac{1}{2}P_{-}.\\
P_{HH} &amp;= \frac{1}{2} + \frac{1}{4}P_{-}.\\
P_H &amp;= \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_{-} &amp;= \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_{-} &amp;= \frac{2}{5}.
\end{align*}

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.
\begin{align*}
P_{HHH} &amp;= 1 \\
P_{HTH} &amp;= 0\\
P_{HH} &amp;= xP_{HHH} + (1-x)P_{HT} = x + (1-x)P_{HT}.\\
P_{HT} &amp;= xP_{HTH} + (1-x)P_{-} = (1-x)P_{-}.\\ 
P_{HH} &amp;= x + (1-x)^2P_{-}.\\
P_H &amp;= xP_{HH} + (1-x)P_{HT} = x^2 + x(1-x)^2P_{-} + (1-x)^2P_{-} =  x^2 + (1+x)(1-x)^2P_{-}.\\
P_{-} &amp;= (1-x)P_{-} + xP_H = (1-x)P_{-} + x^3 + x(1+x)(1-x)^2P_{-}.\\
P_{-} &amp;= \dfrac{x^3}{1-(1-x)-x(1+x)(1-x)^2} = \dfrac{x^3}{x^2 + x^3 - x^4} = \dfrac{x}{1+x-x^2}.
\end{align*}

\begin{proposition}\label{P1} 
Consider Penney's game of player I choosing $HHH$ vs.\ player II
choosing $HTH$.  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)$.
\end{proposition} 
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/\varphi$, the reciprocal of the golden ratio!
(One should also read Vallin \cite{Val20}, where these derivations were
done using martingales.)

\section{Relationship to board tilings}

An $n$-board is a board of size $n \times 1$ composed of $1 \times 1$ cells.  We tile an $n$-board with two types of tiles, a square, which is a $1 \times 1$ tile, and a fence, which is a tile composed of two subtiles (called posts) of size $1 \times 1$ separated by a gap of size $1 \times 1$.  A tiling of a board that consists of $n$ tiles is known as an $n$-tiling.
\begin{table}[H]
\centering
\renewcommand{\arraystretch}{1.4}
\begin{tabular}{|c|c|c|c|c|}
\hline
$S$ &amp; $S$ &amp; \cellcolor[HTML]{C0C0C0}$F$ &amp; $S$ &amp; \cellcolor[HTML]{C0C0C0}\,\,\,\,\\
\hline
\end{tabular}


\begin{tabular}{|c|c|c|c|}
\hline
$S$ &amp; $S$ &amp; $S$ &amp; $S$ \\
\hline
\end{tabular}


\begin{tabular}{|c|c|c|c|c|c|}
\hline
$S$ &amp; $S$ &amp; \cellcolor[HTML]{C0C0C0}$F$ &amp; \cellcolor[HTML]{656565}\color[HTML]{FFFFFF}$F$ &amp; \cellcolor[HTML]{C0C0C0}\,\,\,\, &amp; \cellcolor[HTML]{656565}\color[HTML]{FFFFFF}\,\,\,\, \\
\hline
\end{tabular}
\caption{Examples of tilings by squares and fences.}
\end{table}
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 $FS$ in the first example, is known as a filled fence and the square inside is called a captured square.  An interlocking of fences, like $FF$ in the third example, is known as a bifence.  A square that is not captured is called a free square.

Define $\bracknom{n}{k}$ to be the number of $n$-tilings that contain exactly $k$ fences.  By convention, $\bracknom{0}{0} = 1$.

\begin{proposition}\label{P2}
Consider Penney's game of player I choosing $HHH$ vs.\ player II choosing $HTH$.  The number of winning player I sequences of the form $(a_1a_2\cdots a_rHHH)$ that have exactly $n$ number of tails and exactly $k$ number of heads in $(a_1\cdots a_r)$ is equal to $\bracknom{n}{k}$.
\end{proposition}

\begin{proof}
Let $s = (a_1\cdots 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 $HTH$ 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 $HTH$ 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.
\end{proof}

\begin{corollary}\label{C3}
Consider Penney's game of player I choosing $HHH$ vs.\ player II choosing $HTH$.  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 \sum_{n=0}^{\infty} \sum_{k=0}^{n} \bracknom{n}{k} x^k (1-x)^n.$$
\end{corollary}
Combining Proposition~\ref{P1} and Corollary~\ref{C3}, we evaluate an infinite series:
\begin{theorem}\label{T4}
For each real number $x \in (0,1)$, we have $$ \sum_{n=0}^{\infty} \sum_{k=0}^{n} \bracknom{n}{k} x^k (1-x)^n = \dfrac{1}{x^2 + x^3 - x^4}.$$ 
\end{theorem}
The analogue to Theorem~\ref{T4} using the binomial coefficients is a simple geometric series.

Note that
$$\sum_{k=0}^{n} \binom{n}{k} x^k (1-x)^n = (1-x)^n  \sum_{k=0}^{n} \binom{n}{k} x^k = (1-x)^n (1+x)^n = (1-x^2)^n.$$
Thus,
$$\sum_{n=0}^{\infty} \sum_{k=0}^{n} {{n}\choose{k}} x^k (1-x)^n = \sum_{n=0}^{\infty} (1-x^2)^n = \frac{1}{1-(1-x^2)} = \frac{1}{x^2}$$
if and only if $|1-x^2| &lt; 1$, i.e., if and only if $x \in (-\sqrt{2}, 0) \cup (0, \sqrt{2})$.

The binomial coefficients, \seqnum{A007318}, satisfy the following recursive definition:
\begin{enumerate}

\item $\binom{n}{0} = 1$ for all $n \geq 0$.

\item $\binom{n}{n} = 1$ for all $n \geq 0$.

\item $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ for all $n &gt; k \geq 1$.
\end{enumerate}

In \cite{EdAl20}, it was proven combinatorially that the $\bracknom{n}{k}$ integers satisfy a similar recursive definition:
\begin{enumerate}

\item $\bracknom{n}{0}  = 1$ for all $n \geq 0$.  \cite[Identity 15]{EdAl20}

\item $\bracknom{n}{n}  = 1$ for all even $n \geq 0$.  \cite[Identity 17]{EdAl20}

\item $\bracknom{n}{n}  = 0$ for all odd $n &gt; 0$.  \cite[Identity 17]{EdAl20}

\item $\bracknom{n}{k}  = \bracknom{n-1}{k-1}  + \bracknom{n-1}{k}$  for all $n &gt; k \geq 1$.  \cite[Identity 25]{EdAl20}
\end{enumerate}
Note that the recursive definition for $\bracknom{n}{k} $ differs from $\binom{n}{k}$ only in one of the initial conditions. 

We display the first few rows of integers $\bracknom{n}{k}$ in a triangle similar to Pascal's triangle:
\begin{table}[H]
\resizebox{\textwidth}{!}{
\begin{tabular}{rccccccccccccccccccccccc}
$n=0$:&amp;    &amp;    &amp;    &amp;  &amp; &amp; &amp;   &amp;  &amp; &amp; &amp; 1\\\noalign{\smallskip\smallskip}
$n=1$:&amp;    &amp;    &amp;    &amp;  &amp; &amp; &amp;   &amp; &amp; &amp;1 &amp;    &amp;  0\\\noalign{\smallskip\smallskip}
$n=2$:&amp;    &amp;    &amp;    &amp;  &amp; &amp; &amp;   &amp; &amp;1 &amp;    &amp; 1 &amp;    &amp;  1\\\noalign{\smallskip\smallskip}
$n=3$:&amp;    &amp;    &amp;    &amp;     &amp; &amp; &amp;&amp;   1 &amp;    &amp;  2 &amp;    &amp;  2 &amp;    &amp;  0\\\noalign{\smallskip\smallskip}
$n=4$:&amp;    &amp;    &amp;    &amp;  &amp; &amp; &amp;1 &amp;    &amp;  3 &amp;    &amp;  4 &amp;    &amp;  2 &amp;    &amp;  1\\\noalign{\smallskip\smallskip}
$n=5$:&amp;    &amp;    &amp;  &amp; &amp; &amp;1 &amp;    &amp;  4 &amp;    &amp; 7 &amp;    &amp; 6  &amp;    &amp; 3 &amp;    &amp;  0\\\noalign{\smallskip\smallskip}
$n=6$:&amp;    &amp; &amp; &amp; &amp;1 &amp;    &amp; 5 &amp;   &amp; 11   &amp;  &amp;  13  &amp;   &amp; 9   &amp;  &amp;   3 &amp;     &amp; 1\\\noalign{\smallskip\smallskip}
$n=7$:&amp; &amp; &amp; &amp; 1 &amp;    &amp;  6 &amp;    &amp;  16 &amp;    &amp;  24 &amp;    &amp;  22 &amp;    &amp; 12 &amp;    &amp;  4 &amp;    &amp; 0\\\noalign{\smallskip\smallskip}
$n=8$:&amp; &amp; &amp; 1 &amp; &amp; 7 &amp; &amp; 22 &amp; &amp; 40 &amp; &amp; 46 &amp; &amp; 34 &amp; &amp; 16 &amp;    &amp;  4 &amp;    &amp; 1\\\noalign{\smallskip\smallskip}
$n=9$:&amp; &amp; 1 &amp; &amp; 8 &amp; &amp; 29 &amp; &amp; 62 &amp; &amp; 86 &amp; &amp; 80 &amp; &amp; 50 &amp;    &amp;  20 &amp;    &amp;  5 &amp;    &amp; 0\\\noalign{\smallskip\smallskip}
$n=10$:&amp; 1 &amp; &amp; 9 &amp; &amp; 37 &amp; &amp; 91 &amp; &amp; 148 &amp; &amp; 166 &amp; &amp; 130 &amp;    &amp;  70 &amp;    &amp;  25 &amp;    &amp;  5 &amp;    &amp; 1\\\noalign{\smallskip\smallskip}
\end{tabular}
}
\caption{A Pascal-like triangle.}
\end{table}

The $\bracknom{n}{k}$ integer sequence is \seqnum{A059259}.

\section{Identities involving $\bracknom{n}{k}$}

A few of the identities in this section overlap with those derived in \cite{EdAl20}, and we indicate those as such.  Our proofs differ from the combinatorial proofs in \cite{EdAl20}.  Many of the identities in this section appear to be novel.  
\begin{proposition}\label{P5}
For each $n \geq 0$, we have
$$\bracknom{n}{k} = \sum_{i=0}^{k}( -1)^i {{n-i} \choose {k-i}}.$$
\end{proposition}

\begin{proof} Let $$f(n,k) = \sum_{i=0}^{k}( -1)^i {{n-i} \choose {k-i}} = \sum_{i=0}^{k}\frac{(-1)^i(n-i)!}{(k-i)!(n-k)!}.$$ 
We show that $f(n,k)$ satisfies the recursive definition
\begin{enumerate}

\item $f(n,0) = 1$ for all $n \geq 0$.

\item $f(n,n) = 1$ for all even $n \geq 0$.

\item $f(n,n) = 0$ for all odd $n &gt; 0$.

\item $f(n,k) = f(n-1,k-1) + f(n-1,k)$ for all $n &gt; k \geq 1$.

\end{enumerate}

Conditions (1), (2), and (3) are straight-forward to verify.
To see condition (4), note that for $n &gt; k \geq 1$, we have
\begin{align*}
f(n-1,k-1) &amp; + f(n-1,k) \\
&amp; = \sum_{i=0}^{k-1}\frac{(-1)^i(n-i-1)!}{(k-i-1)!(n-k)!} + \left(\sum_{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)!}\right) \\
&amp;=  \left(\sum_{i=0}^{k-1}\left(\frac{(-1)^i(n-i-1)!}{(k-i-1)!(n-k)!} \cdot \frac{k-i}{k-i} + \frac{(-1)^i(n-i-1)!}{(k-i)!(n-k-1)!}\cdot \frac{n-k}{n-k}\right)\right)+(-1)^k\\
&amp;=  \sum_{i=0}^{k}\frac{(-1)^i(n-i)!}{(k-i)!(n-k)!} = f(n,k).
\end{align*}
Thus, $f(n,k) = \bracknom{n}{k}$.
\end{proof}

\begin{corollary}[{\cite[Identity 24]{EdAl20}}]\label{C6}
For each $n \geq k &gt; 0$, we have
$$\binom{n}{k}  = \bracknom{n-1}{k-1} + \bracknom{n}{k}.$$
\end{corollary}

\begin{proof}
By Proposition~\ref{P5}, we have $$\bracknom{n-1}{k-1} + \bracknom{n}{k} = \sum_{i=0}^{k}( -1)^i {{n-i-1} \choose {k-i-1}} + \sum_{i=0}^{k}( -1)^i {{n-i} \choose {k-i}} = \binom{n}{k}.$$
\end{proof}

The Vandermonde identity, attributed to Vandermonde but known to Chinese mathematicians as far back as the   14\textsuperscript{th} century, states that for fixed $r$ one has the identity $$ \binom{n}{k} = \sum_{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.  
\begin{corollary}\label{C7}
For each $n \geq k \geq 0$, we have
$$\bracknom{n}{k}  = \sum_{i=0}^{k} \binom{n-k}{k-i} \bracknom{k}{i} = \sum_{i=0}^{k} \bracknom{n-k}{k-i} \binom{k}{i}.$$
\end{corollary}

\begin{proof}
By Proposition~\ref{P5}, we have $$ \sum_{i=0}^{k} \binom{n-k}{k-i} \bracknom{k}{i} = \sum_{i=0}^{k} \binom{n-k}{k-i} \left( \sum_{j=0}^{i} (-1)^j \binom{k-j}{i-j} \right).$$

By distributing and rearranging, we have $$ \sum_{i=0}^{k} \binom{n-k}{k-i} \left( \sum_{j=0}^{i} (-1)^j \binom{k-j}{i-j} \right) = \sum_{j=0}^{k} (-1)^j \left( \sum_{i=0}^{k-j} \binom{n-j - (k-j)}{k-j-i} \binom{k-j}{i} \right).$$

By Vandermonde's identity, we have $$ \sum_{j=0}^{k} (-1)^j \left( \sum_{i=0}^{k-j} \binom{n-j - (k-j)}{k-j-i} \binom{k-j}{i} \right) = \sum_{j=0}^{k} (-1)^j \binom{n-j}{k-j}.$$

By Proposition~\ref{P5}, we have $$ \sum_{j=0}^{k} (-1)^j \binom{n-j}{k-j} = \bracknom{n}{k}.$$  

Hence, we have that $$ \bracknom{n}{k}  = \sum_{i=0}^{k} \binom{n-k}{k-i} \bracknom{k}{i}.$$  

The proof that $$ \bracknom{n}{k}  = \sum_{i=0}^{k} \bracknom{n-k}{k-i} \binom{k}{i}$$ is similar.
\end{proof}

\begin{lemma}\label{L8}
For each $m &gt; 0$ and $k \geq 0$, we have
$$\sum_{i=0}^{k} \binom{m+i}{k-i} \binom{k-i}{i} = \sum_{i=0}^{k} \binom{m+i-1}{k-i} \binom{k-i+1}{i}.$$
\end{lemma}

\begin{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 &gt; 0$.

Suppose $k &gt; 0$.  By twice factoring out common terms and applying Pascal's identity we obtain 
$$\sum_{i=0}^{k} \binom{m+i}{k-i} \binom{k-i}{i} - \sum_{i=0}^{k-1} \binom{m+i-1}{k-i-1} \binom{k-i}{i} + \sum_{i=0}^{k-1} \binom{m+i}{k-i-1} \binom{k-i-1}{i}$$

$$ = \sum_{i=0}^{k} \binom{m+i-1}{k-i} \binom{k-i+1}{i}.$$

By induction, we have $$ \sum_{i=0}^{k-1} \binom{m+i}{k-i-1} \binom{k-i-1}{i} = \sum_{i=0}^{k-1} \binom{m+i-1}{k-i-1} \binom{k-i}{i},$$ and the result follows.
\end{proof}

We obtain a Vandermonde analogue for the $\bracknom{n}{k}$ integers.

\begin{proposition}[{\cite[Identity 22]{EdAl20}}]\label{P9}
For each $n \geq k \geq 0$, we have
$$\bracknom{n}{k} = \sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} \binom{n-k+i}{k-i} \binom{k-i}{i}.$$
\end{proposition}

\begin{proof}
We apply the same proof strategy as in Proposition~\ref{P5}: to show that the formula satisfies the recursive definition for the $\bracknom{n}{k}$ integers.

Conditions (1), (2), and (3) are straight-forward to verify (for
conditions (2) and (3), note that $i &lt; k-i$ when $i &lt; \dfrac{k}{2}$).
In regard to condition (4), suppose that $n &gt; k \geq 1$, and note that by factoring out common terms and applying Pascal's identity we obtain
$$\sum_{i=0}^{\lfloor \frac{k-1}{2} \rfloor} \binom{n-k+i}{k-i-1} \binom{k-i-1}{i} + \sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} \binom{n-k+i-1}{k-i} \binom{k-i}{i} = \sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} \binom{n-k+i-1}{k-i} \binom{k-i+1}{i}.$$

Applying Lemma~\ref{L8} with $m= n-k$, and noting that $i &gt; k-i$ when $i &gt; \dfrac{k}{2}$, we obtain
$$\sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} \binom{n-k+i-1}{k-i} \binom{k-i+1}{i} = \sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} \binom{n-k+i}{k-i} \binom{k-i}{i}$$
and this completes the proof.
\end{proof}

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

\begin{proposition}\label{P10}
Let $n \geq 0$ be an integer and let $f(x) = \dfrac{1}{(1+x)(1-x)^{n+1}}$.  Then $\displaystyle \sum_{k=0}^{\infty} \bracknom{n+k}{k} x^k$ is the Maclaurin series expansion for $f(x)$.
\end{proposition}

\begin{proposition}\label{P11}
Let $b$ be any real number and let $g(x) = \dfrac{x}{1-bx-(b+1)x^2}$.  Then $\displaystyle \sum_{n=0}^{\infty} \sum_{k=0}^{n} \bracknom{n}{k} b^{n-k} x^{n+1}$ is the Maclaurin series expansion for $g(x)$.
\end{proposition}

Polynomials of the form $\sum_{k=0}^{n} \bracknom{n}{k} x^k$ can be regrouped as polynomials over $x+x^2$.
\begin{table}[H]
\begin{center}
\begin{tabular}{| l |l |}
\hline
  $n$ &amp; $\sum_{k=0}^{n} \bracknom{n}{k} x^k$ \\
\hline
 0 &amp; 1 \\
 1 &amp; 1 \\
 2 &amp; $1 + (x + x^2)$ \\
 3 &amp; $1 + 2(x + x^2)$ \\
 4 &amp; $1 + 3(x+x^2) + (x+x^2)^2$ \\
 5 &amp; $1 + 4(x+x^2) + 3(x+x^2)^2$ \\
 6 &amp;$ 1 + 5(x+x^2) + 6(x+x^2)^2 + (x+x^2)^3$ \\
 7 &amp; $1  +6(x+x^2) + 10(x+x^2)^2 + 4(x+x^2)^3$ \\
 8 &amp; $1 + 7(x+x^2) + 15(x+x^2)^2 + 10(x+x^2)^3 + (x+x^2)^4$ \\
 9 &amp; $1 + 8(x+x^2) + 21(x+x^2)^2 + 20(x+x^2)^3 + 5(x+x^2)^4$ \\
 10 &amp; $1 + 9(x+x^2) + 28(x+x^2)^2 + 35(x+x^2)^3 + 15(x+x^2)^4 + (x+x^2)^5$ \\
 \hline
\end{tabular}
\end{center}
\caption{A regrouping of $\sum_{k=0}^{n} \bracknom{n}{k} x^k$.}
\end{table}
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, \seqnum{A000045}. 
\begin{table}[H]
\centering
\resizebox{2in}{!}{%
   \begin{tabular}{| l |l | l |}
\hline
  $n$ &amp; $\displaystyle \sum_{k=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor } \binom{n-k}{k}$ &amp; $F_{n+1}$ \\
\hline
 0 &amp; 1 &amp; 1\\
 1 &amp; 1 &amp; 1 \\
 2 &amp; $1 + 1$ &amp; 2 \\
 3 &amp; $1 + 2$ &amp; 3 \\
 4 &amp; $1 + 3 + 1$ &amp; 5 \\
 5 &amp; $1 + 4 + 3$ &amp; 8 \\
 6 &amp;$ 1 + 5 + 6 + 1$ &amp; 13 \\
 7 &amp; $1  +6 + 10 + 4$ &amp; 21 \\
 8 &amp; $1 + 7 + 15 + 10 + 1$ &amp; 34 \\
 9 &amp; $1 + 8 + 21 + 20 + 5$ &amp; 55 \\
 10 &amp; $1 + 9 + 28 + 35 + 15 +1$ &amp; 89 \\
 \hline
\end{tabular}%
}
\caption{Some sums of diagonals in Pascal's triangle.}
\end{table}

\begin{proposition}\label{P12}
For each $n \geq 0$,  we have $$\sum_{k=0}^{n} \bracknom{n}{k} x^k = \sum_{k=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor } \binom{n-k}{k} (x+x^2)^k.$$
\end{proposition}

\begin{proof}
We have $$\sum_{k=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor } \binom{n-k}{k} (x+x^2)^k = \sum_{k=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor } \sum_{i=0}^{k} \binom{n-k}{k} \binom{k}{i} x^{k+i} = \sum_{k=0}^{n} \sum_{i=0}^{\left \lfloor{\frac{k}{2}}\right \rfloor }  \binom{n-k+i}{k-i} \binom{k-i}{i} x^{k}.$$

By Proposition~\ref{P9} we have $$ \bracknom{n}{k} = \sum_{i=0}^{\left \lfloor{\frac{k}{2}}\right \rfloor }  \binom{n-k+i}{k-i} \binom{k-i}{i}.$$ 
\end{proof}

Let $\varphi = (1 + \sqrt{5})/2$ be the golden ratio.  Note that $x+x^2 = 1$ when $x = -\varphi$ or $x = 1/\varphi$.  
\begin{corollary}\label{C13}
For each $n \geq 0$,  we have $$\sum_{k=0}^{n} (-1)^k \bracknom{n}{k} {\varphi}^k = \sum_{k=0}^{n} \frac{\bracknom{n}{k}}{ {\varphi}^k} = F_{n+1}.$$
\end{corollary}

Using the identity $\displaystyle \sum_{k=0}^n \binom{n}{k} \, \, x^{n-k} y^{k} = (x+y)^n$ with $x=1$ and $y=1$ we obtain
\begin{proposition}\label{P14}
For each $n \geq 0$, $$ \sum_{k=0}^n \binom{n}{k} = 2^n.$$
\end{proposition}

The Jacobsthal sequence, \seqnum{A001045}, is defined recursively as $J_0 = 0$, $J_1 = 1$, and $J_n = J_{n-1} + 2J_{n-2}$ for $n &gt; 1$.  Note that the powers of two, \seqnum{A000079}, satisfy $2^0 = 1$, $2^1 = 2$, and $2^n = 2^{n-1} + 2\cdot2^{n-2}$ for $n &gt; 1$.  And so the powers of two and the Jacobsthal numbers have a similar recursive definition aside from the initial conditions.  
\begin{proposition}[{\cite[Theorem 6]{EdAl20}}]\label{P15}
For each $n \geq 0$, we have $$ \sum_{k=0}^n \bracknom{n}{k} = J_{n+1}.$$
\end{proposition}

We leave it to the reader to prove Proposition~\ref{P15}.

Using Proposition~\ref{P12} with $x=1$ we obtain
\begin{corollary}\label{C16}
For each $n \geq 0$, we have $$ \sum_{k=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor } \binom{n-k}{k} \,\, 2^k = J_{n+1}.$$
\end{corollary}

Using the identity $\displaystyle \sum_{k=0}^n \binom{n}{k} \, \, x^{n-k} y^{k} = (x+y)^n$ with $x=1$ and $y=-1$ we obtain
\begin{proposition}\label{P17}
For each $n \geq 1$, we have $$ \sum_{k=0}^n (-1)^k \,\, \binom{n}{k} = 0.$$
\end{proposition}

Using Proposition~\ref{P12} with $x=-1$ we obtain
\begin{proposition}\label{P18}
For each $n \geq 0$, we have $$ \sum_{k=0}^n (-1)^k \, \bracknom{n}{k} = 1.$$
\end{proposition}

We quote the well-known result
\begin{proposition}\label{P19}
For each $n \geq 0$, we have $$ \sum_{k=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor } \binom{n-k}{k} = F_{n+1}.$$
\end{proposition}

We leave it to the reader to prove the following analogue to $\bracknom{n}{k}$:
\begin{proposition}\label{P20}
For each $n \geq 0$, we have $$ \sum_{k=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor } \bracknom{n-k}{k} = \big( F_{\left \lceil{\frac{n+1}{2}}\right \rceil} \big)\big( F_{\left \lceil{\frac{n+2}{2}}\right \rceil} \big).$$
\end{proposition}

The relevant sequence in Proposition~\ref{P20} is \seqnum{A006498}, of
which the even terms are the golden rectangle numbers (the product of
two successive Fibonacci numbers), \seqnum{A001654}, and the odd terms
are the squared Fibonacci numbers, \seqnum{A007598}.  This was proven
combinatorially in \cite{EdAl20}.  It is interesting to note that in
\cite{EdAl20}, 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.

\begin{thebibliography}{9}
\providecommand{\url}[1]{\texttt{#1}}
\providecommand{\urlprefix}{URL }

\bibitem{Bar12}
C.~Barratt and P.~M. Schwartz, Analysis of the Penney-ante game using difference equations: development of an optimal and a mixed-strategies protocol, \emph{J. Math. Res.} \textbf{4} (2012),
  1--11.

\bibitem{Cra73}
K.~J. Craswell, An interesting penny game,
  \emph{Coll. Math. J.} \textbf{4} (1973), 18--25.

\bibitem{EdAl20}
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, \emph{J. Integer Seq.} \textbf{24} (2021), \href{https://cs.uwaterloo.ca/journals/JIS/VOL24/Allen/edwards2.html}{Article 21.3.8}.

\bibitem{Gard74}
M.~Gardner, Mathematical games: on the paradoxical situations that arise from nontransitive relations, \emph{Sci. Am.} \textbf{231} (1974),
  120--125.

\bibitem{Pen69}
W.~Penney, Problem 95: {P}enney-{A}nte, \emph{J. Recreat. Math.} \textbf{2}
  (1969), 241.

\bibitem{Reed96}
R.~J. Reed, An intransitive example of a Markov chain,
  \emph{Math. Gaz.} \textbf{80} (1996), 411--416.

\bibitem{Shu06}
J.~J. Shuster, Using a two-player coin game paradox in the classroom, \emph{Am. Stat.}
  \textbf{60} (2006), 68--70.

\bibitem{Val20}
R.~W. Vallin, Making the unfair fair, \emph{Recreat. Math. Mag.}
  \textbf{7} (2020), 9--26.

\end{thebibliography}

\bigskip
\hrule
\bigskip


\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A10; Secondary 11B65, 11B39.

\noindent \emph{Keywords: } 
Penney's game, Penney ante, golden ratio, Fibonacci sequence, binomial coefficient, Pascal's triangle, $n$-tiling, combinatorial identity.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 18 2020;
revised version received May 15 2021; May 16 2021.
Published in {\it Journal of Integer Sequences}, May 17 2021.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
</pre></body></html>