# Problems regarding $\{x_n \}$ defined by $x_1=1$; $x_n$ is the smallest distinct natural number such that $x_1+...+x_n$ is divisible by $n$.

Let me denote a sequence of distinct natural numbers by $x_n$ whose terms are determined as follows: $x_1$ is $1$ and $x_2$ is the smallest distinct natural number $n$ such that $x_1+x_2$ is divisible by $2$, which is $3$. Similarly $x_n$ is the smallest distinct natural number such that $x_1+...+x_n$ is divisible by $n$. Thus $x_1=1$, $x_2=3$, $x_3=2$.

Now the problem is to show that (i) $x_n$ is surjective (ii) $x_{(x_n)}$ is $n$, for example $x_2=3$ and $x_3=2$

• Maybe because $1$ and $1$ are not distinct ;) Feb 5, 2013 at 2:24
• @Clayton I also missed it at the first read. Feb 5, 2013 at 2:25
• Spoiler: the sequence is oeis.org/A019444 Feb 5, 2013 at 2:29
• Shouldn't condition (ii) be $x_{(x_n)} = n$?
– EuYu
Feb 5, 2013 at 2:35
• Note (ii) implies (i).
– user14972
Feb 6, 2013 at 8:48

As other posters have noticed, this is closely related to the golden ratio $\varphi = \frac{1+\sqrt{5}}{2}$.

$\frac{1}{\varphi}+\frac{1}{\varphi ^2}=1$, so we can partition the natural numbers greater than 1 into numbers of the forms $\lceil {n \varphi} \rceil, \lceil {n \varphi ^2} \rceil$. (Add 1 to the beatty sequences)

Define $a_1=1, a_{\lceil {n \varphi} \rceil}=\lceil {n \varphi ^2} \rceil, a_{\lceil {n \varphi ^2} \rceil}=\lceil {n \varphi} \rceil$. Clearly $a_{a_n}=n$.

That's where the next crucial observation that $\sum\limits_{i=1}^{n}{a_i}=n \lceil{\frac{n}{\varphi}} \rceil$ comes in.

We proceed by induction on $n$ to show that $\sum\limits_{i=1}^{n}{a_i}=n \lceil{\frac{n}{\varphi}} \rceil$ and that $a_n$ is the smallest integer satisfying the divisiblity relation $n \mid \sum\limits_{i=1}^{n}{a_i}$.

When $n=1$, we have $1=1 \lceil{\frac{1}{\varphi}} \rceil$, which is true. When $n=2$, we have $1+3=2 \lceil{\frac{2}{\varphi}} \rceil$, which is true.

Suppose it holds for $n=k \geq 2$. Then $\sum\limits_{i=1}^{k}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil$. Consider 2 cases:

Case 1: $k+1=\lceil{m \varphi} \rceil$ for some $m \in \mathbb{Z}^+$. Then $a_{k+1}=\lceil{m \varphi ^2} \rceil=m+\lceil{m \varphi} \rceil=m+k+1$.

Now $k+1=m \varphi +1- \{m \varphi \}$ so $m-1<m-\frac{\{m \varphi \}}{\varphi}=\frac{k}{\varphi}<m<m+\frac{1-\{m \varphi \}}{\varphi}=\frac{k+1}{\varphi}<m+1$. Thus $\lceil{\frac{k}{\varphi}} \rceil=m, \lceil{\frac{k+1}{\varphi}} \rceil=m+1$.

$\sum\limits_{i=1}^{k+1}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil+a_{k+1}=km+(m+k+1)=(k+1)(m+1)=(k+1) \lceil{\frac{k+1}{\varphi}} \rceil$.

Minimality: Note that $a_{k+1}=m+k+1<2(k+1)$, and because we have a partition, $a_{k+1} \not =a_i \, \forall i$, so it suffices to show that $a_i=m$ for some $i$ with $1 \leq i \leq k$, or equivalently, $a_m \leq k$. If $m=\lceil{b \varphi ^2 } \rceil$ for some $b \in \mathbb{Z}^+$, we are done since $a_m<m \leq k$. Otherwise $m=\lceil{b \varphi} \rceil$ for some $b \in \mathbb{Z}^+$, so $a_m=\lceil{b \varphi ^2 } \rceil \leq \lceil{\lceil b \varphi \rceil \varphi } \rceil=\lceil{m \varphi } \rceil=k+1$. Since $k+1=\lceil{m \varphi} \rceil \not =\lceil{b \varphi ^2 } \rceil = a_m$ (Partition), we now have the desired inequality $a_m \leq k$.

Case 2: $k+1=\lceil{m \varphi ^2} \rceil=m+\lceil{m \varphi} \rceil$ for some $m \in \mathbb{Z}^+$. Then $a_{k+1}=\lceil{m \varphi} \rceil=k+1-m$.

Now $k+1=m \varphi ^2 +1-\{m \varphi ^2 \}$.

As we have a partition, $k+1$ cannot be written in the form $\lceil{i \varphi} \rceil$. Thus $\exists c \in \mathbb{Z}^+$ such that $\lceil{c \varphi} \rceil<k+1<\lceil{(c+1) \varphi} \rceil$. (Since $k>1$.)

This gives $\lceil{c \varphi} \rceil=k, \lceil{(c+1) \varphi} \rceil=k+2$.

Thus: $k=c \varphi +1-\{c \varphi \}, k+2=(c+1) \varphi +1-\{(c+1) \varphi \}$, so \begin{align} c<c+\frac{1-\{c \varphi \}}{\varphi}=\frac{k}{\varphi}=m \varphi -\frac{\{m \varphi ^2 \}}{\varphi}<m \varphi & <m \varphi +\frac{1-\{m \varphi ^2 \}}{\varphi} \\ & =\frac{k+1}{\varphi} \\ & =c+1-\frac{\{(c+1) \varphi \}}{\varphi} \\ & <c+1 \end{align}

We get $\lceil \frac{k}{\varphi} \rceil =\lceil m \varphi \rceil =\lceil \frac{k+1}{\varphi} \rceil =c+1$, so $k+1=m+c+1, a_{k+1}=c+1$.

$\sum\limits_{i=1}^{k+1}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil +a_{k+1}=k(c+1)+(c+1)=(k+1)(c+1)=(k+1) \lceil{\frac{k+1}{\varphi}} \rceil$

Minimality: Also note that $a_{k+1}=k+1-m<k+1$, so $a_{k+1}$ is the smallest integer satisfying the divisibility relation, and because we have a partition, $a_{k+1} \not =a_i \, \forall i$.

We are thus done by induction. Now, since $x_n$ is unique and $a_n$ satisfies the given conditions, $x_n=a_n \, \forall n \in \mathbb{Z}^+$ and we are done. Both i) $x_n$ is surjective and ii) $x_{x_n}=n$ follow trivially.

• +1 Nice solution, which I refused to read before finishing my own, in order not to be influenced. Nevertheless there are significant similarities, and maybe I could have done everything without shifting down the sequence, and without getting too bad formulae. Just one minor remark, I was a bit surprised by the "Now that..." in Case 1, which comes after establishing what is needed for the induction, so it is not obvious why it is there. It turns out to be arguing minimality, but that was not part of the induction statement. Feb 21, 2013 at 14:35
• Yes well, it turned out that it was easier to prove minimality within the induction framework, so that I didn't have to define all the variables again. I'll edit it to make it clearer. Feb 21, 2013 at 14:54

I think it is inevitable here to just pose an expression for the solution and then prove that it satisfies the requirements, rather than deduce the solution directly form the requirements. So I'll use the form of the solution that was suggested; on the other hand I will prove everything about it directly rather than refer to theory.

The question discriminates against $0$, denying it citizenship of the natural numbers, and this bias (for me) complicates both formulae and understanding. Therefore I'll adapt the question as follows by first proclaiming $\def\N{\mathbf N}0\in\N$ (naturalisation of $0$), and then shifting everything one step down: $a_i=x_{i+1}-1$ for all $i\in\N$. Then the following formulation is clearly equivalent to the question: the sequence $(a_i)_{i\in\N}$ is determined the requirement that each $a_i\in\N$ is minimal such that $a_i\neq a_j$ for $0\leq j<i$, and $a_0+a_1+\ldots+a_i$ is divisible by $i+1$ (in particular one has $a_0=0$). Show that the map $i\mapsto a_i$ is an involution of $\N$, in other words $a_{a_i}=i$ for all $i\in\N$ (this of course implies that the map is surjective).

I will use floor and ceiling functions extensively; also I'll denote the complementary fractional part $\def\dn#1{\lfloor#1\rfloor}\def\up#1{\lceil#1\rceil}\up x-x$ of a real number $x$ by $\def\cfr#1{\operatorname{cf}(#1)}\cfr x$, and the golden ratio by $\phi$. The latter satisfies $1+\phi=\phi^2$ and therefore also $1/\phi+1=\phi$ and $1/\phi^2+1/\phi=1$, which identities will often be used without mention.

For an integer $k>0$ two complementary conditions will be important. The condition denoted $\def\lo{\operatorname{low}}\lo(k)$ will be said to hold if $$\cfr{k\phi}=\cfr{k/\phi}<1/\phi=1-1/\phi^2 \quad\text{or equivalently}\quad \cfr{k/\phi^2}>1/\phi^2=1-1/\phi$$ while the condition denoted $\def\hi{\operatorname{high}}\hi(k)$ will be said to hold if $$\cfr{k\phi}=\cfr{k/\phi}>1/\phi=1-1/\phi^2 \quad\text{or equivalently}\quad \cfr{k/\phi^2}<1/\phi^2=1-1/\phi$$ (the equivalences hold because $\cfr{k\phi}+\cfr{k/\phi^2}=1$). The cases are mutually exclusive, and equality cannot happen since that would mean $(k+1)/\phi\in\mathbf N$, which is impossible because $\phi$ is irrational.

When $\lo(l)$, then putting $n=\up{l/\phi}$ one has $\cfr{l/\phi}=n-l/\phi<1/\phi$, and so $n\phi-l=\phi(n-l/\phi)<1$ whence $l=\dn{n\phi}$; conversely $\lo(\dn{n\phi})$ holds for every integer $n>0$. Similarly when $\hi(h)$, then putting $n=\up{h/\phi^2}$ one has $\cfr{h/\phi^2}=n-h/\phi^2<1/\phi^2$, so $n\phi^2-h=\phi^2(n-h/\phi^2)<1$ whence $h=\dn{n\phi^2}$; conversely $\hi(\dn{n\phi^2})$ holds for every integer $n>0$.

Now define $(a_i)_{i\in\N}$ explicitly by $$a_i= \begin{cases} 0 & \text{if i=0,} \\ \up{i\phi}=i+\up{i/\phi} & \text{if \lo(i),} \\ \dn{i/\phi}=i-\up{i/\phi^2} & \text{if \hi(i).} \\ \end{cases}$$ Writing indices $l$ with $\lo(l)$ as $l=\dn{n\phi}$ we get $a_l=l+n=\dn{n\phi+n}=\dn{n\phi^2}$. Similarly writing indices $h$ with $\hi(h)$ as $h=\dn{n\phi^2}$, we get $a_h=h-n=\dn{n\phi^2-n}=\dn{n\phi}$. We see that $$a_{\dn{n\phi}}=\dn{n\phi^2} \quad\text{and}\quad a_{\dn{n\phi^2}}=\dn{n\phi} \qquad\text{for all n\in\N,}$$ and since this covers all cases, clearly $i\mapsto A_i$ is an involution of $\N$.

On to the divisibility condition, which follows from the following stronger fact. Although straightforward by induction, it does not really give any deep understanding why this divisibility holds.

Lemma 1 For all $k\in\N$ one has $\sum_{i<k}a_i=k\dn{k/\phi}$.

Proof by induction on $k$. For $k=0$ the sum is empty and the right hand side is $0$. Now assume the lemma for $k$, deduce it for $k+1$. If $\hi(k)$, then $\phi\up{k/\phi}-k>1$ whence $\up{k/\phi}>(k+1)/\phi$ and $\dn{(k+1)/\phi}=\dn{k/\phi}$; also $a_k=\dn{k/\phi}$ in this case, and so $$\sum_{i\leq k}a_i=k\dn{k/\phi}+\dn{k/\phi} =(k+1)\dn{k/\phi}=(k+1)\dn{(k+1)/\phi}.$$ If on the other hand $\lo(k)$, then $\phi\up{k/\phi}-k<1$ whence $\up{k/\phi}<(k+1)/\phi$ and $\dn{(k+1)/\phi}=\dn{k/\phi}+1$; also $a_k=\up{k\phi}$ in this case, and so $$\sum_{i\leq k}a_i=k\dn{k/\phi}+\up{k\phi} =k\dn{k/\phi}+\dn{k/\phi}+1+k=(k+1)(\dn{k/\phi}+1)=(k+1)\dn{(k+1)/\phi}.$$

Finally, to show that each $a_i$ is the minimal number to satisfy the requirements of injectivity and divisibility, the following will be used.

Lemma 2 Whenever $0\leq i<\dn{k/\phi}$ one has $i\in\{a_0,a_1,\ldots,a_{k-1}\}$; moreover $\dn{k/\phi}\in\{a_0,a_1,\ldots,a_{k-1}\}$ holds if and only if $\lo(k)$.

Proof. From $i\leq\dn{k/\phi}-1$ and $a_i\in\{\up{i\phi},\dn{i/\phi}\}$ it follows (using $\phi>1$) that $a_i<k$, so $i=a_{a_i}\in\{a_0,a_1,\ldots,a_{k-1}\}$. Similarly for $i=\dn{k/\phi}$ one gets $a_i\leq k$, so we will have $\dn{k/\phi}\in\{a_0,a_1,\ldots,a_{k-1}\}$ unless $a_i=k$. But $a_i=k=a_{a_k}$ means that $i=a_k$ while we have $i<k$, so this can only occur if $a_k<k$, that is if $\hi(k)$; conversely if $\hi(k)$ then $i=\dn{k/\phi}=a_k$ and indeed $a_i=k$.

Now to wrap everything up, the sequence $(a_i)_{i\in\N}$ defines an involution of $\N$ that by lemma $1$ satisfies the divisibility condition. To show that each $a_k$ is minimal to satisfy the divisibility condition and distinctness from previous values $a_i$, note first that unless $\lo(k)$ holds, the value $a_k=\dn{k/\phi}<k+1$ is the first one in its congruence class modulo $k+1$, so divisibility alone shows it is minimal. When $\lo(k)$ does hold, lemma $2$ shows that all values $i\leq\dn{k/\phi}$ are already present among the previous values $a_0,a_1,\ldots,a_{k-1}$. But in this case $a_k=\up{k\phi}=\dn{k/\phi}+k+1$ is the second one in its congruence class modulo $k+1$, after the forbidden value $\dn{k/\phi}$, so one has minimality here as well.

Addendum Lemma 2 was only used for a small part above (just the case $i=\dn{k/\phi}$). However its full strength is useful to prove that the pairs $(k,a_k)$ also form the set of cold positions (safe pairs, losing positions) in the game of Wijthoff's Nim, where players take turns modifying a pair of natural numbers, decreasing either one of them, or both by the same amount, and a player incapable of moving (in position $(0,0)$) loses. Positions are classified inductively as cold/hot by: $(0,0)$ is cold; any position from which one can move to a cold position is hot; any position where one can move only to hot positions is cold. The fact that $\{\,(k,a_k)\mid k\in\N\,\}$ is the set of cold positions for this game translates into the following statement.

Proposition $(a_i)_{i\in\N}$ is the lexicographically minimal sequence for which the map $i\mapsto a_i$ is injective $\N\to\N$, and the map $i\mapsto a_i-i$ is injective $\def\Z{\mathbf Z}\N\to\Z$.

Proof. Since $\dn{n\phi^2}-\dn{n\phi}=n$, one easily sees that both maps are in fact bijections. Establishing minimality requires a bit more work. Lemma 2 shows that when $\hi(k)$ holds, the value $a_k=\dn{k/\phi}$ is the first value not yet used. For the case $\lo(k)$, first observe that the values $a_i-i$ for $0\leq i<k$ form a contiguous segment of $\Z$: the value $k=0$ occupies $0$, the values $0<l<k$ with $\lo(l)$ are $l=\dn{n\phi}$ running through $0<n<k/\phi$ and occupy the corresponding positive values $\dn{n\phi^2}-\dn{n\phi}=n$, while the values $0<h<k$ with $\hi(h)$ are $h=\dn{n\phi^2}$ running through $0<n<k/\phi^2$, and occupy the corresponding negative values $\dn{n\phi}-\dn{n\phi^2}=-n$. Thus there are $k$ successive values $a_i-i$ that are forbidden for $a_k-k$, and the actual value $a_k=\up{k\phi}$ occupies the first positive free value $\up{k\phi}-k=\up{k/\phi}$. This means that to prove minimality in this case, it suffices to exclude as candidates for $a_k$ the values up to $a_k-(k+1)=\up{k\phi}-k-1=\dn{k/\phi}$ inclusive, but this is just what lemma 2 does.

• Just one more thing, I should have mentioned that with the indicated shift it becomes sequence oeis.org/A002251, where the comment by Amarnath Murthy, Aug 16 2002, shows that this interpretation was indeed known. This other reference for the original sequence of the question (mentioned in OEIS A0194440 that was linked to by Gerry Meyerson) even geos back to 1996. Feb 21, 2013 at 14:16
• (cold, hot) is more familiar as (losing, winning) positions for the player required to move.
– zyx
Feb 21, 2013 at 15:35
• Great read, as usual! I just have some trouble understanding the proof of the Proposition in the Addendum. Why is the second map ($i\mapsto a_i-i$) a bijection? And what do you mean by "a value [...] occupies a value [...]"? Mar 14, 2013 at 5:57
• @darijgrinberg If $n\geq0$ then $n=a_i-i$ for $i=\lfloor n\phi\rfloor$, while if $n<0$ then $n=a_i-i$ for $i=\lfloor-n\phi^2\rfloor$, and this covers all values $i\in\mathbf N$. Since the proposition requires $a_i-i\neq a_j-j$ for $i\neq j$, we can think of $a_i$ as occupying the diagonal $\{(j,j+k):j\in\mathbf Z\}$ containing $(i,a_i)$ and associated to the value $k=a_i-i$, so I say $a_i$ "occupies" that value of $k$ (for other values $a_j-j$, as these are forbidden). Mar 14, 2013 at 7:12
• Thanks! Just in case you want to edit the comment: You meant $i=\left\lfloor -n\phi^2\right\rfloor$, not $i=\left\lfloor n\phi^2\right\rfloor$. And in the proof itself, $0 < n < h/\phi^2$ should be $0 < n < k/\phi^2$. Mar 14, 2013 at 7:13

This isn’t even a start on a solution; it’s merely some observations that might be useful (or at least of interest) and that are far too long for a comment.

I’ll write $x(n)$ for $x_n$. Something very interesting happens if we write out $n$ and $x(n)$ in a modified Zeckendorf notation. The modification is that I will write

$$n=\sum_{k\ge 1}e_kF_k\;,$$

where each $e_k\in\{0,1\}$, and if the standard representation, which does not use $F_1$, has $e_2=1$, I permit both $e_2=1,e_1=0$ and $e_2=0,e_1=1$. The choice will not, however, be random.

First, here are the first $19$ values of $x(n)$, marked up to show that to this point there is no counterexample to the claim that $x\big(x(n)\big)=n$ for $n\in\Bbb Z^+$.

$$\begin{array}{r} n:&1&\color{red}{2}&\color{red}{3}&\color{blue}{4}&\underline{5}&\color{blue}{6}&\color{green}{7}&\underline{8}&\color{cyan}{9}&\color{magenta}{10}&\color{green}{11}&\color{purple}{12}&\tiny{13}&\color{cyan}{14}&\tiny{15}&\color{magenta}{16}&\tiny{17}&\tiny{18}&\color{purple}{19}\\ x_n:&1&\color{red}{3}&\color{red}{2}&\color{blue}{6}&\underline{8}&\color{blue}{4}&\color{green}{11}&\underline{5}&\color{cyan}{14}&\color{magenta}{16}&\color{green}{7}&\color{purple}{19}&\tiny{21}&\color{cyan}{9}&\tiny{24}&\color{magenta}{10}&\tiny{27}&\tiny{29}&\color{purple}{12} \end{array}$$

Here is the same table in modified Zeckendorf notation:

$$\begin{array}{r|r|r|r|c|c} n&x(n)&n_{\text{Zeck}}&x(n)_{\text{Zeck}}&\text{Shift}&\text{Fibonacci numbers}\\ \hline 1&1&10&1&\to&F_2,F_1\\ 2&3&100&1000&\leftarrow&F_3,F_4\\ 3&2&1000&100&\to&F_4,F_3\\ 4&6&1001&10010&\leftarrow\\ 5&8&10000&100000&\leftarrow&F_5,F_6\\ 6&4&10010&1001&\to\\ 7&11&10100&101000&\leftarrow\\ 8&5&100000&10000&\to&F_6,F_5\\ 9&14&100001&1000010&\leftarrow\\ 10&16&100100&1001000&\leftarrow\\ 11&7&101000&10100&\to\\ 12&19&101001&1010010&\leftarrow\\ 13&21&1000000&10000000&\leftarrow&F_7,F_8\\ 14&9&1000010&100001&\to\\ 15&24&1000100&10001000&\leftarrow\\ 16&10&1001000&100100&\to\\ 17&27&1001001&10010010&\leftarrow\\ 18&29&1010000&10100000&\leftarrow\\ 19&12&1010010&101001&\to \end{array}$$

The choice of $F_1$ or $F_2$ in the representation of $n$ is determined by the direction of shift. If we replace $\to$ by $0$ and $\leftarrow$ by $1$, the Shift column becomes

$$0101101011011010110\;,$$

which is the beginning of the Fibonacci word, OEIS A096270, that is the fixed point of the map $0\mapsto01,1\mapsto011$.

• The following reference may be of interest: Robert Silber, Wythoff's Nim and Fibonacci Representations, Fibonacci Quarterly 15-1 (1977) pp 85-88. (Also you probably mean "Fibonacci word" rather than "Fibonacci sequence".) Feb 21, 2013 at 12:30
• @Marc: Thanks very much for the reference. (And yes, I did mean word; apparently my fingers have learnt Fibonacci sequence too well!) Feb 21, 2013 at 12:33

Not an answer, but it might help somebody. I can't prove this, it is observation. With $\phi = \frac {1+\sqrt 5}2$, the naturals greater than $1$ are partitioned into pairs $\lceil n\phi \rceil$ and $\lceil n\phi^2 \rceil$. This is a partitioning as $\frac 1\phi + \frac 1{\phi^2}=1$. Then $a_{\lceil n\phi \rceil}=\lceil n\phi^2 \rceil$ and $a_{\lceil n\phi^2 \rceil}=\lceil n\phi \rceil$. The gap between them the elements of the pair is $n$, as $\phi^2=1+\phi$. I can't relate this to the divisibility test.

• The corresponding Beatty sequences also occur in the solution of Wythoff's game; perhaps there's a connection? See also the corresponding OEIS sequences A000201 and A001950. Feb 5, 2013 at 18:05

See this paper, A Curious Bijection on Natural Numbers by B. J. Venkatachala in Journal of Integer Sequences, Vol. 12 (2009).

Here are some interesting patterns:

The sequence

$$a_n = \begin{cases} x_n & x_n < n \\ x_n - n & x_n \geq n \end{cases}$$

satisfies $a_{n+1} - a_n \in \{ 0, 1 \}$.

If $n_i$ is the sequence of indices where $x_{n_i} \geq {n_i}$, then $x_{n_i} = n_i + i$. (starting with $n_0 = 1$)

If $x_n < n$, then $x_{n+1} = (n+1) + x_n$

Here are some more observations that might point towards a more elementary solution. Let $X_n$ denote $\sum_{i=1}^n x_n$. We have the following values:

$$\begin{array}{rrlrr} n & x_n & & X_n & X_n/x_n \\ 1 & 1 & & 1 & 1 \\ 2 & \not1 & 3 & 4 & 2 \\ 3 & 2 & & 6 & 2 \\ 4 & \not2 & 6 & 12 & 3 \\ 5 & \not3 & 8 & 20 & 4 \\ 6 & 4 & & 24 & 4 \\ 7 & \not4 & 11 & 35 & 5 \\ \end{array}$$

Here I have written all of the candidates for $x_n$ and crossed out the non-unique ones. Note that the sequence of candidates seems to be the same as the sequence of factors on the right. Certainly $X_{n-1}/(n-1)$ is a candidate for $x_n$, since $X_{n-1}=a(n-1)$ gives $X_{n-1}+ X_{n-1}/(n-1) =an$. If we knew $x_n < 2n$ then we could prove both that it it the smallest candidate and that you need to add at most one copy of $n$. This would lead to surjectivity since the factors in the right column would go up by at most 1.

That seems true but I can't prove it.