It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
In Section 2c of Fredricksen's paper A survey of full length nonlinear shift register cycle algorithms (SIAM Review 24 (1982), 195–221), he states a result that he attributes to "Kibler, personal communication, 1972":
Theorem. The number of cycles of length $2^n-2$ in the De Bruijn graph of order $n$ is ${1\over 3}(2^{2^n-2n})(2^{n-1} + (-1)^n)$.
However, he gives only the bare outline of a proof. By appealing to the BEST theorem, he reduces the calculation to a determinant evaluation, and then simply says, "By induction, the determinant can be evaluated." However, I don't see how to do this.
Can someone explain how to evaluate the determinant, or give an alternative proof of the above fact?
