4
$\begingroup$

Prove or refute: $a[n]=\lfloor(n+1)\pi\rfloor-\lfloor n\pi\rfloor$ is periodic.

This sequence looks periodic, starting with ${3, 3, 3, 3, 3, 3, 4, \,3, 3, 3, 3, 3, 3, 4,\, 3, 3, 3, 3, 3, 3, 4,\dots}$. After a while, there is a sequence of seven threes: $\dots, 3, 3, 3, 3, 3, 3, 3, 4,\dots$ which disproves the period being $7$.

However, I believe it's not periodic, not even for larger periods. How could I prove it?

  • 0
    You could try to prove that $[(n+1)x]-[nx]$ is periodic if and only if $x$ is rational.2012-11-04

1 Answers 1

4

Suppose that $a[n]$ is periodic with period $q$. Observe that the $\sum_{m=0}^{n-1} a[m] = \lfloor n\pi \rfloor$, as the sum telescopes. Let $p=\lfloor q\pi \rfloor=\sum_{m=0}^{q-1} a[m]$, so $p$ is an integer. Then for all positive integers $k$,

$\lfloor kq\pi \rfloor=\sum_{m=0}^{kq-1} a[m]=\sum_{i=0}^{k-1} \sum_{j=0}^{q-1} a[qi+j]=\sum_{i=0}^{k-1} \sum_{j=0}^{q-1} a[j]=k \sum_{j=0}^{q-1} a[j]=kp$.

(The third term is obtained by dividing each $m$ in the second term by $q$ with quotient $i$ and remainder $j$). By the definition of $\lfloor x \rfloor$, we have that for all positive integers $k$,

$kp\le kq\pi,

or

$\frac{p}{q}\le \pi<\frac{p}{q}+\frac{1}{kq}$.

Now for any real number $\varepsilon>0$, if we let $M=\lfloor \frac{1}{q\varepsilon} \rfloor+1$, then

$M-1\le\frac{1}{q\varepsilon},

so $\frac{1}{Mq}<\varepsilon$. Thus for all real numbers $\varepsilon>0$,

$\frac{p}{q}\le\pi<\frac{p}{q}+\frac{1}{Mq}<\frac{p}{q}+\varepsilon$,

so $\pi=\frac{p}{q}$. Since $\pi$ is irrational, this is a contradiction, so $a[n]$ must not be periodic.

If you're interested, this argument also proves that $a[n]$ is not periodic if $\pi$ is replace with any irrational number, and it is easy to prove that $a[n]$ is periodic if $\pi$ is replaced with a rational number.