6
$\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$
  • $\begingroup$ Maybe you could use the Zeckendorf factorization of $n$: en.m.wikipedia.org/wiki/Zeckendorf%27s_theorem $\endgroup$ – Jacob Nov 7 '18 at 23:14
  • $\begingroup$ It seems that $max(S_n, n \le 10^k)\ge k$ $\endgroup$ – Next Nov 8 '18 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$ – Zero Nov 9 '18 at 0:34
  • $\begingroup$ @Next How do you come to this conclusion? Could you give me some more-detailed hints please? Thanks $\endgroup$ – Zero Nov 9 '18 at 0:36
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.