\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}{\underline{#1}}} \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} \newtheorem{depolignac*}[theorem]{DePolignac's Formula} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On Properties of the General Bow Sequence} \vskip 1cm Melissa Dennison\\ Department of Mathematics\\ Baldwin Wallace University\\ Berea, OH 44017\\ USA \\ \href{mailto:mdenniso@bw.edu}{\tt mdenniso@bw.edu} \\ \end{center} \begin{abstract} In this paper, we define and study a two-parameter family of recursive sequences, which we call the {\it bow sequences}. The general bow sequence is defined similarly to the Stern sequence, and many of the properties of the bow sequences are related to known properties of the Stern sequence. In particular, we focus on common divisors of consecutive terms, maximum values, sums of terms, and generating functions. \end{abstract} \section{Introduction} In 1858, Stern \cite{stern} studied the so-called ``diatomic'' array of integers, which was motivated by a function studied by Eisenstein. The diatomic array can be completely understood by consideration of the Stern sequence \seqnum{A002487}. The Stern sequence is defined as follows: \begin{align} s(0) & = 0, \quad s(1) = 1; \\ s(2n) & = s(n), \quad \text{for } n \geq 1; \label{evenstern} \\ s(2n+1) & = s(n)+s(n+1), \quad \text{for } n \geq 1. \end{align} The terms in the Stern sequence can be written in an array, where the $r^{th}$ row consists of $s(n)$ for $2^r \leq n \leq 2^{r+1}$, for $r \geq 0$. The even entries in each row are copied from the previous row, and the odd entries are found by adding adjacent entries in the row above. The first five rows of the array are given in Table~\ref{tablestern}, with the enumeration of terms as in Sloane's {\it On-Line Encyclopedia of Integer Sequences} \cite{sloane}. \begin{table}[!ht] \begin{center}$ \begin{array}{ccccccccccccccccc} 1& & & & & & & & & & & & & & & &1 \\ 1& & & & & & & &2& & & & & & & &1 \\ 1& & & &3& & & &2& & & &3& & & &1 \\ 1& &4& &3& &5& &2& &5& &3& &4& &1 \\ 1&5&4&7&3&8&5&7&2&7&5&8&3&7&4&5&1 \end{array} $ \caption{The first five rows of the diatomic array for the Stern sequence} \end{center} \label{tablestern} \end{table} De Rham \cite{derham} was the first to consider the Stern sequence as defined above. He attributed the name to Bachmann \cite{bachmann}, who considered only the diatomic array. The related {\it Stern-Brocot array} \cite{graham} was used in defining Minkowski's ?-function \cite{minkowski}, and the Stern sequence has recently been used to understand 2-regular sequences \cite{allouche} and the Tower of Hanoi graph \cite{hinz}. In this paper we define a new two-parameter family of recursive sequences called the {\it bow sequences}, which have the flipped recursion from the Stern recursion. \begin{definition} The general $\mathit{bow\ sequence}$, $b_{\alpha, \beta}(n)$, for $\alpha$, $\beta \in \mathbb{Z}$ is defined by: \begin{align} b_{\alpha, \beta}(0) & = 0, \quad b_{\alpha, \beta}(1) = \alpha, \quad b_{\alpha, \beta}(2) = \beta; \\ b_{\alpha, \beta}(2n) & = b_{\alpha, \beta}(n)+b_{\alpha, \beta}(n+1), \quad \text{for } n \geq 2; \label{evenrecur}\\ b_{\alpha, \beta}(2n+1) & = b_{\alpha, \beta}(n), \quad \text{for } n \geq 1. \label{oddrecur} \end{align} \end{definition} We define $b_{\alpha,\beta}(0)=0$ to simplify results, although the designation does not affect later terms in the sequence, as $b_{\alpha,\beta}(0)$ does not enter into the recurrence. It is also worth noting that (\ref{evenrecur}) fails in the case where $n=1$, since if $\alpha \neq 0$, then $b_{\alpha,\beta}(2) \neq b_{\alpha,\beta}(1)+b_{\alpha,\beta}(2)$. Table~\ref{genarray} lists the first 17 values of the general bow sequence. \begin{table}[!ht] \[ \begin{array}{cc} n & b_{\alpha, \beta}(n)\\ \hline 0 & 0 \\ 1 & \alpha \\ 2 & \beta \\ 3 & \alpha \\ 4 & \alpha + \beta \\ 5 & \beta \\ 6 & 2\alpha + \beta \\ 7 & \alpha \\ 8 & \alpha + 2\beta \\ 9 & \alpha + \beta \\ 10 & 2\alpha + 2\beta \\ 11 & \beta \\ 12 & 3\alpha + \beta \\ 13 & 2\alpha + \beta \\ 14 & 2\alpha + 2\beta \\ 15 & \alpha \\ 16 & 2\alpha + 3\beta \end{array} \] \caption{The general bow sequence} \label{genarray} \end{table} Many properties of the bow sequences are related to known properties of the Stern sequence. In particular, in Section~\ref{secgcd} we note that although pairs of consecutive terms in the Stern sequence are always relatively prime, pairs of consecutive terms in the bow sequences may share a common factor, but triples may only share factors which divide $\gcd(\alpha, \beta)$. We also show that, much like the Stern sequence, the maximum values of the bow sequences on intervals are related to the Fibonacci numbers. Next, in Section~\ref{sums}, we derive properties of the summatory function. Then we derive the generating function for the general bow sequence, and give interpretations of the generating function for two basic cases in Section~\ref{generating}. In particular, we note that $b_{0,1}(n)$ is the number of ways of writing $n-2$ as the sum $\displaystyle\sum_i c_i 2^i$ where $c_i \in \{0,2,3\}$, while $b_{1,0}(n)$ is the number of ways of writing $n-3$ as a finite sum $\displaystyle\sum_{i=0}^k c_i 2^i$ where $c_i \in \{1,3,4\}$. Lastly, we look at an alternative representation of $b_{0, 1}(n)$ in Section~\ref{reps}. \section{Preliminaries} We begin by considering the values of the general bow sequence. Note that the terms of the general bow sequence are not necessarily distinct. In particular, we can see from Table~\ref{genarray} that $b_{\alpha, \beta}(10) = b_{\alpha, \beta}(14)$. By considering the recursion, we see that $b_{\alpha, \beta}(n)$ is linear in $\alpha$ and $\beta$. Accordingly, we can write \begin{align} b_{\alpha, \beta}(n) = \alpha b_{1,0}(n) + \beta b_{0,1}(n). \label{linearity} \end{align} For simplicity, we shall define \begin{align*} b_0(n):=b_{0,1}(n), \end{align*} and \begin{align*} b_1(n):=b_{1,0}(n). \end{align*} In this paper we consider the sequences $b_0(n)$ \seqnum{A106345} and $b_1(n)$ \seqnum{A281185}, as all other cases of the general bow sequence can be determined from these two cases by applying equation~(\ref{linearity}). We can present the values of the general bow sequence as a ``triatomic'' array where the first row is $b_{\alpha, \beta}(1)$, $b_{\alpha, \beta}(2)$, $b_{\alpha, \beta}(3)$, and the second row is $b_{\alpha, \beta}(3)$, $b_{\alpha, \beta}(4)$, $b_{\alpha, \beta}(5)$, $b_{\alpha, \beta}(6)$, $b_{\alpha, \beta}(7)$. In general the $r$-th row contains $b_{\alpha, \beta}(2^r-1)$, ..., $b_{\alpha, \beta}(2^{r+1}-1)$. The odd entries in each row are copied from the previous row in Table~\ref{gentri}. The even entries are found by adding the two numbers in the previous row that occur to the right of the entry. For example, the second entry in the third row, $b_{\alpha,\beta}(8)=\alpha+2\beta$, is obtained by adding the second and third entries in the second row of the array, namely, $\alpha + \beta$ and $\beta$. The last even entry in each row is obtained by summing the first two entries in that same row. The first three rows of the array are given in Table~\ref{gentri}. \begin{table}[!ht] \[ \begin{array}{ccccccccc} \alpha & & & & \beta & & & & \alpha \\ \alpha & & {\color{magenta}\alpha+\beta} & & {\color{magenta}\beta} & & 2\alpha+\beta & & \alpha \\ \alpha & {\color{magenta}\alpha+2\beta} & \alpha+\beta & 2\alpha+2\beta & \beta & 3\alpha+\beta & 2\alpha+\beta & 2\alpha+2\beta & \alpha \end{array} \] \caption{First three rows of the triatomic array for the general bow sequence} \label{gentri} \end{table} The triatomic arrays for $b_{0}(n)$ and $b_{1}(n)$ are quite different from each other. As it turns out, $b_{0}(n)$ is much more regular than $b_{1}(n)$, but the two sequences share many properties. Consider Table~\ref{tableb0} and Table~\ref{tableb1}: \begin{table}[!ht] \[ \begin{array}{ccccccccccccccccc} 0& & & & & & & &1& & & & & & & &0 \\ 0& & & &1& & & &1& & & &1& & & &0 \\ 0& &2& &1& &2& &1& &1& &1& &2& &0 \\ 0&3&2&3&1&3&2&2&1&2&1&3&1&2&2&3&0 \end{array} \] \caption{First four rows of the triatomic array for $b_0(n)$} \label{tableb0} \end{table} \begin{table}[!ht] \[ \begin{array}{ccccccccccccccccc} 1& & & & & & & &0& & & & & & & &1 \\ 1& & & &1& & & &0& & & &2& & & &1 \\ 1& &1& &1& &2& &0& &3& &2& &2& &1 \\ 1&2&1&3&1&2&2&3&0&5&3&4&2&3&2&3&1 \end{array} \] \caption{First four rows of the triatomic array for $b_{1}(n)$} \label{tableb1} \end{table} \section{Greatest common divisors and maximum values} \label{secgcd} \subsection{Greatest common divisors of three consecutive terms} One interesting property of the bow sequences is that although two consecutive terms may share a nontrivial factor, three consecutive terms can only share factors which divide $\gcd{(\alpha, \beta)}$. \begin{theorem} For all $\{\alpha, \beta\}$ and $n > 0$, \begin{align} \gcd(b_{\alpha, \beta}(n), b_{\alpha, \beta}(n+1), b_{\alpha, \beta}(n+2)) = \gcd(\alpha, \beta). \end{align} \label{GCD} \end{theorem} \begin{proof} Observe from Table~\ref{genarray} that $\gcd(b_{\alpha,\beta}(n),b_{\alpha,\beta}(n+1),b_{\alpha,\beta}(n+2))=\gcd(\alpha, \beta)$ \newline for $n=1,\ 2$. Now assume that this holds true for $n0$. \end{proof} \begin{remark} This result bears some similarity to a result for pairs of consecutive terms of the Stern sequence. As noted by Stern \cite{calkin,lehmer,stern}, for $n \geq 0$, every pair of consecutive terms of the Stern sequence is relatively prime, or $\gcd(s(n),s(n+1))=1.$ \end{remark} \subsection{Greatest common divisors of pairs} Surprisingly, Theorem~\ref{GCD} has implications for pairs. Although we have seen in Table~\ref{tableb0} and Table~\ref{tableb1} that pairs frequently share common factors, when the pairs \begin{align*} (b_0(n), b_0(n+1)), \text{ and } (b_1(n), b_1(n+1)) \end{align*} are taken together, the resulting quadruple does not have a common factor. \begin{theorem} For $n\geq 0$, $\gcd(b_0(n), b_0(n+1), b_1(n), b_1(n+1))=1$. \label{bruce} \end{theorem} \begin{proof} Suppose $p$ is prime, and let \begin{align*} p \mid \gcd(b_0(n), b_0(n+1), b_1(n), b_1(n+1)). \end{align*} Then, $p$ must necessarily divide $b_0(n)$ and $b_0(n+1)$, so we know by Theorem~\ref{GCD} that $p \nmid b_0(n+2)$. Similarly, $p \nmid b_1(n+2)$. So let \begin{align*} b_0(n+2) \equiv r \pmod p \ \ \ \ \text{ and } \ \ \ \ b_1(n+2) \equiv s \pmod p, \end{align*} where $1 \leq r,s \leq p-1$. Consider $b_{s,-r}(n) = s b_1(n) -r b_0(n)$. Thus $p \mid b_{s,-r}(n)$, and $p \mid b_{s,-r}(n+1)$. Then, since \begin{align*} b_{s,-r}(n+2) \equiv sr+(-r)s \equiv 0 \pmod p, \end{align*} we know that $p \mid b_{s,-r}(n+2)$. But this implies that $p \mid \gcd(r,s)$, which is a contradiction. Thus $\gcd(b_0(n), b_0(n+1), b_1(n), b_1(n+1))=1$. \end{proof} \begin{remark} Note that Theorem~\ref{bruce} fails if we consider only three of the four terms. For example, consider $n=2149948$. Then we have \begin{align*} (b_0(n), b_0(n+1), b_1(n), b_1(n+1)) &= (2070, 1815, 1430, 1254) \\ &=(2 \cdot 3^2 \cdot 5 \cdot 23, 3 \cdot 5 \cdot 11^2, 2 \cdot 5 \cdot 11 \cdot 13, 2 \cdot 3 \cdot 11 \cdot 19). \end{align*} When we consider the triples, we find that \begin{align*} \gcd(b_0(n), b_0(n+1),b_1(n)) & = 5,\\ \gcd(b_0(n), b_0(n+1),b_1(n+1)) & = 3,\\ \gcd(b_0(n), b_1(n),b_1(n+1)) & = 2,\\ \gcd(b_0(n+1), b_1(n),b_1(n+1)) & = 11. \end{align*} However, clearly $\gcd(b_0(n), b_0(n+1),b_1(n), b_1(n+1)) = 1$. \end{remark} Similarly, we have the following theorem. \begin{theorem} For $n\geq 0$, $\gcd(b_0(n), b_0(n+2), b_1(n), b_1(n+2))=1$. \label{bruce2} \end{theorem} %By employing {\it Mathematica}, we have found that $b_0(n)$, $b_0(n+1)$, $b_1(n)$, and $b_1(n+1)$ do not share a single common factor for $N \leq 2\cdot 10^9$. \begin{proof} Suppose $p$ is prime, and let \begin{align*} p \mid \gcd(b_0(n), b_0(n+2), b_1(n), b_1(n+2)). \end{align*} Then, $p$ must necessarily divide $b_0(n)$ and $b_0(n+2)$, so we know by Theorem~\ref{GCD} that $p \nmid b_0(n+1)$. Similarly, $p \nmid b_1(n+1)$. So let \begin{align*} b_0(n+1) \equiv r \pmod p \ \ \ \ \text{ and } \ \ \ \ b_1(n+1) \equiv s \pmod p, \end{align*} where $1 \leq r,s \leq p-1$. Consider $b_{s,-r}(n) = s b_1(n) -r b_0(n)$. Thus $p \mid b_{s,-r}(n)$, and $p \mid b_{s,-r}(n+2)$. Then, since \begin{align*} b_{s,-r}(n+1) \equiv sr+(-r)s \equiv 0 \pmod p, \end{align*} we know that $p \mid b_{s,-r}(n+1)$. But this implies that $p \mid \gcd(r,s)$, which is a contradiction. Thus $\gcd(b_0(n), b_0(n+2), b_1(n), b_1(n+2))=1$. \end{proof} \subsection{Maximum values on intervals} For the next theorem, we will need the Fibonacci numbers \seqnum{A000045}, defined as usual by \begin{align*} F_0 & = 0, \quad F_1 = 1;\\ F_n & = F_{n-1}+F_{n-2}, \quad \text{for } n \geq 2. \end{align*} \begin{theorem} For $r \geq 1$, \begin{align} b_{\alpha, \beta}(2^r)=\alpha F_{r-1}+\beta F_r. \end{align} In particular, for $r \geq 1$, \begin{align*} b_0(2^r)=F_{r}, \quad b_1(2^r)=F_{r-1}, \quad \text{and} \quad b_{1,1}(2^r)=F_{r+1}. \end{align*} \label{twotor} \end{theorem} \begin{proof} First, note that by applying (\ref{evenrecur}) and (\ref{oddrecur}) we find for $n \geq 1$, \begin{align*} b_{\alpha, \beta}(4n) =b_{\alpha, \beta}(2n)+b_{\alpha, \beta}(2n+1) =b_{\alpha, \beta}(2n)+b_{\alpha, \beta}(n). \end{align*} Thus, for $r \geq 2$, \begin{align*} b_{\alpha, \beta}(2^r) =b_{\alpha, \beta}(2^{r-1})+b_{\alpha, \beta}(2^{r-2}). \end{align*} Secondly, recall by (\ref{linearity}) that \begin{align*} b_{\alpha, \beta}(2^r)=\alpha b_{1}(2^r)+\beta b_{0}(2^r). \end{align*} Thus we consider only these two cases. All that remains is to check the initial conditions. We find that \begin{align*} (b_0(2),b_0(4)) = (0,1) = (F_0,F_1), \end{align*} and \begin{align*} (b_1(2),b_1(4)) = (1,1) = (F_1,F_2). \end{align*} Thus the initial conditions are satisfied. \end{proof} Next, we estimate the size of $b_{\alpha, \beta}(n)$. Let $I_r=(2^{r-1}, 2^r] \cap \mathbb{Z}$. To be specific, \begin{align*} I_r = \{2^{r-1}+1, \ldots, 2^r\}. \end{align*} Note that \begin{align*} I_r =(2I_{r-1}-1) \cup 2I_{r-1}. \end{align*} We have the following upper bound. \begin{theorem} For $r \geq 1$, \begin{align} \max_{n \in I_r}{|b_{\alpha, \beta}(n)|} & \leq \max{\{|\alpha|, |\beta|\}} F_{r+1}. \label{maxforgen} \end{align} Moreover, for $\beta \geq \alpha \geq 0$, \begin{align} \max_{n \in I_r}{|b_{\alpha, \beta}(n)|} = b_{\alpha, \beta}(2^r)=\alpha F_{r-1} + \beta F_r. \end{align} \label{max} \end{theorem} \begin{proof} Since $b_{\alpha, \beta}(n) \geq 0$ for $\alpha$, $\beta \geq 0$, $|b_{\alpha, \beta}(n)| \leq b_{|\alpha|, |\beta|}(n)$, and we may assume that $\alpha$, $\beta \geq 0$. Observe that for $\alpha$, $\beta \geq 0$ and $\gamma = \max\{\alpha, \beta\}$, \begin{align*} b_{\alpha, \beta}(n) \leq b_{\gamma, \gamma}(n) & = \gamma b_{1,1}(n) \\ & = \gamma \left( b_0(n)+b_1(n) \right) . \end{align*} For $r=1,2,$ it is easy to see that $\max_{n \in I_r}{b_{1,1}(n)}$ is $F_{r+1}$. Now assume that this holds for all $r 0$ and $b_{0,\delta}(n)=\delta b_{0}(n)$, we have $\max_{n \in I_{r}}{b_{0,\delta}(n)} \leq \delta F_r$. Now we shall show that the maximum occurs at $n=2^r$. Let $\beta \geq \alpha \geq 0$. Then, by setting $\gamma = \alpha$ and $\delta = \beta-\alpha$ in the previous results above, we find \begin{align*} b_{\alpha, \beta}(2^r)&=\alpha b_{1,1}(2^r)+ (\beta-\alpha)b_{0}(2^r) \\ & \leq \alpha F_{r+1}+(\beta - \alpha)F_r\\ & = \alpha F_{r-1}+ \beta F_r. \end{align*} However, by Theorem~\ref{twotor} we know that $b_{\alpha, \beta}(2^r)=\alpha F_{r-1}+\beta F_r$, thus the maximum occurs at $n=2^r$. \end{proof} \begin{remark} As noted by Lucas \cite{lucas} and Lehmer \cite{lehmer}, the maximum value of $s(n)$ on $I_r$ is $F_{r+1}$. \end{remark} \section{Properties of the summatory function} \label{sums} Next, we consider the sums of the rows of the triatomic array. We define a new function as follows: \begin{definition} $D_{\alpha, \beta}(r)$ is defined as the sum of the $r^{th}$ row of the triatomic array of the bow sequence, \begin{align} D_{\alpha, \beta}(r):= \sum_{n \in I_{r+1}} b_{\alpha,\beta}(n) = \sum_{n=2^r+1}^{2^{r+1}} b_{\alpha,\beta}(n). \label{sumF} \end{align} \end{definition} \begin{lemma} For $r \geq 5$, \begin{align} D_{\alpha, \beta}(r)=3D_{\alpha, \beta}(r-1)-\alpha F_{r-5} -\beta F_{r-4} . \end{align} \label{sumfunct} \end{lemma} \begin{proof} Starting with the definition of $D_{\alpha,\beta}(r)$ and applying the recurrence, we find \begin{align*} D_{\alpha,\beta}(r) & = \sum_{n \in I_{r+1}} b_{\alpha,\beta}(n) \\ & =\sum_{n \in I_r} b_{\alpha,\beta}(2n)+b_{\alpha,\beta}(2n-1) \\ & =\sum_{n \in I_r} b_{\alpha,\beta}(n) + b_{\alpha,\beta}(n+1) + b_{\alpha, \beta}(n-1) \\ & =\left(\sum_{n \in I_r} 3b_{\alpha,\beta}(n) \right) + b_{\alpha,\beta}(2^r + 1)-b_{\alpha,\beta}(2^{r-1} + 1) + b_{\alpha, \beta}(2^{r-1}) - b_{\alpha,\beta}(2^r) \\ & = 3 D_{\alpha, \beta}(r-1) + b_{\alpha, \beta}(2^{r-1}) - b_{\alpha, \beta}(2^{r-2})+ b_{\alpha, \beta}(2^{r-1}) - b_{\alpha,\beta}(2^r). \end{align*} Then, by applying Theorem~\ref{twotor} and simplifying we get \begin{align*} D_{\alpha,\beta}(r) & = 3 D_{\alpha,\beta}(r-1)+ 2 (\alpha F_{r-2}+\beta F_{r-1}) - \alpha F_{r-3} - \beta F_{r-2} - \alpha F_{r-1} - \beta F_r \\ & = 3D_{\alpha, \beta}(r-1)+\alpha \left( F_{r-1} - 3 F_{r-3} \right) +\beta \left( F_r - 3 F_{r-2} \right) \\ & = 3D_{\alpha, \beta}(r-1)+\alpha \left(F_{r-2}-2F_{r-3} \right) + \beta \left( F_{r-1}-2 F_{r-2} \right) \\ & = 3D_{\alpha, \beta}(r-1)+\alpha \left( F_{r-4} - F_{r-3} \right) + \beta \left( F_{r-3}-F_{r-2} \right) \\ & = 3D_{\alpha, \beta}(r-1)-\alpha F_{r-5} - \beta F_{r-4}. \end{align*} \end{proof} Lemma~\ref{sumfunct} suggests a relationship of the following form. \begin{theorem} For $r \geq 1$, \begin{align*} D_{\alpha, \beta}(r)=\alpha \bigg{(} \frac{7}{5} \cdot 3^{r-1} + \frac{3}{5} \cdot F_r - \frac{4}{5} \cdot F_{r-1} \bigg{)} + \beta \bigg{(} \frac{2}{5} \cdot 3^r - \frac{1}{5} \cdot F_r + \frac{3}{5} \cdot F_{r-1} \bigg{)}. \end{align*} \label{above} \end{theorem} \begin{proof} By considering Table~\ref{genarray}, we check that this holds for small $r$. Suppose that the formula holds for $r < k$. Then by Lemma~\ref{sumfunct}, \begin{align*} D_{\alpha,\beta}(k) & = 3\alpha \bigg{(} \frac{7}{5} \cdot 3^{k-2} + \frac{3}{5} \cdot F_{k-1} - \frac{4}{5} \cdot F_{k-2} \bigg{)} + 3\beta \bigg{(} \frac{2}{5} \cdot 3^{k-1} - \frac{1}{5} \cdot F_{k-1} + \frac{3}{5} \cdot F_{k-2} \bigg{)} \\ & \ \ \ \ \ + \alpha F_{k-1} - 3 \alpha F_{k-3} + \beta F_k - 3 \beta F_{k-2}\\ & = \alpha \bigg{(} \frac{7}{5} \cdot 3^{k-1} + \frac{9}{5} \cdot F_{k-1} - \frac{12}{5} \cdot F_{k-2} + F_{k-1}-3 F_{k-3} \bigg{)} \\ & \ \ \ \ \ + \beta \bigg{(} \frac{2}{5} \cdot 3^{k} - \frac{3}{5} \cdot F_{k-1} + \frac{9}{5} \cdot F_{k-2} + F_k - 3 F_{k-2}\bigg{)} \\ & = \alpha \bigg{(} \frac{7}{5} \cdot 3^{k-1} + \frac{3}{5} \cdot F_k - \frac{4}{5} \cdot F_{k-1} \bigg{)} + \beta \bigg{(} \frac{2}{5} \cdot 3^k - \frac{1}{5} \cdot F_k + \frac{3}{5} \cdot F_{k-1} \bigg{)}. \end{align*} Thus the theorem holds for $r \geq 1$. \end{proof} \begin{remark} Theorem~\ref{above} implies that \begin{align*} \frac{D_{\alpha,\beta}(r)}{3^r} = \frac{7 \alpha + 6 \beta}{15} + \mathcal{O}\left( \left( \frac{\phi}{3}\right)^r \right)= \frac{7 \alpha + 6 \beta}{15} + o(1). \end{align*} \end{remark} \begin{remark} Interestingly, as noted by Stern \cite{stern} and Lehmer \cite{lehmer}, the sum of the $r^{th}$ row of the diatomic array for the Stern sequence is $3^r+1$. \end{remark} \begin{remark} Note that $D_{-6,7}(r) = -5F_r + 9 F_{r-1}$, which means that the average value of $b_{-6,7}(n) \to 0$ as $n \to \infty$. \end{remark} Now suppose we sum all the terms of the general bow sequence up to the $N^{th}$ term. Note that summatory functions of $k$-regular sequences are again $k$-regular sequences, as they are obtained by convolution with the all 1 sequence, which is also $k$-regular. The result is $k$-regular, as noted by Allouche and Shallit \cite{allshall}, which explains in some sense Theorem~\ref{theoremE}. Define a new function as follows: \begin{definition} $E_{\alpha, \beta}(N)$ is defined as the finite sum of the first $N$ terms of the bow sequence, \begin{align} E_{\alpha,\beta}(N) & :=\sum_{k=1}^N b_{\alpha,\beta}(k). \label{sumE} \end{align} \end{definition} \begin{theorem} For $N\geq 1$ we have the following: \begin{align} E_{\alpha,\beta}(2N) &= 3 E_{\alpha,\beta}(N) - \alpha - b_{\alpha,\beta}(N) + b_{\alpha,\beta}(N+1). \end{align} \label{theoremE} \end{theorem} \begin{proof} One can calculate quickly that this formula holds for $N<4$. Let $N \geq 4$. We start with the definition, separate terms and apply the recursion to find \begin{align*} E_{\alpha,\beta}(2N) &= \sum_{k=1}^{2N} b_{\alpha,\beta}(k) \\ &= b_{\alpha,\beta}(1)+b_{\alpha,\beta}(2)+b_{\alpha,\beta}(3) +\sum_{k=4}^{2N} b_{\alpha,\beta}(k) \\ &= b_{\alpha,\beta}(1)+b_{\alpha,\beta}(2)+b_{\alpha,\beta}(3) +\sum_{k=2}^{N} \left( b_{\alpha,\beta}(2k)+b_{\alpha,\beta}(2k+1) \right) - b_{\alpha,\beta}(2N+1) \\ &= b_{\alpha,\beta}(1)+b_{\alpha,\beta}(2)+b_{\alpha,\beta}(3) +\sum_{k=2}^{N} \left( 2b_{\alpha,\beta}(k)+b_{\alpha,\beta}(k+1) \right) - b_{\alpha,\beta}(2N+1). \end{align*} Using Table~\ref{genarray} we see that \begin{align*} E_{\alpha,\beta}(2N) &= 2\alpha + \beta + \sum_{k=2}^{N} \left( 2b_{\alpha,\beta}(k)+b_{\alpha,\beta}(k+1) \right) - b_{\alpha,\beta}(2N+1)\\ &= \sum_{k=1}^{N} 2b_{\alpha,\beta}(k)+ \sum_{k=1}^N b_{\alpha,\beta}(k+1) - b_{\alpha,\beta}(2N+1). \end{align*} We reindex the second sum and apply~(\ref{sumE}) to obtain \begin{align*} E_{\alpha,\beta}(2N) &= 2E_{\alpha,\beta}(N) +\sum_{k=2}^{N+1} b_{\alpha,\beta}(k) - b_{\alpha,\beta}(2N+1)\\ &= 2E_{\alpha,\beta}(N) + E_{\alpha,\beta}(N) - \alpha + b_{\alpha,\beta}(N+1) - b_{\alpha,\beta}(2N+1). \end{align*} Then by applying the recursion we get the desired result \begin{align*} E_{\alpha,\beta}(2N) &= 3 E_{\alpha,\beta}(N) - \alpha - b_{\alpha,\beta}(N) + b_{\alpha,\beta}(N+1). \end{align*} \end{proof} \begin{corollary} For $r\geq 3$ we have \begin{align} E_{\alpha,\beta}(2^{r+1}) = 3E_{\alpha,\beta}(2^r) - \alpha(F_{r-3}+1) - \beta F_{r-2}. \end{align} \label{corlemma} \end{corollary} \begin{proof} By Theorem~\ref{theoremE} we have \begin{align*} E_{\alpha,\beta}(2^{r+1}) &= 3 E_{\alpha,\beta}(2^r) - \alpha - b_{\alpha,\beta}(2^r) + b_{\alpha,\beta}(2^r+1). \end{align*} By applying Theorem~\ref{twotor} and (\ref{oddrecur}), and simplifying we obtain \begin{align*} E_{\alpha,\beta}(2^{r+1}) &= 3 E_{\alpha,\beta}(2^r) - \alpha - \left( \alpha F_{r-1} + \beta F_r \right) + \left( \alpha F_{r-2} + \beta F_{r-1} \right)\\ &= 3 E_{\alpha,\beta}(2^r) - \alpha - \alpha F_{r-3} - \beta F_{r-2} \\ &=3E_{\alpha,\beta}(2^r) - \alpha(F_{r-3}+1) - \beta F_{r-2}. \end{align*} \end{proof} Corollary~\ref{corlemma} suggests the following relationship. \begin{theorem} For $r \geq 1$ we have \begin{align} E_{\alpha,\beta}(2^{r}) = \alpha \left( \frac{7}{10} \cdot 3^{r-1} - \frac{1}{5} \cdot F_r + \frac{3}{5} \cdot F_{r-1} + \frac{1}{2} \right) + \beta \left( \frac{1}{5} \cdot 3^r + \frac{2}{5} \cdot F_r - \frac{1}{5} \cdot F_{r-1} \right). \end{align} \label{longthem} \end{theorem} \begin{proof} By considering Table~\ref{genarray}, we check that this holds for small $r \geq 1$. Suppose that the formula holds for $r 0$ has a unique representation \begin{align*} n=\sum_{i=0}^{\infty}\gamma_i 2^i, \end{align*} where $\gamma_i \in \{0,1\}$. \end{example} We now consider the generating function for the general bow sequence. First, let \begin{align} B_{\alpha, \beta}(x)=\sum_{n \geq 0} b_{\alpha, \beta}(n)x^n = \alpha B_{1,0}(x) + \beta B_{0,1}(x). \label{genfun} \end{align} It follows from (\ref{maxforgen}) that $B_{1,0}(x)$ and $B_{0,1}(x)$ have radius of convergence 1. By repeatedly applying (\ref{evenrecur}) and (\ref{oddrecur}) and tweaking the limits, we have \begin{align*} B_{\alpha, \beta}(x) & = \alpha x + \beta x^2 + \sum_{n \geq 3} b_{\alpha, \beta}(n)x^n \\ & = \alpha x + \beta x^2 + \sum_{n \geq 1} b_{\alpha, \beta}(2n+1)x^{2n+1} + \sum_{n \geq 2} b_{\alpha, \beta}(2n)x^{2n} \\ & = \alpha x + \beta x^2 + \sum_{n \geq 1} b_{\alpha, \beta}(n)x^{2n+1} + \sum_{n \geq 2} (b_{\alpha, \beta}(n)+b_{\alpha, \beta}(n+1))x^{2n} \\ & = \alpha x + \beta x^2 + \sum_{n \geq 1} b_{\alpha, \beta}(n)x^{2n+1} + \sum_{n \geq 2} b_{\alpha, \beta}(n)x^{2n} + \sum_{n \geq 2} b_{\alpha, \beta}(n+1)x^{2n} \\ & = \alpha x + \beta x^2 + \sum_{n \geq 1} b_{\alpha, \beta}(n)x^{2n+1} + \sum_{n \geq 2} b_{\alpha, \beta}(n)x^{2n} + \sum_{n \geq 3} b_{\alpha, \beta}(n)x^{2n-2} \\ \end{align*} \begin{align*} & = \alpha x + \beta x^2 + x \sum_{n \geq 1} b_{\alpha, \beta}(n)x^{2n} + \sum_{n \geq 2} b_{\alpha, \beta}(n)x^{2n} + \frac{1}{x^2} \sum_{n \geq 3} b_{\alpha, \beta}(n)x^{2n} \\ & = \alpha x + \beta x^2 + x \sum_{n \geq 1} b_{\alpha, \beta}(n)x^{2n} + \sum_{n \geq 1} b_{\alpha, \beta}(n)x^{2n} - \alpha x^2 \\ & \ \ \ \ \ \ + \frac{1}{x^2} \sum_{n \geq 1} b_{\alpha, \beta}(n)x^{2n} - \alpha - \beta x^2 \\ & = - \alpha + \alpha x - \alpha x^2 + \left( \frac{1}{x^2}+1+x \right) B_{\alpha, \beta}(x^2) \\ & = - \alpha (1 - x + x^2) + \frac{1}{x^2}(1 + x^2 + x^3)B_{\alpha, \beta}(x^2). \end{align*} Since $b_{\alpha, \beta}(0)=0$ and $b_{\alpha, \beta}(1)=\alpha$, we can write $B_{\alpha, \beta}(x)=\alpha x + x^2 C_{\alpha, \beta}(x)$, with $C_{\alpha, \beta}(0)=\beta$, so $B_{\alpha, \beta}(x^2)= \alpha x^2 + x^4 C_{\alpha, \beta}(x^2)$. Thus we have \begin{align*} B_{\alpha, \beta}(x) & = \alpha x + x^2 C_{\alpha, \beta}(x) \\ & = \frac{1}{x^2}(1+x^2+x^3)(\alpha x^2 + x^4 C_{\alpha, \beta}(x^2)) - \alpha (1-x+x^2). \\ \end{align*} Solving for $C_{\alpha, \beta}(x)$, we find \begin{align*} C_{\alpha, \beta}(x) & = \frac{1}{x^2} \Big{(} \alpha(1-x+x^2+x^3)+x^2 C_{\alpha, \beta}(x^2)(1+x^2+x^3) - \alpha(1-x+x^2) \Big{)} \\ & = \alpha x + C_{\alpha, \beta}(x^2)(1+x^2+x^3). \end{align*} We can feed this identity back into the equation to get \begin{align*} C_{\alpha, \beta}(x) & = \alpha x + (1+x^2+x^3)(\alpha x^2 + C_{\alpha, \beta}(x^4)(1+x^4+x^6)) \\ & = \alpha x + (1+x^2+x^3) \alpha x^2 + (1+x^2+x^3)(1+x^4+x^6)C_{\alpha, \beta}(x^4) . \end{align*} After $N$ steps, \begin{align*} C_{\alpha, \beta}(x) = \alpha x + \alpha \sum_{k=0}^N x^{2 \cdot 2^k} \prod_{j=0}^{k} (1+x^{2 \cdot 2^j}+x^{3 \cdot 2^j}) + \prod_{k=0}^{N+1} (1+ x^{2 \cdot 2^k}+x^{3 \cdot 2^k}) C_{\alpha, \beta}(x^{2^{N+2}}). \end{align*} Since, $C_{\alpha, \beta}(x) = \beta + x \cdot P(x)$ for some $P(x)$, $C_{\alpha, \beta}(x^{2^{N+2}})-\beta = x^{2^{N+2}}P(x^{2^{N+2}})$. Thus for $|x|<1$, $ C_{\alpha,\beta}(x^{2^{N+2}})-\beta \to 0$ as $N \to \infty$; hence we have \begin{align*} C_{\alpha, \beta}(x) = \alpha x + \alpha \sum_{k=0}^{\infty} x^{2 \cdot 2^k} \prod_{j=0}^{k} (1+x^{2 \cdot 2^j}+x^{3 \cdot 2^j}) + \beta \prod_{k=0}^{\infty} (1+x^{2 \cdot 2^k}+x^{3 \cdot 2^k}). \end{align*} Thus we have the following theorem. \begin{theorem} The generating function for the general bow sequence is: \begin{align} B_{\alpha, \beta}(x) & = \alpha x + \alpha x^3 + \alpha x^2 \sum_{k=0}^{\infty} x^{2 \cdot 2^k} \prod_{j=0}^{k} (1+x^{2 \cdot 2^j}+x^{3 \cdot 2^j}) \\ & + \beta x^2 \prod_{k=0}^{\infty} (1+x^{2 \cdot 2^k}+x^{3 \cdot 2^k}). \notag \end{align} \end{theorem} Since $B_{\alpha, \beta}(x) = \alpha B_{1,0}(x) + \beta B_{0,1}(x)$, we can state two combinatorial implications. First, as also noted by Anders, Lansing, Reznick, and the author \cite{anders} we have \begin{align} B_{0,1}(x):=\sum_{n=0}^{\infty}b_0(n)x^n = x^2 \prod_{k=0}^{\infty} (1+x^{2 \cdot 2^k}+x^{3 \cdot 2^k}) = x G^{2,3}(x) \end{align} for the case when $\alpha=0$, $\beta=1$. We see that $b_{0}(n) = c^{2, 3}(n-1)$, where $c^{2,3}(m)$ is the number of ways of writing $m-1$ as the sum $\displaystyle\sum_i c_i 2^i$ where $c_i \in \{0,2,3\}$. We interpret this statement as: \begin{corollary} Combinatorially, for $n \geq 2$, $b_{0}(n)$ is the number of ways of writing $n-2$ as the sum $\displaystyle\sum_i c_i 2^i$ where $c_i \in \{0,2,3\}$. \end{corollary} We also have \begin{align} B_{1,0}(x):=\sum_{n=0}^{\infty}b_1(n)x^n = x + x^3 + x^2 \sum_{k=0}^{\infty} x^{2 \cdot 2^k} \prod_{j=0}^{k} (1+x^{2 \cdot 2^j}+x^{3 \cdot 2^j}) \end{align} for the case when $\alpha=1$, $\beta=0$. We interpret this statement as: \begin{corollary} Combinatorially, for $n \geq 4$, $b_{1}(n)$ is the number of ways of writing $n-2-2^{k+1}$ as the sum $\displaystyle\sum_{i=0}^k c_i 2^i$ where $c_i \in \{0,2,3\}$ and $k \in \mathbb{N}$. \end{corollary} \begin{remark} By rearranging, we find that $b_{1}(n)$ is also the number of ways of writing $n-2$ as the sum $\displaystyle\sum_{i=0}^k c_i 2^i$ where $k \in \mathbb{N}$, $c_i \in \{0,2,3\}$ for $i \leq k-1$, and $c_k \in \{2,4,5\}$. \end{remark} Alternatively, since $\displaystyle\sum_{i=0}^k 2^i = 2^{k+1}-1$, we get the following formula \begin{align} B_{1,0}(x)= x + x^3 + x^3 \sum_{k=0}^{\infty} \prod_{j=0}^{k} (x^{1 \cdot 2^j}+x^{3 \cdot 2^j}+x^{4 \cdot 2^j}), \end{align} which means that $b_{1}(n)$ is the number of ways of writing $n-3$ as a finite sum $\displaystyle\sum_{i=0}^k c_i 2^i$ where $c_i \in \{1,3,4\}$. \begin{remark} Similarly, Reznick \cite{reznick} showed for the Stern sequence that \begin{align} S(x)=xT(x)=x \prod_{j=0}^{\infty}(1+x^{2^j}+x^{2 \cdot 2^j}). \end{align} By equation~(\ref{genfunct}) we see that $S(x)=G^{1,2}(x)$. \end{remark} \section{Another representation of $b_{0}(n)$} \label{reps} In this section, we discuss another representation of $b_0(n)$, found independently in unpublished work by Paul Barry \cite{barry}, and referenced in Sloane's {\it On-Line Encyclopedia of Integer Sequences} \cite{sloane}. The sequence was defined by Barry, but was not shown to satisfy the bow recurrence. We show that $b_0(n)$ can be determined by computing this finite sum, which is independent of the recurrence. Before we give this new equation we must first state a few formulas which will be necessary in the proof of our theorem. The first is the well-known dePolignac's formula. \begin{theorem}[dePolignac's Formula]~\cite{hardywright,nivenzuck} For $n \geq 1$, the exponent of the highest power of a prime $p$ dividing $n!$ is \begin{align} s_p (n):=\sum_{k=1}^{\infty} \left\lfloor{\frac{n}{p^k}}\right\rfloor. \end{align} \label{Polignac} \end{theorem} We will need the following corollary for the proof of the next theorem. \begin{corollary} For $m \geq 1$, \begin{align} s_2 (2m+1) = s_2(2m) = s_2 (m)+m. \end{align} \label{corPolignac} \end{corollary} \begin{proof} We write $(2m+1)!=(2m+1)(2m)!$, thus $s_2 (2m+1) = s_2(2m)$. Then, pulling the first term out of the sum, we find \begin{align*} s_2(2m)&=\left\lfloor{\frac{2m}{2}}\right\rfloor+\sum_{k=2}^{\infty} \left\lfloor{\frac{2m}{2^k}}\right\rfloor \\ &=m+s_2(m). \end{align*} Thus $s_2 (2m+1) = s_2(2m) = s_2 (m)+m$. \end{proof} \begin{remark} The second equality in Corollary~\ref{corPolignac} can also be shown directly by noting that \begin{align*} (2m)!=2^m m! \prod_{j=1}^{m} (2j-1). \end{align*} \end{remark} \begin{definition} Define $\epsilon(m)$ to be the smallest non-negative residue of $m$ modulo 2, thus $m \in \{0,1\}$. \end{definition} Let \begin{align} c(n):=\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor} \epsilon \left( \binom{k}{n-2k} \right). \end{align} The terms of this sequence are 1, 0, 1, 1, 1, 0, 2, 1, 2, $\ldots$ We can see that this looks the same as $b_{0}(n+2)$. In fact, we shall prove that $c(n-2)=b_{0}(n)$. Let $c(n-2)=a(n)$. We have the following lemma. \begin{lemma} \begin{align*} \binom{2a+1}{2b+1} \equiv \binom{2a+1}{2b} \equiv \binom{2a}{2b} \equiv \binom{a}{b} \pmod 2. \end{align*} \label{annoylemma} \end{lemma} \begin{proof} To show that the first three have the same parity, we note that \begin{align*} \frac{(2a+1)!}{(2b+1)!(2a-2b)!}, \text{ } \frac{(2a+1)!}{(2b)!(2a+1-2b)!}, \text{ and } \frac{(2a)!}{(2b)!(2a-2b)!} \end{align*} share all the same even factors in both their numerator and denominator. Thus the highest power of 2 dividing $\binom{2a+1}{2b+1}$, $\binom{2a+1}{2b}$, and $\binom{2a}{2b}$ is the same, and they are all congruent modulo 2. Then, to show that $\binom{a}{b} \equiv \binom{2a}{2b} \pmod 2$, we notice that if $s_2(a)=r$, then by Corollary~\ref{corPolignac} we know that $s_2(2a)=r+a$. Similarly, if $s_2(b)=t$, then $s_2(2b)=t+b$. Lastly, if $s_2(a-b)=s$, then $s_2(2a-2b)=s+(a-b)$. The highest power of 2 dividing $\binom{a}{b}$ is $r-s-t$, and the highest power of 2 dividing $\binom{2a}{2b}$ is $r+a-(t+b)-s-(a-b) = r-s-t$. Thus the highest power of 2 dividing $\binom{a}{b}$ and $\binom{2a}{2b}$ is the same, and they are congruent modulo 2. \end{proof} \begin{remark} Note that Lemma~\ref{annoylemma} also follows from Lucas's Theorem, stated below. In particular, we can see that $\binom{2a}{2b} \equiv \binom{a}{b} \pmod 2$ since multiplication by 2 simply shifts all the indices in the base 2 expansions of $a$ and $b$ up by 1. \end{remark} \begin{theorem}[Lucas's Theorem]~\cite{fine} For non-negative integers $m$ and $n$ and a prime $p$, the congruence relation \[ \binom{m}{n} \equiv \prod_{i=0}^{k} \binom{m_i}{n_i} \pmod p \] holds, where $m=\displaystyle\sum_{i=0}^k m_i p^i$ and $n=\displaystyle\sum_{i=0}^k n_i p^i$ with $m_i, n_i \in \{0, \dots, p-1\}$ are the base $p$ expansions of $m$ and $n$, using the convention that $\binom{m}{n}=0$ if $m