Prove that this sequence is not periodic 
A sequence $a_1,a_2,a_3,\ldots$ is defined recursively by $a_1 = 1$ and $a_{2^k+j} = -a_j \text{ } (j = 1,2,\ldots,2^k)$. Prove that this sequence is not periodic.

We see that $$A(x) = \sum_{n \ge 0} a_n x^n = x(1 - x)(1 - x^2)(1 - x^4) \cdots.$$ Now for the sequence to be periodic, would $A(x)$ have to be representable as a rational function? How would we prove that? In that case we see that $A(x)$ can't be a rational function since it is $0$ at infinitely many points.
 A: If the sequence were $T$-periodic, multiplying $A(x)$ by $x^T-1$ would give you a polynomial, and so yes, $A(x)$ would be a rational fraction.
A: This can be shown directly, without any side trips through rational functions, generating functions, or infinite products.
We'll write $N(x)$ for the number of $1{s}$ in the binary representation of $x.$
First, we use mathematical induction to show that, for all integers $n\ge 1,$ \begin{align}a_n&=(-1)^{N(n-1)}\\&=\begin{cases}1,&\text{ if }n-1\text{ written in binary has an even number of }1\text{s},
\\-1,&\text{ if }n-1\text{ written in binary has an odd number of }1\text{s}.\end{cases}\end{align}
[This uses strong induction.  The basis $a_1=1$ is given.  For $n\gt 1,$ assume that $a_k=(-1)^{N(k-1)}$ for all $k\lt n.$ Let $d$ be the number of binary digits in $n-1.$ Then $n-1-2^{d-1}$ in binary is the same as $n-1$ with its leftmost digit changed from $1$ to $0;$ so $N(n-1-2^{d-1})=N(n-1)-1.$ We have $2^{d-1} \le n-1 \le 2^d-1,$ so $2^{d-1}+1 \le n \le 2^d.$ It follows that $$a_n=-a_{n-2^{d-1}}=-(-1)^{N(n-2^{d-1}-1)}=-(-1)^{N(n-1)-1}=(-1)^{N(n-1)},$$ completing the induction proof.]
Now let $p$ be any positive integer.  We'll show that the sequence $(a_n)_{n\in \mathbb{Z}^+}$ can't be periodic with period $p.$
Let $d$ be the number of binary digits in $p;$ we know that $d\ge 1.$   
Case 1: $N(p)$ is odd.
Then $2^d+p$ in binary is $1$ followed by the digits of $p.$  So $N(2^d)=1,$ but $N(2^d+p) = 1 + N(p),$ which is even.  It follows that $a_{2^d+1}=-1,$ but $a_{2^d+1+p}=1.$
Case 2: $N(p)$ is even.
Then $2^{d-1}+p$ in binary is $10$ followed by all but the leftmost digit of $p$ (that omitted digit is $1,$ being the leftmost digit). So $N(2^{d-1})=1,$ but $N(2^{d-1}+p)=N(p).$ which is is even. It follows that $a_{2^{d-1}+1}=-1,$ but $a_{2^{d-1}+1+p}=1.$
$$ $$
In either case, we've found a positive integer $k$ such that $a_k\ne a_{k+p}.$ So the sequence can't be periodic with period $p.$
