A curious Hankel determinant

Edit: following our exchange, I modify the presentation of what is now a partial result.

I will stick to your notations. For example $H_8$ is the $2^3 \times 2^3 $ Hankel matrix:

$$H_{8}:=\begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$

We are going to prove a restricted version of your result, i.e., we will prove that, for $k\geq 2$:

$$\det(H_{2^k})=1$$

complying with formula $(-1)^{\binom{2^k}{2}}=(-1)^{\tfrac{2^k(2^k-1)}{2}}=1.$

Let us set, for notational convenience, $K_n=H_{2^n}$.

$K_n$ possesses a recursive structure with the form :

$$\tag{1}K_{n+1}= \begin{pmatrix}K_{n} & J_{n}\\J_{n} & 0_{n}\end{pmatrix}$$

where $J_n$ is the anti-diagonal matrix (with ones on the secondary diagonal) and $0_{n}$ is the all-zero matrix, both of size $2^n \times 2^n$.

Now (1) allows to work by recursion for obtaining $\det(K_n)$ by using the Schur formula for $2 \times 2$ block-defined matrices :

$$M=\begin{pmatrix}A & B\\C & D\end{pmatrix} \ \ \implies \ \ \det(M)=\det(A)det(D-CA^{-1}B)$$

giving here:

$$det(K_{n+1})=\det(K_n)\det(-JK_{n}^{-1}J)=\det(K_n)\det(-I)\det(J)\det(K_{n}^{-1})\det(J)=$$

$$det(-I)det(J_n^2)\det(K_nK_{n}^{-1})=(-1)^{2^n}=\begin{cases}-1 & (n=0)\\+1& (n>0) \end{cases}$$

(where $I$ denotes the identity matrix with $2^n \times 2^n$ elements).

Explanations: $\det(J_n^2)=\det(I)=1$ and $\det(-I_k)=(-1)^k$.

---

A Matlab program for the recursive generation of matrix $K_{2^p}$ (here with $p=2$):

p=2;
K=[1];J=[1];Z=[0];
for k=1:p
   K=[K,J;J,Z]
   J=[Z,J;J,Z];
   Z=[Z,Z;Z,Z];
end;
K

Edit : I wonder if a simple solution couldn't be achieved by using [Lucas Theorem] (https://en.wikipedia.org/wiki/Lucas%27s_theorem)

Yes, there is -- but this is not really about determinants. Let me introduce some notations and state the main result.

Definition. Let $\mathbb{N}$ be the set $\left\{ 0,1,2,\ldots \right\} $. For each $i\in\mathbb{N}$ and $j\in\mathbb{N}$, we let $\left[ i,j\right] $ be the interval $\left\{ i,i+1,\ldots,j\right\} $ of $\mathbb{N}$ (this is empty when $i>j$).

For each $n\in\mathbb{N}$, we let $\left[ n\right] ^{\prime}$ be the interval $\left[ 0,n-1\right] =\left\{ 0,1,\ldots,n-1\right\} $ of $\mathbb{N}$.

Definition. Let $n\in\mathbb{N}$, and let $\sigma$ be a permutation of $\left[ n\right] ^{\prime}$. Then, $\sigma$ is said to be nimble if for each $i\in\left\{ 0,1,\ldots,n-1\right\} $, the number $i+\sigma\left( i\right) +1$ is a power of $2$.

Yes, $1$ counts as a power of $2$. The name "nimble" hints at the game of Nim (and Nim addition), but I don't have the time to figure out the exact connection.

Here is my main claim (which you conjectured):

Theorem 1. Let $n\in\mathbb{N}$.

(a) Then, there is a unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$.

(b) This permutation $\sigma_{n}$ has sign $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$.

This permutation yields your conjecture that $\det\left( H_{n}\right) =\left( -1\right) ^{n\left( n-1\right) /2}$ for each $n\in\mathbb{N}$. Indeed, if we fix $n\in\mathbb{N}$, then the determinant of the matrix $H_{n}=\left( a_{i+j}\right) _{i\in\left[ n\right] ^{\prime};\ j\in\left[ n\right] ^{\prime}}$ rewrites as \begin{align*} \det\left( H_{n}\right) & =\sum_{\sigma\text{ is a permutation of }\left[ n\right] ^{\prime}}\left( -1\right) ^{\sigma}\underbrace{a_{0+\sigma\left( 0\right) }a_{1+\sigma\left( 1\right) }\cdots a_{n-1+\sigma\left( n-1\right) }}_{\substack{= \begin{cases} 1, & \text{if }\sigma\text{ is nimble};\\ 0, & \text{if }\sigma\text{ is not nimble} \end{cases} \\\text{(by the definition of the }a_{k}\text{)}}}\\ & =\sum_{\sigma\text{ is a permutation of }\left[ n\right] ^{\prime} }\left( -1\right) ^{\sigma} \begin{cases} 1, & \text{if }\sigma\text{ is nimble};\\ 0, & \text{if }\sigma\text{ is not nimble} \end{cases} \\ & = \sum_{\sigma\text{ is a nimble permutation of }\left[ n\right] ^{\prime} }\left( -1\right) ^{\sigma} \\ & =\left( -1\right) ^{n\left( n-1\right) /2}\qquad\left( \text{by Theorem 1}\right) . \end{align*} So it remains to prove Theorem 1.

We begin with simple lemmas:

Lemma 2. Let $n$ be a positive integer. Let $k$ be a positive integer such that $2^{k-1}<n\leq2^{k}$. Let $i\in\left[ n\right] ^{\prime}$ be such that $i\geq2^{k}-n$.

(a) Then, both numbers $i$ and $2^{k}-i-1$ are elements of $\left[ n\right] ^{\prime}$, and at least one of them is $\geq2^{k-1}$.

(b) Let $\sigma$ be a nimble permutation of $\left[ n\right] ^{\prime}$. Then, $\sigma\left( i\right) =2^{k}-i-1$.

Proof of Lemma 2. (a) From $i\in\left[ n\right] ^{\prime}$, we obtain $i\leq n-1<n\leq2^{k}$, so that $2^{k}-i>0$ and thus $2^{k}-i-1\geq0$. But $i\geq2^{k}-n$, so that $i+n\geq2^{k}$ and thus $2^{k}-i\leq n$. Thus, $\underbrace{2^{k}-i}_{\leq n}-1\leq n-1$. Combining this with $2^{k} -i-1\geq0$, we obtain $2^{k}-i-1\in\left[ 0,n-1\right] =\left[ n\right] ^{\prime}$. Thus, both numbers $i$ and $2^{k}-i-1$ are elements of $\left[ n\right] ^{\prime}$ (since $i\in\left[ n\right] ^{\prime}$ by assumption). It remains to prove that at least one of them is $\geq2^{k-1}$.

Assume the contrary. Thus, none of these two numbers is $\geq2^{k-1}$. Hence, they are both $<2^{k-1}$. In other words, $i<2^{k-1}$ and $2^{k}-i-1<2^{k-1}$. From $i<2^{k-1}$, we obtain $i\leq2^{k-1}-1$ (since $i$ and $2^{k-1}$ are integers). Hence, \begin{equation} 2^{k}-1=\underbrace{i}_{\leq2^{k-1}-1}+\underbrace{2^{k}-i-1}_{<2^{k-1} }<2^{k-1}-1+2^{k-1}=\underbrace{2\cdot2^{k-1}}_{=2^{k}}-1=2^{k}-1. \end{equation} This is absurd. This contradiction shows that our assumption was wrong. Hence, the proof of Lemma 2 (a) is complete.

(b) Lemma 2 (a) shows that both numbers $i$ and $2^{k}-i-1$ are elements of $\left[ n\right] ^{\prime}$, and at least one of them is $\geq2^{k-1}$. We are thus in one of the following two cases:

Case 1: We have $i\geq2^{k-1}$.

Case 2: We have $2^{k}-i-1\geq2^{k-1}$.

Let us first consider Case 1. In this case, we have $i\geq2^{k-1}$. But the permutation $\sigma$ is nimble. Hence, the number $i+\sigma\left( i\right) +1$ is a power of $2$ (by the definition of "nimble"). In other words, $i+\sigma\left( i\right) +1=2^{m}$ for some $m\in\mathbb{N}$. Consider this $m$.

From $2^{m}=\underbrace{i}_{\geq2^{k-1}}+\underbrace{\sigma\left( i\right) }_{\geq0}+\underbrace{1}_{>0}>2^{k-1}$, we obtain $m>k-1$. Thus, $m\geq k$ (since $m$ and $k$ are integers).

On the other hand, $i\leq n-1$ (since $i\in\left[ n\right] ^{\prime}$) and $\sigma\left( i\right) \leq n-1$ (since $i\in\left[ n\right] ^{\prime}$). Hence, \begin{align*} 2^{m} & =\underbrace{i}_{\leq n-1}+\underbrace{\sigma\left( i\right) }_{\leq n-1}+1\leq\left( n-1\right) +\left( n-1\right) +1=2\underbrace{n} _{\leq2^{k}}-1\\ & \leq2\cdot2^{k}-1<2\cdot2^{k}=2^{k+1}. \end{align*} Hence, $m<k+1$, so that $m\leq k$ (since $m$ and $k$ are integers). Combining this with $m\geq k$, we obtain $m=k$. Hence, $2^{m}=2^{k}$, so that $i+\sigma\left( i\right) +1=2^{m}=2^{k}$ and thus $\sigma\left( i\right) =2^{k}-i-1$. This proves Lemma 2 (b) in Case 1.

Now, let us consider case 2. In this case, we have $2^{k}-i-1\geq2^{k-1}$. But we know that $2^{k}-i-1$ is an element of $\left[ n\right] ^{\prime}$. Hence, there exists some $j\in\left[ n\right] ^{\prime}$ such that $\sigma\left( j\right) =2^{k}-i-1$ (since $\sigma$ is a permutation of $\left[ n\right] ^{\prime}$). Consider this $j$. We have $\sigma\left( j\right) =2^{k}-i-1\geq2^{k-1}$. But the permutation $\sigma$ is nimble. Hence, the number $j+\sigma\left( j\right) +1$ is a power of $2$ (by the definition of "nimble"). In other words, $j+\sigma\left( j\right) +1=2^{m}$ for some $m\in\mathbb{N}$. Consider this $m$.

From $2^{m}=\underbrace{j}_{\geq2^{k-1}}+\underbrace{\sigma\left( j\right) }_{\geq0}+\underbrace{1}_{>0}>2^{k-1}$, we obtain $m>k-1$. Thus, $m\geq k$ (since $m$ and $k$ are integers).

On the other hand, $j\leq n-1$ (since $j\in\left[ n\right] ^{\prime}$) and $\sigma\left( j\right) \leq n-1$ (since $j\in\left[ n\right] ^{\prime}$). Hence, \begin{align*} 2^{m} & =\underbrace{j}_{\leq n-1}+\underbrace{\sigma\left( j\right) }_{\leq n-1}+1\leq\left( n-1\right) +\left( n-1\right) +1=2\underbrace{n} _{\leq2^{k}}-1\\ & \leq2\cdot2^{k}-1<2\cdot2^{k}=2^{k+1}. \end{align*} Hence, $m<k+1$, so that $m\leq k$ (since $m$ and $k$ are integers). Combining this with $m\geq k$, we obtain $m=k$. Hence, $2^{m}=2^{k}$, so that $j+\sigma\left( j\right) +1=2^{m}=2^{k}$ and thus $\sigma\left( j\right) =2^{k}-j-1$. Comparing this with $\sigma\left( j\right) =2^{k}-i-1$, we find $2^{k}-i-1=2^{k}-j-1$. Hence, $i=j$. Thus, $\sigma\left( i\right) =\sigma\left( j\right) =2^{k}-i-1$. This proves Lemma 2 (b) in Case 2.

We have now proven Lemma 2 (b) in both Cases 1 and 2. Thus, Lemma 2 (b) always holds.

Lemma 3. Let $n$ be a positive integer. Let $k$ be a positive integer such that $2^{k-1}<n\leq2^{k}$. Let $\sigma$ be a nimble permutation of $\left[ n\right] ^{\prime}$.

(a) We have $2^{k}-n<n$.

(b) The map $\sigma$ preserves the two subsets $\left[ 2^{k} -n\right] ^{\prime}$ and $\left[ 2^{k}-n,n-1\right] $ of $\left[ n\right] ^{\prime}$ (in other words, it maps each of these two subsets into itself).

(c) Let $\alpha$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n\right] ^{\prime}$, regarded as a map $\left[ 2^{k}-n\right] ^{\prime}\rightarrow\left[ 2^{k}-n\right] ^{\prime}$. Then, $\alpha$ is a nimble permutation of $\left[ 2^{k}-n\right] ^{\prime}$.

(d) Let $\beta$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n,n-1\right] $, regarded as a map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $. Then, $\beta$ is the unique order-reversing permutation of this subset (i.e., it is strictly decreasing as a map).

Proof of Lemma 3. (a) We have $2^{k}=2\cdot\underbrace{2^{k-1}} _{<n}<2n=n+n$, so that $2^{k}-n<n$. This proves Lemma 3 (a).

(b) Let $i\in\left[ 2^{k}-n,n-1\right] $. Hence, $2^{k}-n\leq i\leq n-1$. Thus, $i\in\left[ n\right] ^{\prime}$ and $i\geq2^{k}-n$. Thus, Lemma 2 (b) shows that \begin{equation} \sigma\left( i\right) =2^{k}-\underbrace{i}_{\leq n-1}-1\geq2^{k}-\left( n-1\right) -1=2^{k}-n. \end{equation} Combining this with $\sigma\left( i\right) =2^{k}-\underbrace{i}_{\geq 2^{k}-n}-1\leq2^{k}-\left( 2^{k}-n\right) -1=n-1$, we obtain $\sigma\left( i\right) \in\left[ 2^{k}-n,n-1\right] $.

Now, forget that we fixed $i$. We thus have shown that $\sigma\left( i\right) \in\left[ 2^{k}-n,n-1\right] $ for each $i\in\left[ 2^{k}-n,n-1\right] $. In other words, the map $\sigma$ preserves the subset $\left[ 2^{k}-n,n-1\right] $ of $\left[ n\right] ^{\prime}$. Since $\sigma$ is a permutation of $\left[ n\right] ^{\prime}$, we thus conclude that $\sigma$ also preserves the complementary subset $\left[ n\right] ^{\prime}\setminus\left[ 2^{k}-n,n-1\right] =\left[ 2^{k}-n\right] ^{\prime}$ of $\left[ n\right] ^{\prime}$. Thus, Lemma 3 (b) is proven.

(c) Lemma 3 (b) shows that the permutation $\sigma$ of $\left[ n\right] ^{\prime}$ preserves the subset $\left[ 2^{k}-n\right] ^{\prime}$ of $\left[ n\right] ^{\prime}$. Hence, it restricts to a permutation of this subset $\left[ 2^{k}-n\right] ^{\prime}$. Thus, $\alpha$ is a well-defined permutation of $\left[ 2^{k}-n\right] ^{\prime}$. It remains to show that $\alpha$ is nimble. But this is clear, because $\alpha$ is a restriction of the nimble permutation $\sigma$. Thus, Lemma 3 (c) is proven.

(d) Lemma 3 (b) shows that the permutation $\sigma$ of $\left[ n\right] ^{\prime}$ preserves the subset $\left[ 2^{k}-n,n-1\right] $ of $\left[ n\right] ^{\prime}$. Hence, it restricts to a permutation of this subset $\left[ 2^{k}-n,n-1\right] $. Thus, $\beta$ is a well-defined permutation of $\left[ 2^{k}-n,n-1\right] $. Each $i\in\left[ 2^{k}-n,n-1\right] $ satisfies \begin{align*} \beta\left( i\right) & =\sigma\left( i\right) \qquad\left( \text{since }\beta\text{ is a restriction of }\sigma\right) \\ & =2^{k}-i-1 \end{align*} (by Lemma 2 (b), since $i\geq2^{k}-n$); therefore, $\beta$ is the permutation of $\left[ 2^{k}-n,n-1\right] $ sending each $i$ to $2^{k}-i-1$. In other words, $\beta$ is the unique order-reversing permutation of this subset (i.e., it is strictly decreasing as a map). Thus, Lemma 3 (d) is proven.

Definition. Let $A$ and $B$ be two disjoint sets. Let $\alpha$ be a permutation of $A$. Let $\beta$ be a permutation of $B$. Then, the map \begin{equation} A\cup B\rightarrow A\cup B,\qquad x\mapsto \begin{cases} \alpha\left( x\right) , & \text{if }x\in A;\\ \beta\left( x\right) , & \text{if }x\in B \end{cases} \end{equation} is a permutation of the set $A\cup B$. This permutation is called the union of $\alpha$ and $\beta$, and is denoted by $\alpha\cup\beta$.

We are now ready to prove Theorem 1:

Proof of Theorem 1. (a) We shall prove Theorem 1 (a) by strong induction on $n$:

Fix $n\in\mathbb{N}$. Assume (as the induction hypothesis) that for each $g\in\mathbb{N}$ satisfying $g<n$, there is a unique nimble permutation $\sigma_{g}$ of $\left[ g\right] ^{\prime}$. We want to prove that there is a unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$.

If $n\leq1$, then this is obvious (because there is a unique permutation of $\left[ n\right] ^{\prime}$ in this case, and its nimbleness is trivially verified). Thus, WLOG assume that $n>1$. Thus, there exists a unique positive integer $k$ satisfying $2^{k-1}<n\leq2^{k}$ (namely, this $k$ is the smallest positive integer $\ell$ satisfying $2^{\ell}\geq n$). Consider this $k$. We have $2^{k}-n<n$ (this is proven as in Lemma 3 (a)). Hence, the induction hypothesis (applied to $g=2^{k}-n$) shows that there is a unique nimble permutation $\sigma_{2^{k}-n}$ of $\left[ 2^{k}-n\right] ^{\prime}$. Consider this $\sigma_{2^{k}-n}$.

Let $\gamma$ be the unique order-reversing permutation of the interval $\left[ 2^{k}-n,n-1\right] $ (that is, the unique strictly decreasing map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $). Explicitly, $\gamma$ is given by $\gamma\left( i\right) =2^{k}-i-1$ for each $i\in\left[ 2^{k}-n,n-1\right] $.

The permutations $\sigma_{2^{k}-n}$ and $\gamma$ are permutations of two complementary subsets of $\left[ n\right] ^{\prime}$ (namely, of the subsets $\left[ 2^{k}-n\right] ^{\prime}$ and $\left[ 2^{k}-n,n-1\right] $, respectively). Hence, their union $\sigma_{2^{k}-n}\cup\gamma$ is a well-defined permutation of $\left[ n\right] ^{\prime}$. Furthermore, this permutation $\sigma_{2^{k}-n}\cup\gamma$ is nimble.

[Proof. Let $i\in\left[ n\right] ^{\prime}$. We must prove that the number $i+\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) +1$ is a power of $2$.

If $i\in\left[ 2^{k}-n\right] ^{\prime}$, then $\left( \sigma_{2^{k}-n} \cup\gamma\right) \left( i\right) =\sigma\left( i\right) $ and thus $i+\underbrace{\sigma\left( i\right) }_{=\sigma_{2^{k}-n}\left( i\right) }+1=i+\sigma_{2^{k}-n}\left( i\right) +1$ is a power of $2$ (since $\sigma_{2^{k}-n}$ is nimble). Thus, if $i\in\left[ 2^{k}-n\right] ^{\prime }$, then we are done. Hence, we WLOG assume that $i\notin\left[ 2^{k}-n\right] ^{\prime}$. Hence, $i\in\left[ n\right] ^{\prime} \setminus\left[ 2^{k}-n\right] ^{\prime}=\left[ 2^{k}-n,n-1\right] $. Therefore, $\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) =\gamma\left( i\right) =2^{k}-i-1$ (by the definition of $\gamma$), so that $i+\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) +1=2^{k}$ is a power of $2$. This completes this proof.]

Thus, there exists at least one nimble permutation of $\left[ n\right] ^{\prime}$ (namely, $\sigma_{2^{k}-n}\cup\gamma$).

Now, let $\sigma$ be a nimble permutation of $\left[ n\right] ^{\prime}$.

Lemma 3 (b) shows that the map $\sigma$ preserves the two subsets $\left[ 2^{k}-n\right] ^{\prime}$ and $\left[ 2^{k}-n,n-1\right] $ of $\left[ n\right] ^{\prime}$.

Let $\alpha$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n\right] ^{\prime}$, regarded as a map $\left[ 2^{k}-n\right] ^{\prime}\rightarrow\left[ 2^{k}-n\right] ^{\prime}$. Lemma 3 (c) shows that $\alpha$ is a nimble permutation of $\left[ 2^{k}-n\right] ^{\prime}$. Thus, $\alpha=\sigma_{2^{k}-n}$ (since $\sigma_{2^{k}-n}$ is the unique nimble permutation $\sigma_{2^{k}-n}$ of $\left[ 2^{k}-n\right] ^{\prime}$).

Let $\beta$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n,n-1\right] $, regarded as a map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $. Lemma 3 (d) shows that $\beta$ is the unique order-reversing permutation of this subset. Thus, $\beta=\gamma$ (since the unique order-reversing permutation of this subset is $\gamma$).

The permutation $\sigma$ is the union of the permutations $\alpha$ and $\beta$ (since $\alpha$ and $\beta$ are the restrictions of $\sigma$ to two complementary subsets). In other words, $\sigma=\alpha\cup\beta$. In view of $\alpha=\sigma_{2^{k}-n}$ and $\beta=\gamma$, this rewrites as $\sigma =\sigma_{2^{k}-n}\cup\gamma$.

Now, forget that we fixed $\sigma$. We thus have shown that each nimble permutation $\sigma$ of $\left[ n\right] ^{\prime}$ satisfies $\sigma =\sigma_{2^{k}-n}\cup\gamma$. Hence, there exists at most one nimble permutation of $\left[ n\right] ^{\prime}$. Since we already know that there exists at least one such permutation, we thus conclude that there exists exactly one such permutation. In other words, there is a unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$. This completes the induction step. Hence, Theorem 1 (a) is proven.

(b) We shall prove Theorem 1 (b) by strong induction on $n$:

Fix $n\in\mathbb{N}$. Assume (as the induction hypothesis) that for each $g\in\mathbb{N}$ satisfying $g<n$, the unique nimble permutation $\sigma_{g}$ of $\left[ g\right] ^{\prime}$ has sign $\left( -1\right) ^{\sigma_{g} }=\left( -1\right) ^{g\left( g-1\right) /2}$. We want to prove that the unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$ has sign $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$.

If $n\leq1$, then this is obvious. Hence, WLOG assume that $n>1$. Thus, there exists a unique positive integer $k$ satisfying $2^{k-1}<n\leq2^{k}$ (namely, this $k$ is the smallest positive integer $\ell$ satisfying $2^{\ell}\geq n$). Consider this $k$. Notice that $k$ is positive; thus, $2^{k}$ is even.

We have $2^{k}-n<n$ (this is proven as in Lemma 3 (a)). Hence, the induction hypothesis (applied to $g=2^{k}-n$) shows that the unique nimble permutation $\sigma_{2^{k}-n}$ of $\left[ 2^{k}-n\right] ^{\prime}$ has sign \begin{equation} \left( -1\right) ^{\sigma_{2^{k}-n}}=\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}. \end{equation}

Let $\gamma$ be the unique order-reversing permutation of the interval $\left[ 2^{k}-n,n-1\right] $ (that is, the unique strictly decreasing map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $). Explicitly, $\gamma$ is given by $\gamma\left( i\right) =2^{k}-i-1$ for each $i\in\left[ 2^{k}-n,n-1\right] $.

A well-known fact says the following: If $m\in\mathbb{N}$, and if $M$ is an $m$-element set of integers, then the unique order-reversing permutation of the set $M$ has sign $\left( -1\right) ^{m\left( m-1\right) /2}$. Applying this to $m=2n-2^{k}$ and $M=\left[ 2^{k}-n,n-1\right] $, we conclude that the unique order-reversing permutation of the set $\left[ 2^{k}-n,n-1\right] $ has $\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k} -1\right) /2}$. Since this permutation is $\gamma$, we thus have proven that \begin{equation} \left( -1\right) ^{\gamma}=\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}. \end{equation}

In the proof of Theorem 1 (a), we have shown that each nimble permutation $\sigma$ of $\left[ n\right] ^{\prime}$ satisfies $\sigma=\sigma_{2^{k} -n}\cup\gamma$. Applying this to $\sigma=\sigma_{n}$, we conclude that $\sigma_{n}$ satisfies $\sigma_{n}=\sigma_{2^{k}-n}\cup\gamma$.

But if $A$ and $B$ are two disjoint finite sets, and if $\alpha$ and $\beta$ are permutations of $A$ and $B$ (respectively), then the union $\alpha \cup\beta$ of $\alpha$ and $\beta$ has sign $\left( -1\right) ^{\alpha \cup\beta}=\left( -1\right) ^{\alpha}\left( -1\right) ^{\beta}$. Applying this to $A=\left[ 2^{k}-n\right] ^{\prime}$, $B=\left[ 2^{k}-n,n-1\right] $, $\alpha=\sigma_{2^{k}-n}$ and $\beta=\gamma$, we conclude that the union $\sigma_{2^{k}-n}\cup\gamma$ has sign \begin{align*} \left( -1\right) ^{\sigma_{2^{k}-n}\cup\gamma} & =\underbrace{\left( -1\right) ^{\sigma_{2^{k}-n}}}_{=\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}}\underbrace{\left( -1\right) ^{\gamma} }_{=\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}}\\ & =\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}\\ & =\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}\\ & =\left( -1\right) ^{n\left( n-1\right) /2} \end{align*} (since \begin{equation} \left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2\equiv n\left( n-1\right) /2\operatorname{mod}2 \end{equation} (because \begin{align*} & \left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k} \right) \left( 2n-2^{k}-1\right) /2-n\left( n-1\right) /2\\ & =\left( n-2^{k}\right) \underbrace{\left( 2n-2^{k}\right) }_{\substack{\equiv0\operatorname{mod}2\\\text{(since }2^{k}\text{ is even)} }}\equiv0\operatorname{mod}2 \end{align*} )). In view of $\sigma_{n}=\sigma_{2^{k}-n}\cup\gamma$, this rewrites as $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$. So we have proven that the unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$ has sign $\left( -1\right) ^{\sigma_{n} }=\left( -1\right) ^{n\left( n-1\right) /2}$. This completes the induction step. Hence, Theorem 1 (b) is proven.

Remark. Our recursive proof of Theorem 1 (a) can be used to show that the permutation $\sigma_{n}$ is an involution (i.e., it equals its own inverse) and has no fixed points except possibly $1$ (because the permutation $\gamma$ is an order-reversing permutation of a set of even size, and such permutations never have fixed points). Thus, the cycle type of $\sigma_{n}$ is $\left( \underbrace{2,2,\ldots,2}_{n/2\text{ times}}\right) $ when $n$ is even, and $\left( \underbrace{2,2,\ldots,2}_{\left(n-1\right)/2\text{ times}},1\right) $ otherwise. This gives another way of computing the sign of $\sigma_{n}$, and thus of proving Theorem 1 (b).