7
$\begingroup$

Let $\theta = \frac{\sqrt{5}-1}{2}$. Define $a_{n}=(-1)^{\left \lfloor n\theta \right \rfloor}$. Please judge whether $S_{n}=\sum_{k=1}^{n} a_{k}$ is unbounded.

I tried to relate $\left\lfloor n\theta \right\rfloor$ to $\left\lfloor\theta^n\right\rfloor$, because $\theta^n$ can be written in the form "$x_{n}\theta + y_{n}$" in which $x_{n}$ and $y_{n}$ are related to Fibonacci sequence and $\left \lfloor \theta^n \right \rfloor$ is $0$.

But in this why I can only analyze some of the $a_{n}$.

Any ideas for help?

$\endgroup$
4
  • $\begingroup$ Maybe you could use the Zeckendorf factorization of $n$: en.m.wikipedia.org/wiki/Zeckendorf%27s_theorem $\endgroup$
    – Jacob
    Nov 7, 2018 at 23:14
  • $\begingroup$ It seems that $max(S_n, n \le 10^k)\ge k$ $\endgroup$
    – lsr314
    Nov 8, 2018 at 1:56
  • $\begingroup$ @Jacob Thanks, but it's hard to analyze the precise equation of a certain number being represented as the sum of Fibonacci numbers. $\endgroup$
    – Chiquita
    Nov 9, 2018 at 0:34
  • $\begingroup$ @Next How do you come to this conclusion? Could you give me some more-detailed hints please? Thanks $\endgroup$
    – Chiquita
    Nov 9, 2018 at 0:36

1 Answer 1

4
$\begingroup$

This is a very interesting problem.

Throughout this proof, let $$\rho(x,z)=\sum_{n=1}^{x}(-1)^{\left\lfloor\frac{n}{\varphi}+z\right\rfloor},$$ where $x \in \mathbb{N}$ and $z\in \mathbb{R}$, and let $\rho(x)=\rho(x,0)=S_x$. We may begin by noticing that $$\theta^{-1}=\varphi=\frac{1+\sqrt{5}}{2}.$$ We will use properties of the golden ratio throughout this proof.

Theorem 1. Let $E(x) = x-[x]$, where $[x]$ is the nearest integer function. If $c<E\left(\frac{n}{\varphi}\right)$ for all $n\leq x$, then $$\rho(x)=\rho(x,c). \tag{1}$$

Proof. Since $c<E\left(\frac{n}{\varphi}\right)$, we have that $\left\lfloor\frac{n}{\varphi}\right\rfloor=\left\lfloor\frac{n}{\varphi}+c\right\rfloor$ for all $n\leq x.$ Thus, $\rho(x)=\rho(x,c).$

Theorem 2. \begin{equation}\left\vert E\left(\frac{F_n}{\varphi}\right)\right\vert<\left\vert E\left(\frac{k}{\varphi}\right)\right\vert \quad \text{for all} \quad k<F_n,\tag{2}\end{equation} where $F_n=\frac{\varphi^n-(-\varphi)^{-n}}{\sqrt{5}}$ is the $n$th Fibonacci number.

Proof. From this post, we have $$\vert F_{n-1}\varphi-F_n\vert<|q\varphi-p| \quad\text{for all} \quad p,q\in \mathbb{N} \quad\text{such that}\quad q<F_{n-1},$$ since the Fibonacci numbers are the convergents of $\varphi$. Dividing by $\varphi$, we have $$\left\vert F_{n-1}-\frac{F_n}{\varphi}\right\vert<\left\vert q-\frac{p}{\varphi}\right\vert\quad\text{for all} \quad p,q\in \mathbb{N} \quad\text{such that}\quad q<F_{n-1}.$$ Also, $\left[\frac{F_n}{\varphi}\right] = F_{n-1}$, so $\left[\frac{p}{\varphi}\right]<F_{n-1}$ for $p<F_n$. Letting $q=\left[\frac{p}{\varphi}\right]$, we arrive at $(2)$.

Theorem 3. For all $k<F_n$, $$\rho(F_n+k)=\rho(F_n)+(-1)^{F_{n-1}}\rho(k). \tag{3}$$

Proof. We write $\rho(F_n+k)$ as \begin{align}\rho(F_n+k)=\rho(F_n)+\rho\left(k,\frac{F_n}{\varphi}\right)=\rho(F_n)+\sum_{n=1}^k(-1)^{\left\lfloor\frac{n}{\varphi}+F_{n-1}+E\left(\frac{F_n}{\varphi}\right)\right\rfloor}\\ =\rho(F_n)+(-1)^{F_{n-1}}\rho\left(k,E\left(\frac{F_n}{\varphi}\right)\right).\end{align} Applying $(1)$ and $(2)$, we have, $\rho\left(k,E\left(\frac{F_n}{\varphi}\right)\right)=\rho(k),$ yielding $(3).$

Theorem 4. $\rho(F_n)$ is periodic with period $6$. Specifically, $$\rho(F_n,0)=\begin{cases}1 & n \equiv 1,2 \pmod{6} \\ 0 & n \equiv 0 \pmod{3} \\ -1 & n\equiv 4,5\pmod{6}\end{cases}\tag{4}$$

Proof. We shall induct on $n$. For our base case, we choose all $n\leq 6$: $\rho(1)=1$, $\rho(2)=0$, $\rho(3)=-1$, $\rho(5)=-1$, $\rho(8)=0$ (note that $F_1=F_2=1$). Now assume $\rho(F_n)$ obeys $(4)$ up to $n=6k$. Using $(3)$ and the fact that $2\mid F_n$ iff $3\mid n$, we have $$\begin{split}\rho(F_{6k+1})=\rho(F_{6k})+(-1)^{F_{6k-1}}\rho(F_{6k-1})=0+1=1 \\ \rho(F_{6k+2})=\rho(F_{6k+1})+(-1)^{F_{6k}}\rho(F_{6k})=1+0=1 \\ \rho(F_{6k+3})=\rho(F_{6k+2})+(-1)^{F_{6k+1}}\rho(F_{6k+1})=1-1=0\\ \rho(F_{6k+4})=\rho(F_{6k+3})+(-1)^{F_{6k+2}}\rho(F_{6k+2})=0-1=-1\\ \rho(F_{6k+5})=\rho(F_{6k+4})+(-1)^{F_{6k+3}}\rho(F_{6k+3})=-1+0=-1\\ \rho(F_{6k+6})=\rho(F_{6k+5})+(-1)^{F_{6k+4}}\rho(F_{6k+4})=-1+1=0.\end{split}$$ This proves the induction step, and thus, $(4)$.

Theorem 5. $\rho(x)$ is unbounded. Specifically, $\rho:\mathbb{N}\rightarrow\mathbb{Z}$ is surjective.

Proof. Let $(n_i)_{i=1}^m$ be a finite, sequence of positive integers congruent to $1$ modulo $6$ such that $F_{n_i}>\sum_{k=i+1}^mF_{n_k}$ for all $i$. Then, by using $(3)$ iteratively, $$\begin{align}\rho\left(\sum_{i=1}^mF_{n_i}\right)=\rho(F_{n_1})+\rho\left(\sum_{i=2}^mF_{n_i}\right)=\rho(F_{n_1})+\rho(F_{n_2})+\rho\left(\sum_{i=3}^mF_{n_i}\right)=\cdots\\ =\sum_{i=1}^m\rho(F_{n_i})=m.\end{align}$$ Alternatively, let $(n_i)_{i=1}^m$ be a finite, sequence of positive integers congruent to $4$ modulo $6$ such that $F_{n_i}>\sum_{k=i+1}^mF_{n_k}$ for all $i$. Then, by using $(3)$ iteratively, $$\begin{align}\rho\left(\sum_{i=1}^mF_{n_i}\right)=\rho(F_{n_1})+\rho\left(\sum_{i=2}^mF_{n_i}\right)=\rho(F_{n_1})+\rho(F_{n_2})+\rho\left(\sum_{i=3}^mF_{n_i}\right)=\cdots\\ =\sum_{i=1}^m\rho(F_{n_i})=-m.\end{align}$$ Since we also know $\rho$ takes on the value of $0$ at some numbers (e.g. $\rho(2)=0$), $\rho$ (i.e. $S_n$) is not only unbounded, but surjective.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .