INFINITELY MANY COMPOSITE NSW NUMBERS: AN INDUCTIVE PROOF

James A. Sellers

1. Motivation. The NSW numbers were introduced approximately 20 years ago [3] in connection with the order of certain simple groups. These are the numbers f_{n} which satisfy the recurrence

f_{n+1} = 6f_{n} − f_{n−1}  (1)

with initial conditions f_{1} = 1 and f_{2} = 7.

In recent years, these numbers have been studied from a variety of perspectives [1, 2]. Moreover, the author, in collaboration with Hugh Williams, has proven that there are infinitely many composite NSW numbers [4] as requested in [1]. The goal of this note is to provide a purely inductive proof of the main theorem in [4]. We restate it here.

\underline{Theorem 1.1}. For all m ≥ 1 and all n ≥ 0, f_{m}|f_{(2m−1)n+m}.

2. The Necessary Tools. To prove Theorem 1.1, we need to develop a few key tools.

\underline{Proposition 2.1}. For all integers a, b ≥ 0, and for all 1 ≤ j ≤ a + b − 2, we have

f_{a+b} = s_{j+1}f_{a+b−j} − s_{j}f_{a+b−j−1}  (2)

where

s_{j} = ∑_{i=1}^{j}(−1)^{i+j}f_{i}.

\underline{Proof}. We prove this proposition using induction on j. First, when j = 1, the right hand side of (2) is (f_{2} − f_{1})f_{a+b−1} − f_{1}f_{a+b−2} or 6f_{a+b−1} − f_{a+b−2}, which equals f_{a+b} thanks to (1).

Next, we assume

f_{a+b} = s_{j+1}f_{a+b−j} − s_{j}f_{a+b−j−1}

for j < a + b − 2. Thus, since f_{a+b−j} = 6f_{a+b−j−1} − f_{a+b−j−2}, we have

\begin{aligned}f_{a+b} & = s_{j+1}(6f_{a+b−j−1} − f_{a+b−j−2}) − s_{j}f_{a+b−j−1} \\ & = (6s_{j+1} − s_{j})f_{a+b−j−1} − s_{j+1}f_{a+b−j−2}. \end{aligned}

Then we note that by (1)

6s_{j+1} − s_{j} = 6 ∑_{i=1}^{j+1}(−1)^{i+j+1}f_{i} − ∑_{i=1}^{j}(−1)^{i+j}f_{i}

= 6(−1)^{j+2}f_{1} + 6 ∑_{i=2}^{j+1}(−1)^{i+j+1}f_{i} − ∑_{i=1}^{j}(−1)^{i+j}f_{i}

= 6(−1)^{j+2}f_{1} + 6 ∑_{i=1}^{j}(−1)^{i+j+2}f_{i+1} − ∑_{i=1}^{j}(−1)^{i+j}f_{i}

= (f_{2} − f_{1})(−1)^{j+2} + ∑_{i=1}^{j}(−1)^{i+j+2}(6f_{i+1} − f_{i})

= (f_{2} − f_{1})(−1)^{j+2} + ∑_{i=1}^{j}(−1)^{i+j+2}f_{i+2}

= (f_{2} − f_{1})(−1)^{j+2} + ∑_{i=3}^{j+2}(−1)^{i+j}f_{i}

= ∑_{i=1}^{j+2}(−1)^{i+j}f_{i}

= s_{j+2}.

Therefore, we have

\begin{aligned}f_{a+b} & = (6s_{j+1} − s_{j})f_{a+b−j−1} − s_{j+1}f_{a+b−j−2} \\ & = s_{j+2}f_{a+b−j−1} − s_{j+1}f_{a+b−j−2}, \end{aligned}

which completes the proof of Proposition 2.1.

\underline{Proposition 2.2}. For all m ≥ 1 and for all 1 ≤ c ≤ m − 1, f_{m}|f_{m+c} + f_{m−c}. \underline{Proof}. For c = 1, we know from (1) that 6f_{m} = f_{m+1}+f_{m−1}, so that f_{m}|f_{m+1}+

f_{m−1}. Next, we assume f_{m}|f_{m+c} + f_{m−c} for 1 ≤ c ≤ d for some value d < m − 1. Since

f_{m+d+1} = 6f_{m+d} − f_{m+d−1} and f_{m−d−1} = 6f_{m−d} − f_{m−d+1},

we know

\begin{aligned}f_{m+d+1} + f_{m−(d+1)} & = 6f_{m+d} − f_{m+d−1} + 6f_{m−d} − f_{m−d+1} \\ & = 6(f_{m+d} + f_{m−d}) − (f_{m+d−1} + f_{m−(d−1)}). \end{aligned}

By the induction hypothesis, the result follows.

\underline{Proposition 2.3}. For all m ≥ 1, f_{m}|s_{2m−1}.

\underline{Proof}. We see that

s_{2m−1} = ∑_{i=1}^{2m−1}(−1)^{i−1}f_{i} = f_{1} − f_{2} + f_{3} − ⋯ + (−1)^{m−1}f_{m} + ⋯ + f_{2m−1}.

Notice that this sum is centered about f_{m}, which divides itself, and that the rest of the terms can be paired in such a way that Proposition 2.2 can be applied easily.

We are now ready to prove Theorem 1.1.

\underline{Proof of Theorem 1.1}. When n = 0, the result is clear. Next, assume f_{m}|f_{(2m−1)n+m} or f_{m}|f_{2mn−n+m}. We want to prove

f_{m}|f_{(2m−1)(n+1)+m} or f_{m}|f_{2mn−n+m+(2m−1)}.

Using Proposition 2.1 with a = 2mn − n + m, b = 2m − 1, and j = 2m − 2, we have

f_{2mn−n+m+(2m−1)} = s_{2m−1}f_{2mn−n+m+1} − s_{2m−2}f_{2mn−n+m}.

From Proposition 2.3, we know f_{m}|s_{2m−1}, and from the induction hypothesis, f_{m}|f_{2mn−n+m}. The result follows.

\underline{References}

1. E. Barcucci, S. Brunetti, A. Del Lungo, and F. Del Ristoro, “A Combinatorial Interpretation of the Recurrence f_{n+1} = 6f_{n} − f_{n−1},” Discrete Mathematics, 190 (1998), 235–240.

2. J. Bonin, L. Shapiro, and R. Simion, “Some q–analogues of the Schröder Numbers Arising From Combinatorial Statistics on Lattice Paths,” J. Statist. Plann. Inference, 34 (1993), 35–55.

3. M. Newman, D. Shanks, and H. C. Williams, “Simple Groups of Square Order and an Interesting Sequence of Primes,” Acta Arithmetica, XXXVIII (1980), 129–140.

4. J. Sellers and H. Williams, “On the Infinitude of Composite NSW Numbers,” The Fibonacci Quarterly, 40 (2002), 253–254.

James A. Sellers Department of Mathematics Pennsylvania State University 107 Whitmore Laboratory University Park, PA 16802 email: sellersj@math.psu.edu