%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-60/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{remark}{Remark}

\title{On $N$-Sequences}
\author{T. C. Brown and M. L. Weiss}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{On $N$-sequences}, Math. Magazine \textbf{44} (1971), 89--92.}\bigskip\end{center}

In~\cite{silver1961}, it is shown that the Fibonacci sequence $1,1,2,3,5,\dots$ has the property that if any one term is removed from the sequence then every positive integer can be expressed as the sum of some of the terms that remain, and that if any two terms are removed, then there is a positive integer that cannot be expressed as the sum of some of the remaining terms. We describe this situation by saying that removal of any two terms from the Fibonacci sequence renders it \emph{incomplete}, while removal of any one term does not. A sequence which is not incomplete will be called \emph{complete}. 

In this note we consider, for each $n = 0,1,2,\dots,$ nondecreasing sequences which are rendered incomplete by the removal of any $n + 1$ terms, but not by the removal of any $n$ terms. We call such a sequence an \emph{n-sequence}. Thus the Fibonacci sequence is a $1$-sequence.We characterize in a simple way the set of all $1$-sequences and show that there are no $n$-sequences for any $n \geq 2$. A simple description of the set of all $0$-sequences seems more difficult, and is left open.

\begin{thm} \label{thm: 1}
The sequence $\{a_k\}_{k=1}^\infty$ is a $1$-sequence if and only if it has the following three properties:

(1) $a_1 = a_2 = 1$.

(2) $a_{k + 1} = a_k$ or $a_{k + 1}= \sum_{j=1}^{k - 1} a_j + 1, \qquad k \geq 2$.

(3) $a_{k+1} = \sum_{j=1}^{k-1}a_j + 1$ for infinitely many $k$.
\end{thm}

\begin{proof}[Proof of sufficiency]
The proof that the Fibonacci sequence is a $1$-sequence given in~\cite{silver1961} translates more or less immediately into a proof of the sufficiency of the given conditions, and is given here, slightly altered, for the sake of completeness.

Let $\{b_k\}_{k=1}^\infty$ be the sequence obtained from $\{a_k\}_{k=1}^\infty$ by deleting one term from $\{a_k\}$. Suppose that $N$ is the smallest number which is not the sum of terms from $\{b_k\}$ and that $a_n \leq N < a_{n+1}$. Then $\sum_{j=1}^{n - 1} b_j \geq \sum_{j=1}^{n-1} a_j = \left( \sum_{j=1}^{n-1} a_j + 1 \right) - 1 = a_{n+1} - 1 \geq N$. Now let $L$ be the smallest number greater than $N$ which is the sum of terms from $\{b_k\}$ and suppose that $L = \sum_{m=1}^r b_{j_m}$, where $j_1 < j_2 < \cdots < j_r \leq n - 1$. Then if $b_{j_1} = 1$ we get 
\[ \sum_{m=2}^r b_{j_m} = L - 1 \geq N, \]
and hence, since $N$ is not the sum of terms from $\{b_k\}$, $L - 1 > N$, contradicting the choice of $L$. If $b_{j_1} > 1$ then $N \geq a_n \geq b_{n-1} \geq b_{j_1}$, hence $N > b_{j_1} - 1 \geq 1$, hence by the definition of $N$, $b_{j_1} - 1 = \sum_{p=1}^s b_{j_p}'$, and moreover $b_{j_p}' < b_{j_m}$ for all $m \geq 2$ and all $p$. Thus $\sum_{p=1}^s b_{j_p}' + \sum_{m=2}^r b_{j_m} = L - 1 \geq N$, hence $> N$, again contradicting the choice of $L$. Thus $\{a_k\}$ remains complete if one term is deleted.

Suppose now that both $a_m$ and $a_n$ are deleted, $m < n$, to obtain $\{b_k\}$. We may assume without loss of generality that $a_{n+1} = \sum_{j=1}^{n-1} a_j + 1$. Then
\[ \sum_{j=1}^{n-2}b_j = \sum_{j=1}^{n-1} a_j - a_m = a_{n+1} - 1 - a_m < a_{n+1} - 1 = b_{n+1} - 1, \]
hence $b_{n-1} - 1$ is not that sum of terms of $\{b_k\}$. Then $\{a_k\}$ is rendered incomplete by the deletion of any two terms. 
\end{proof}

\begin{proof}[Proof of necessity]
Let $\{a_k\}$ be a $1$-sequence. Then clearly $a_1 = a_2 = 1$, and $a_3$ is either $1$ or $2$. Suppose that, for $k= 1,2,\dots,n \: (n \geq 2)$, either $a_{k+1} = a_k$ or $a_{k+1} = \sum_{j=1}^{k-1}a_j + 1$. We wish to show that then either $a_{n+2} = a_{n+1}$ or $a_{n+2} = \sum_{j=1}^n a_j + 1$. Clearly $a_{p + 1} \leq \sum_{j=1}^p a_j + 1$ for all $p$, otherwise deleting $a_{p + 1}$ from $\{a_k\}$ would yield an incomplete sequence. Thus in particular, $a_{n + 1} \leq a_{n + 2} \leq \sum_{j=1}^n a_j + 1$.

Let $\{b_k\}$ be the sequence obtained from $\{a_k\}$ by deleting $a_1$ and $a_{n+1}$. We show that if $a_{n+1} < a_{n+2} < \sum_{j=1}^n a_j + 1$ then $\{b_k\}$ is complete, contradicting the assumption that $\{a_k\}$ is a $1$-sequence. Note that $\{b_k\}_{k=1}^{n-1} = \{a_k\}_{k=2}^n$ is an initial part of the complete sequence $\{a_k\}_{k=2}^\infty$. It is easy to show by induction, and we leave it to the reader to do so, that if $\{c_k\}$ is complete and $N \leq c_1 + \cdots + c_m$ then $N$ is the sum of terms from $\{c_k\}_{k=1}^{m}$. Hence if $N \leq b_1 + \cdots + b_{n-1}$ then $N$ is the sum of terms from $\{b_k\}_{k=1}^{n-1}$ and we say that the sequence $\{b_k\}$ is complete through $b_1 + \cdots + b_{n-1}$.

Now 
\[ b_n = a_{n+2} < \sum_{j=1}^n a_j + 1 = 1 + \sum_{j=1}^{n-1}b_j + 1, \]
so $b_n \leq \sum_{j=1}^{n-1} b_j + 1$, and hence $\{b_k\}$ is complete through $b_1 + \cdots + b_n$. Next, 
\begin{align*} b_{n+1} &= a_{n + 3} \leq \sum_{j=1}^{n+1} a_j + 1 = 1 + b_1 + \cdots + b_{n-1} + a_{n+1} + 1 \\
&< 1 + b_1 + \cdots + b_{n-1} + a_{n+2} + 1 = 1 + b_1 + \cdots + b_n + 1. \end{align*}
Thus $b_{n+1} \leq \sum_{j=1}^n b_j + 1$, and so $\{b_k\}$ is complete through $b_1 + \cdots + b_{n+1}$. Now assume $\{b_k\}$ is complete through $b_1 + \cdots + b_{n+p}$, $p \geq 1$. Then 
\begin{align*} 
b_{n + p + 1} &= a_{n + p + 3} \leq \sum_{j=1}^{n + p + 1} a_j + 1 = 1 + \sum_{j=2}^n a_j + \sum_{j=n+1}^{n + p + 1} a_j + 1 \\
&= 1 + b_1 + \cdots + b_{n-1} + \sum_{j=n + 1}^{n+ p + 1}a_j + 1 \\
&< 1 + b_1 + \cdots + b_{n-1} + \sum_{j=n+2}^{n + p + 2} + 1 \\
&= 1 + b_1 + \cdots + b_{n-1} + \sum_{j=n}^{n + p} b_j + 1, \end{align*}
hence $b_{n + p + 1} \leq \sum_{j=1}^{n + p} b_j + 1$, hence $\{b_k\}$ is complete through $b_1 + \cdots + b_{n + p + 1}$. 

We have now shown that $\{b_k\}$ is complete through $b_1 + \cdots + b_m$ for all $m$, and hence is complete. This completes the proof that condition (2) holds for the sequence $\{a_k\}$. Condition (3) then follows immediately. This completes the proof of Theorem~\ref{thm: 1}.
\end{proof}

\begin{thm} \label{thm: 2}
For $n \geq 2$, there are no $n$-sequences.
\end{thm}

\begin{proof} For any $n > 2$, an $n$-sequence can be converted into a $2$-sequence by deleting any $n-2$ terms. Hence it is sufficient to show there are no $2$-sequences.

Suppose $\{a_k\}$ is a $2$-sequence. Then if any term is deleted the result is a $1$-sequence; in particular $\{a_k\}_{k=2}^\infty$ is a $1$-sequence, But then by Theorem~\ref{thm: 1} there are arbitrarily large $n$ such that $a_{n+2} = \sum_{j=2}^na_j + 1$, or, since $a_1 = 1, a_{n+2} = \sum_{j=1}^n a_j$. But then, choosing $n$ large enough that $a_n > 1$, we have $a_{n+2} - 1 > \sum_{j=1}^{n-1} a_j$, and hence $a_{n+2} - 1$ is not the sum of terms from the sequence resulting when $a_n,a_{n+1}$ are deleted from $\{a_k\}$. Thus $\{a_k\}$ is not a $2$-sequence. This completes the proof.
\end{proof} 


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}