Putnam 2020, Problem B-6

Let \( n \) be a positive integer. Prove that
\[
\sum_{k=1}^{n} (-1)^{\lfloor k(\sqrt{2} - 1) \rfloor} \geq 0.
\]
(As usual, \( \lfloor x \rfloor \) denotes the greatest integer less than or equal to \( x \).)


Solution:
**First solution.** Define the sequence $\{a_k\}_{k=0}^\infty$ by $a_k = \lfloor k(\sqrt{2} - 1) \rfloor$. The first few terms of the sequence $\{(-1)^{a_k}\}$ are
$$1,1,1,-1,-1,1,1,1,-1,1,1,1,\ldots$$

Define a new sequence $\{c_i\}_{i=0}^\infty$ given by $3,2,3,2,3,2,3,\ldots$, whose members alternately are the lengths of the clusters of consecutive 1's and the lengths of the clusters of consecutive -1's in the sequence $\{(-1)^{a_k}\}$. Then for any $i$, $c_0 + \cdots + c_i$ is the number of nonnegative integers $k$ such that $\lfloor k(\sqrt{2} - 1) \rfloor$ is strictly less than $i + 1$, i.e., such that $k(\sqrt{2} - 1) < i + 1$. This last condition is equivalent to $k < \frac{i+1}{\sqrt{2} - 1}$, and we conclude that
$$c_0 + \cdots + c_i = \lfloor (i+1)(\sqrt{2} + 1) \rfloor + 1$$
$$= 2i + 3 + \lfloor (i+1)(\sqrt{2} - 1) \rfloor.$$

Thus for $i > 0$,
$$c_i = 2 + \lfloor (i+1)(\sqrt{2} - 1) \rfloor - \lfloor i(\sqrt{2} - 1) \rfloor. \tag{10}$$

Now note that $\lfloor (i+1)(\sqrt{2} - 1) \rfloor - \lfloor i(\sqrt{2} - 1) \rfloor$ is either $1$ or $0$ depending on whether or not there is an integer $j$ between $i(\sqrt{2} - 1)$ and $(i+1)(\sqrt{2} - 1)$: this condition is equivalent to $i < j(\sqrt{2} + 1) < i+1$. That is, for $i > 0$,
$$c_i = \begin{cases} 3 & \text{if } i = \lfloor j(\sqrt{2} + 1) \rfloor \text{ for some integer } j; \\ 2 & \text{otherwise;} \end{cases} \tag{11}$$

by inspection, this also holds for $i = 0$.

Now we are asked to prove that
$$\sum_{k=0}^n (-1)^{a_k} \geq 1 \tag{12}$$

for all $n \geq 1$. We will prove that if (12) holds for all $n \leq N$, then (12) holds for all $n \leq 4N$; since (12) clearly holds for $n = 1$, this will imply the desired result.

Suppose that (12) holds for $n \leq N$. To prove that (12) holds for $n \leq 4N$, it suffices to show that the partial sums
$$\sum_{i=0}^m (-1)^{c_i} \tag{13}$$

of the sequence $\{(-1)^{a_k}\}$ are positive for all $m$ such that $c_0 + \cdots + c_{m-1} < 4N + 3$, since these partial sums cover all clusters through $a_{4N}$. Now if $c_0 + \cdots + c_{m-1} < 4N + 3$, then since each $c_i$ is at least $2$, we must have $m < 2N + 2$. From (11), we see that if $m$ is odd, then
$$\sum_{i=0}^m (-1)^{c_i} = \sum_{i=0}^m (-1)^i (c_i - 2)$$
$$= \sum_{j} (-1)^{\lfloor j(\sqrt{2} + 1) \rfloor} = \sum_{j} (-1)^{a_j}$$

where the sum in $j$ is over nonnegative integers $j$ with $j(\sqrt{2} + 1) < m$, i.e., $j < m(\sqrt{2} - 1)$; since $m(\sqrt{2} - 1) < m/2 < N + 1$, $\sum_{j} (-1)^{a_j}$ is positive by the induction hypothesis. Similarly, if $m$ is even, then $\sum_{i=0}^m (-1)^{c_i} = c_m + \sum_{j} (-1)^{a_j}$ and this is again positive by the induction hypothesis. This concludes the induction step and the proof.

**Remark.** More generally, using the same proof we can establish the result with $\sqrt{2} - 1$ replaced by $\sqrt{n^2 + 1} - n$ for any positive integer $n$.

**Second solution.** For $n \geq 0$, define the function
$$f(n) = \sum_{k=1}^n (-1)^{\lfloor k(\sqrt{2} - 1) \rfloor}$$

with the convention that $f(0) = 0$.

Define the sequence $q_0,q_1,\ldots$ by the initial conditions
$$q_0 = 0, \quad q_1 = 1$$

and the recurrence relation
$$q_j = 2q_{j-1} + q_{j-2}.$$

This is OEIS sequence A000129; its first few terms are
$$0,1,2,5,12,29,70,\ldots$$

Note that $q_j \equiv j \pmod{2}$.

We now observe that the fractions $q_{j-1}/q_j$ are the convergents of the continued fraction expansion of $\sqrt{2} - 1$. This implies the following additional properties of the sequence.

- For all $j \geq 0$,
$$\frac{q_{2j}}{q_{2j+1}} < \sqrt{2} - 1 < \frac{q_{2j+1}}{q_{2j+2}}.$$

- There is no fraction $r/s$ with $s < q_j + q_{j+1}$ such that $r/s$ separates $\sqrt{2} - 1$ from $q_j/q_{j-1}$. In particular, for $k < q_j + q_{j+1}$,
$$\lfloor k(\sqrt{2} - 1) \rfloor = \left\lfloor \frac{kq_{j-1}}{q_j} \right\rfloor$$

except when $j$ is even and $k \in \{q_j,2q_j\}$, in which case they differ by $1$.

We use this to deduce a "self-similarity" property of $f(n)$.

**Lemma 1.** Let $n,j$ be nonnegative integers with $q_j \leq n < q_j + q_{j+1}$.

(a) If $j$ is even, then
$$f(n) = f(q_j) - f(n - q_j).$$

(b) If $j$ is odd, then
$$f(n) = f(n - q_j) + 1.$$

*Proof.* If $j$ is even, then
$$f(n) = f(q_j) + \sum_{k=q_j+1}^n (-1)^{\lfloor k(\sqrt{2} - 1) \rfloor}$$
$$= f(q_j) + \sum_{k=q_j+1}^n (-1)^{\lfloor kq_{j-1}/q_j \rfloor} + *$$

where $*$ equals $2$ if $n \geq 2q_j$ (accounting for the term $k = 2q_j$) and $0$ otherwise. Continuing,
$$f(n) = f(q_j) + \sum_{k=1}^{n-q_j} (-1)^{q_{j-1} + \lfloor kq_{j-1}/q_j \rfloor} + *$$
$$= f(q_j) - \sum_{k=1}^{n-q_j} (-1)^{\lfloor k(\sqrt{2} - 1) \rfloor}$$
$$= f(q_j) - f(n - q_j).$$

If $j$ is odd, then
$$f(n) = f(n - q_j) + \sum_{k=n-q_j+1}^n (-1)^{\lfloor k(\sqrt{2} - 1) \rfloor}$$
$$= f(n - q_j) - 2 + \sum_{k=n-q_j+1}^n (-1)^{\lfloor kq_{j-1}/q_j \rfloor}.$$

Since
$$\lfloor (k+q_j)q_{j-1}/q_j \rfloor \equiv \lfloor kq_{j-1}/q_j \rfloor \pmod{2},$$

we also have
$$f(n) = f(n - q_j) + \sum_{k=1}^{q_j} (-1)^{\lfloor kq_{j-1}/q_j \rfloor}.$$

In this sum, the summand indexed by $q_j$ contributes $1$, and the summands indexed by $k$ and $q_j - k$ cancel each other out for $k = 1,\ldots,q_j - 1$. We thus have
$$f(n) = f(n - q_j) + 1$$

as claimed. $\square$

From Lemma 1, we have
$$f(q_{2j}) = f(q_{2j} - 2q_{2j-1}) + 2 = f(q_{2j-2}) + 2.$$

By induction on $j$, $f(q_{2j}) = 2j$ for all $j \geq 0$; by similar logic, we have $f(n) \leq f(q_{2j}) = 2j$ for all $n \leq q_{2j}$. We can now apply Lemma 1 once more to deduce that $f(n) \geq 0$ for all $j$.

**Remark.** As a byproduct of the first solution, we confirm the equality of two sequences that were entered separately in the OEIS but conjectured to be equal: A097509 (indexed from 0) matches the definition of $\{c_i\}$, while A276862 (indexed from 1) matches the characterization of $\{c_{i-1}\}$ given by (8).

**Remark.** We can confirm an additional conjecture from the OEIS by showing that in the notation of the first solution, the sequence $a(n) = c_{n+1}$ indexed from 1 equals A082844: "Start with 3,2 and apply the rule $a(a(1) + a(2) + \cdots + a(n)) = a(n)$, fill in any undefined terms with $a(t) = 2$ if $a(t-1) = 3$ and $a(t) = 3$ if $a(t-1) = 2$." We first verify the recursion. By (10),
$$a(1) + \cdots + a(n) = c_0 + \cdots + c_{n+1} - c_0 - c_1$$
$$= \lfloor (n+2)(\sqrt{2} + 1) \rfloor - 4.$$

From (9), we see that $a(a(1) + \cdots + a(n)) + 3 = 3$. Consequently, exactly one of $a(a(1) + \cdots + a(n))$ or $a(a(1) + \cdots + a(n) + 1)$ equals $3$, and it is the former if and only if
$$\lfloor (n+2)(\sqrt{2} + 1) \rfloor - 3 = \lfloor (n+1)(\sqrt{2} + 1) \rfloor,$$

i.e., if and only if $a(n) = c_{n+1} = 3$.

We next check that the definition correctly fills in values not determined by the recursion. If $a(n) = 3$, then $a(a(1) + \cdots + a(n) + 1) = 2$ because no two consecutive values can both equal $3$; by the same token, $a(n+1) = 2$ and so there are no further values to fill in. If $a(n) = 2$, then $a(a(1) + \cdots + a(n) + 1) = 3$ by the previous paragraph; this in turn implies $a(a(1) + \cdots + a(n) + 2) = 2$, at which point there are no further values to fill in.

**Remark.** We can confirm an additional conjecture from the OEIS by showing that in the notation of the first solution, the sequence $\{c_i\}$ equals A245219. This depends on some additional lemmas.

**Lemma 2.** Let $k$ be a positive integer. Then
$$\{ i(\sqrt{2} - 1) \} < \{ k(\sqrt{2} - 1) \} \quad (i = 0,\ldots,k-1)$$

if and only if $k = q_{2j}$ or $k = q_{2j} + q_{2j-1}$ for some $j > 0$.

*Proof.* For each $j > 0$, we have
$$\frac{q_{2j-2}}{q_{2j-1}} < \frac{q_{2j}}{q_{2j+1}} = \frac{q_{2j-1} + 2q_{2j-2}}{q_{2j} + 2q_{2j-1}} < \sqrt{2} - 1 < \frac{q_{2j+1}}{q_{2j+2}} = \frac{q_{2j+1} + 2q_{2j}}{q_{2j+1} + 2q_{2j+2}} < \frac{q_{2j+1}}{q_{2j}}.$$

We also have
$$\frac{q_{2j-2}}{q_{2j-1}} < \frac{q_{2j}}{q_{2j+1}} = \frac{q_{2j-1} + 2q_{2j-2}}{q_{2j} + 2q_{2j-1}} < \frac{q_{2j-1} + q_{2j-2}}{q_{2j} + q_{2j-1}} < \frac{q_{2j+1}}{q_{2j+2}} = \frac{q_{2j+1} + 2q_{2j}}{q_{2j+1} + 2q_{2j+2}} < \frac{q_{2j+1}}{q_{2j}}.$$

Moreover, $\frac{q_{2j-1} + q_{2j-2}}{q_{2j} + q_{2j-1}}$ cannot be less than $\sqrt{2} - 1$, or else it would be a better approximation to $\sqrt{2} - 1$ than the convergent $q_{2j}/q_{2j+1}$ with $q_{2j+1} > q_{2j} + q_{2j-1}$. By the same token, $\frac{q_{2j-1} + q_{2j-2}}{q_{2j} + q_{2j-1}}$ cannot be a better approximation to $\sqrt{2} - 1$ than $q_{2j+1}/q_{2j+2}$. We thus have
$$\frac{q_{2j}}{q_{2j+1}} < \sqrt{2} - 1 < \frac{q_{2j+1}}{q_{2j+2}} < \frac{q_{2j-1} + q_{2j-2}}{q_{2j} + q_{2j-1}} < \frac{q_{2j+1}}{q_{2j}}.$$

From this, we see that
$$\{ q_{2j}(\sqrt{2} - 1) \} < \{ (q_{2j} + q_{2j-1})(\sqrt{2} - 1) \} < \{ q_{2j+2}(\sqrt{2} - 1) \}.$$

It will now suffice to show that for $q_{2j} < k < q_{2j} + q_{2j-1}$,
$$\{ k(\sqrt{2} - 1) \} < \{ q_{2j}(\sqrt{2} - 1) \}$$

while for $q_{2j} + q_{2j-1} < k < q_{2j+2}$,
$$\{ k(\sqrt{2} - 1) \} < \{ (q_{2j} + q_{2j-1})(\sqrt{2} - 1) \}.$$

The first of these assertions is an immediate consequence of the "best approximation" property of the convergent $q_{2j-1}/q_{2j}$. As for the second assertion, note that for $k$ in this range, no fraction with denominator $k$ can lie strictly between $q_{2j}/q_{2j+1}$ and $\frac{q_{2j-1} + q_{2j-2}}{q_{2j} + q_{2j-1}}$ because these fractions are consecutive terms in a Farey sequence (that is, their difference has numerator $1$ in lowest terms); in particular, such a fraction cannot be a better upper approximation to $\sqrt{2} - 1$ than $\frac{q_{2j-1} + q_{2j-2}}{q_{2j} + q_{2j-1}}$. $\square$

**Lemma 3.** For $j > 0$, the sequence $c_0,\ldots,c_{j-1}$ is palindromic if and only if
$$j = q_{2i+1} \quad \text{or} \quad j = q_{2i+1} + q_{2i+2}$$

for some nonnegative integer $i$. (That is, $j$ must belong to one of the sequences A001653 or A001541.) In particular, $j$ must be odd.

*Proof.* Let $j$ be an index for which $\{c_0,\ldots,c_{j-1}\}$ is palindromic. In particular, $c_{j-1} = c_0 = 3$, so from (9), we see that $j - 1 = \lfloor k(\sqrt{2} + 1) \rfloor$ for some $k$. Given this, the sequence is palindromic if and only if
$$\lfloor i(\sqrt{2} + 1) \rfloor + \lfloor (k-i)(\sqrt{2} + 1) \rfloor = \lfloor k(\sqrt{2} + 1) \rfloor \quad (i = 0,\ldots,k),$$

or equivalently
$$\{ i(\sqrt{2} - 1) \} + \{ (k-i)(\sqrt{2} - 1) \} = \{ k(\sqrt{2} - 1) \} \quad (i = 0,\ldots,k)$$

where the braces denote fractional parts. This holds if and only if
$$\{ i(\sqrt{2} - 1) \} < \{ k(\sqrt{2} - 1) \} \quad (i = 0,\ldots,k-1),$$

so we may apply Lemma 2 to identify $k$ and hence $j$. $\square$

**Lemma 4.** For $j > 0$, if there exists a positive integer $k$ such that
$$(c_0,\ldots,c_{j-2}) = (c_k,\ldots,c_{k+j-2}) \text{ but } c_{j-1} \neq c_{k+j-1},$$

then
$$j = q_{2i+1} \quad \text{or} \quad j = q_{2i+1} + q_{2i+2}$$

for some nonnegative integer $i$. In particular, $j$ is odd and (by Lemma 3) the sequence $(c_0,\ldots,c_{j-1})$ is palindromic.

*Proof.* Since the sequence $\{c_i\}$ consists of 2s and 3s, we must have $\{c_{j-1},c_{k+j-1}\} = \{2,3\}$. Since each pair of 3s is separated by either one or two 2s, we must have $c_{j-2} = 2$, $c_{j-3} = 3$. In particular, by (9) there is an integer $i$ for which $j - 3 = \lfloor i(\sqrt{2} + 1) \rfloor$; there is also an integer $l$ such that $k = \lfloor l(\sqrt{2} + 1) \rfloor$. By hypothesis, we have
$$\lfloor (h+l)(\sqrt{2} + 1) \rfloor = \lfloor h(\sqrt{2} + 1) \rfloor + \lfloor l(\sqrt{2} + 1) \rfloor$$

for $h = 0,\ldots,i-1$ but not for $h = i$. In other words,
$$\{ (h+l)(\sqrt{2} - 1) \} = \{ h(\sqrt{2} - 1) \} + \{ l(\sqrt{2} - 1) \}$$

for $h = 0,\ldots,i-1$ but not for $h = i$. That is, $\{ h(\sqrt{2} - 1) \}$ belongs to the interval $(0,1 - \{l(\sqrt{2} - 1)\})$ for $h = 0,\ldots,i-1$ but not for $h = i$; in particular,
$$\{ h(\sqrt{2} - 1) \} < \{ i(\sqrt{2} - 1) \} \quad (h = 0,\ldots,i-1),$$

so we may apply Lemma 2 to identify $i$ and hence $j$. $\square$

The sequence A245219 is defined as the sequence of coefficients of the continued fraction of $\sup\{b_i\}$ where $b_1 = 1$ and for $i > 1$,
$$b_{i+1} = \begin{cases} b_i + 1 & \text{if } i = \lfloor j\sqrt{2} \rfloor \text{ for some integer } j; \\ 1/b_i & \text{otherwise.} \end{cases}$$

It is equivalent to take the supremum over values of $i$ for which $b_{i+1} = 1/b_i$; by Beatty's theorem, this occurs precisely when $i = \lfloor j(2 + \sqrt{2}) \rfloor$ for some integer $j$. In this case, $b_i$ has continued fraction
$$[c_{j-1},\ldots,c_0].$$

Let $K$ be the real number with continued fraction $[c_0,c_1,\ldots]$; we must show that $K = \sup\{b_i\}$. In one direction, by Lemma 3, there are infinitely many values of $i$ for which $[c_{j-1},\ldots,c_0] = [c_0,\ldots,c_{j-1}]$; the corresponding values $b_i$ accumulate at $K$, so $K \leq \sup\{b_i\}$.

In the other direction, we show that $K \geq \sup\{b_i\}$ as follows. It is enough to prove that $K \geq b_i$ when $i = \lfloor j(2 + \sqrt{2}) \rfloor$ for some integer $j$.

- If $c_0,\ldots,c_{j-1}$ is palindromic, then Lemma 3 implies that $j$ is odd; that is, the continued fraction $[c_{j-1},\ldots,c_0]$ has odd length. In this case, replacing the final term $c_0 = c_{j-1}$ by the larger quantity $[c_{j-1},c_j,\ldots]$ increases the value of the continued fraction.

- If $c_0,\ldots,c_{j-1}$ is not palindromic, then there is a least integer $k \in \{0,\ldots,j-1\}$ such that $c_k \neq c_{j-1-k}$. By Lemma 3, the sequence $c_0,c_1,\ldots$ has arbitrarily long palindromic initial segments, so the sequence $(c_{j-1},\ldots,c_{j-1-k})$ also occurs as $c_h,\ldots,c_{h+k}$ for some $h > 0$. By Lemma 4, $k$ is even and $c_k = 3 > 2 = c_{j-1-k}$; hence in the continued fraction for $b_i$, replacing the final segment $c_{j-1-k},\ldots,c_0$ by $c_k,c_{k+1},\ldots$ increases the value.