Skip to main content
MathOverflow

Return to Answer

fix typo, Zeckendorf
Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

$\let\fii\varphi\let\ol\overline$Andreas has already answered the original question, however it was raised in the comments whether $f$ coincides with the sequence in http://oeis.org/A022342: $$\tag{$*$}f(n)=\lfloor n\fii+\fii^{-1}\rfloor=\lfloor(n+1)\fii\rfloor-1,$$ where $\fii=(1+\sqrt5)/2$ is the golden ratio, so let me argue that this is indeed the case.

Every integer $n\ge0$ can be written as $n=\ol a:=\sum_{i=2}^\infty a_iF_i$, where $F_i$ is the $i$th Fibonacci number, and $a=(a_i)_{i\ge2}$ is a sequence such that $a_i\in\{0,1\}$, $a_i=0$ for all but finitely many $i$, and no two consecutive elements of $a$ are $1$. (We can find find such a representation recursively by choosing the largest $i$ such that $F_i\le n$, and combining it with a representation of $n-F_i$. This is known as the Zeckendorf expansion of $n$.) Let $A$ denote the set of all such sequences $a$. It is easy to see that if $i$ is the largest index of a nonzero element of $a\in A$, then $\tilde a< F_{i+1}$$\ol a< F_{i+1}$; it follows that $\ol a< \ol b$ iff $a< b$ in the lexicographic order. In particular, the representation is unique.

Define $f'\colon\mathbb N\to\mathbb N$ by $f'(\ol a)=\ol{a0}$, where for $u\in\{0,1\}$, $au$ denotes the concatenation of $u$ and $a$: $(au)_{i+1}=a_i$, $(au)_2=u$. In other words, $f'(\ol a)=\sum_ia_iF_{i+1}$. Clearly, $f'$ is an increasing function. Moreover, $$f'(\ol a)+\ol a+1=\sum_ia_i(F_i+F_{i+1})+1=\sum_ia_iF_{i+2}+F_2=\ol{a01}.$$ It follows that $\mathbb N$ is the disjoint union of $\{f'(k):k\in\mathbb N\}$ and $\{f'(k)+k+1:k\in\mathbb N\}$. Then it is easy to show $$f(n)=f'(n)$$ by induction on $n=\ol a$: indeed, $a0$ is the lexicographically least sequence in $A$ excluded from $\{b0,b01:b< a\}$.

Since $F_i=\bigl(\fii^i-(-\fii)^{-i}\bigr)/\sqrt5$, we have $$f(n)-\fii n=\sum_{i:a_i=1}(F_{i+1}-\fii F_i)=\sum_{i:a_i=1}(-\fii)^{-i}\frac{\fii^{-1}+\fii}{\sqrt5}=\sum_{i:a_i=1}(-\fii)^{-i}.$$ Thus, \begin{align*} f(n)-\fii n&< \sum_{\substack{i\ge2\\\\i\text{ even}}}\fii^{-i}=\frac{\fii^{-2}}{1-\fii^{-2}}=\fii^{-1},\\\\ f(n)-\fii n&>-\sum_{\substack{i\ge2\\\\i\text{ odd}}}\fii^{-i}=-\frac{\fii^{-3}}{1-\fii^{-2}}=-\fii^{-2}=\fii^{-1}-1, \end{align*} which shows $(*)$.

$\let\fii\varphi\let\ol\overline$Andreas has already answered the original question, however it was raised in the comments whether $f$ coincides with the sequence in http://oeis.org/A022342: $$\tag{$*$}f(n)=\lfloor n\fii+\fii^{-1}\rfloor=\lfloor(n+1)\fii\rfloor-1,$$ where $\fii=(1+\sqrt5)/2$ is the golden ratio, so let me argue that this is indeed the case.

Every integer $n\ge0$ can be written as $n=\ol a:=\sum_{i=2}^\infty a_iF_i$, where $F_i$ is the $i$th Fibonacci number, and $a=(a_i)_{i\ge2}$ is a sequence such that $a_i\in\{0,1\}$, $a_i=0$ for all but finitely many $i$, and no two consecutive elements of $a$ are $1$. (We can find find such a representation recursively by choosing the largest $i$ such that $F_i\le n$, and combining it with a representation of $n-F_i$.) Let $A$ denote the set of all such sequences $a$. It is easy to see that if $i$ is the largest index of a nonzero element of $a\in A$, then $\tilde a< F_{i+1}$; it follows that $\ol a< \ol b$ iff $a< b$ in the lexicographic order. In particular, the representation is unique.

Define $f'\colon\mathbb N\to\mathbb N$ by $f'(\ol a)=\ol{a0}$, where for $u\in\{0,1\}$, $au$ denotes the concatenation of $u$ and $a$: $(au)_{i+1}=a_i$, $(au)_2=u$. In other words, $f'(\ol a)=\sum_ia_iF_{i+1}$. Clearly, $f'$ is an increasing function. Moreover, $$f'(\ol a)+\ol a+1=\sum_ia_i(F_i+F_{i+1})+1=\sum_ia_iF_{i+2}+F_2=\ol{a01}.$$ It follows that $\mathbb N$ is the disjoint union of $\{f'(k):k\in\mathbb N\}$ and $\{f'(k)+k+1:k\in\mathbb N\}$. Then it is easy to show $$f(n)=f'(n)$$ by induction on $n=\ol a$: indeed, $a0$ is the lexicographically least sequence in $A$ excluded from $\{b0,b01:b< a\}$.

Since $F_i=\bigl(\fii^i-(-\fii)^{-i}\bigr)/\sqrt5$, we have $$f(n)-\fii n=\sum_{i:a_i=1}(F_{i+1}-\fii F_i)=\sum_{i:a_i=1}(-\fii)^{-i}\frac{\fii^{-1}+\fii}{\sqrt5}=\sum_{i:a_i=1}(-\fii)^{-i}.$$ Thus, \begin{align*} f(n)-\fii n&< \sum_{\substack{i\ge2\\\\i\text{ even}}}\fii^{-i}=\frac{\fii^{-2}}{1-\fii^{-2}}=\fii^{-1},\\\\ f(n)-\fii n&>-\sum_{\substack{i\ge2\\\\i\text{ odd}}}\fii^{-i}=-\frac{\fii^{-3}}{1-\fii^{-2}}=-\fii^{-2}=\fii^{-1}-1, \end{align*} which shows $(*)$.

$\let\fii\varphi\let\ol\overline$Andreas has already answered the original question, however it was raised in the comments whether $f$ coincides with the sequence in http://oeis.org/A022342: $$\tag{$*$}f(n)=\lfloor n\fii+\fii^{-1}\rfloor=\lfloor(n+1)\fii\rfloor-1,$$ where $\fii=(1+\sqrt5)/2$ is the golden ratio, so let me argue that this is indeed the case.

Every integer $n\ge0$ can be written as $n=\ol a:=\sum_{i=2}^\infty a_iF_i$, where $F_i$ is the $i$th Fibonacci number, and $a=(a_i)_{i\ge2}$ is a sequence such that $a_i\in\{0,1\}$, $a_i=0$ for all but finitely many $i$, and no two consecutive elements of $a$ are $1$. (We can find find such a representation recursively by choosing the largest $i$ such that $F_i\le n$, and combining it with a representation of $n-F_i$. This is known as the Zeckendorf expansion of $n$.) Let $A$ denote the set of all such sequences $a$. It is easy to see that if $i$ is the largest index of a nonzero element of $a\in A$, then $\ol a< F_{i+1}$; it follows that $\ol a< \ol b$ iff $a< b$ in the lexicographic order. In particular, the representation is unique.

Define $f'\colon\mathbb N\to\mathbb N$ by $f'(\ol a)=\ol{a0}$, where for $u\in\{0,1\}$, $au$ denotes the concatenation of $u$ and $a$: $(au)_{i+1}=a_i$, $(au)_2=u$. In other words, $f'(\ol a)=\sum_ia_iF_{i+1}$. Clearly, $f'$ is an increasing function. Moreover, $$f'(\ol a)+\ol a+1=\sum_ia_i(F_i+F_{i+1})+1=\sum_ia_iF_{i+2}+F_2=\ol{a01}.$$ It follows that $\mathbb N$ is the disjoint union of $\{f'(k):k\in\mathbb N\}$ and $\{f'(k)+k+1:k\in\mathbb N\}$. Then it is easy to show $$f(n)=f'(n)$$ by induction on $n=\ol a$: indeed, $a0$ is the lexicographically least sequence in $A$ excluded from $\{b0,b01:b< a\}$.

Since $F_i=\bigl(\fii^i-(-\fii)^{-i}\bigr)/\sqrt5$, we have $$f(n)-\fii n=\sum_{i:a_i=1}(F_{i+1}-\fii F_i)=\sum_{i:a_i=1}(-\fii)^{-i}\frac{\fii^{-1}+\fii}{\sqrt5}=\sum_{i:a_i=1}(-\fii)^{-i}.$$ Thus, \begin{align*} f(n)-\fii n&< \sum_{\substack{i\ge2\\\\i\text{ even}}}\fii^{-i}=\frac{\fii^{-2}}{1-\fii^{-2}}=\fii^{-1},\\\\ f(n)-\fii n&>-\sum_{\substack{i\ge2\\\\i\text{ odd}}}\fii^{-i}=-\frac{\fii^{-3}}{1-\fii^{-2}}=-\fii^{-2}=\fii^{-1}-1, \end{align*} which shows $(*)$.

Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

$\let\fii\varphi\let\ol\overline$Andreas has already answered the original question, however it was raised in the comments whether $f$ coincides with the sequence in http://oeis.org/A022342: $$\tag{$*$}f(n)=\lfloor n\fii+\fii^{-1}\rfloor=\lfloor(n+1)\fii\rfloor-1,$$ where $\fii=(1+\sqrt5)/2$ is the golden ratio, so let me argue that this is indeed the case.

Every integer $n\ge0$ can be written as $n=\ol a:=\sum_{i=2}^\infty a_iF_i$, where $F_i$ is the $i$th Fibonacci number, and $a=(a_i)_{i\ge2}$ is a sequence such that $a_i\in\{0,1\}$, $a_i=0$ for all but finitely many $i$, and no two consecutive elements of $a$ are $1$. (We can find find such a representation recursively by choosing the largest $i$ such that $F_i\le n$, and combining it with a representation of $n-F_i$.) Let $A$ denote the set of all such sequences $a$. It is easy to see that if $i$ is the largest index of a nonzero element of $a\in A$, then $\tilde a< F_{i+1}$; it follows that $\ol a< \ol b$ iff $a< b$ in the lexicographic order. In particular, the representation is unique.

Define $f'\colon\mathbb N\to\mathbb N$ by $f'(\ol a)=\ol{a0}$, where for $u\in\{0,1\}$, $au$ denotes the concatenation of $u$ and $a$: $(au)_{i+1}=a_i$, $(au)_2=u$. In other words, $f'(\ol a)=\sum_ia_iF_{i+1}$. Clearly, $f'$ is an increasing function. Moreover, $$f'(\ol a)+\ol a+1=\sum_ia_i(F_i+F_{i+1})+1=\sum_ia_iF_{i+2}+F_2=\ol{a01}.$$ It follows that $\mathbb N$ is the disjoint union of $\{f'(k):k\in\mathbb N\}$ and $\{f'(k)+k+1:k\in\mathbb N\}$. Then it is easy to show $$f(n)=f'(n)$$ by induction on $n=\ol a$: indeed, $a0$ is the lexicographically least sequence in $A$ excluded from $\{b0,b01:b< a\}$.

Since $F_i=\bigl(\fii^i-(-\fii)^{-i}\bigr)/\sqrt5$, we have $$f(n)-\fii n=\sum_{i:a_i=1}(F_{i+1}-\fii F_i)=\sum_{i:a_i=1}(-\fii)^{-i}\frac{\fii^{-1}+\fii}{\sqrt5}=\sum_{i:a_i=1}(-\fii)^{-i}.$$ Thus, \begin{align*} f(n)-\fii n&< \sum_{\substack{i\ge2\\\\i\text{ even}}}\fii^{-i}=\frac{\fii^{-2}}{1-\fii^{-2}}=\fii^{-1},\\\\ f(n)-\fii n&>-\sum_{\substack{i\ge2\\\\i\text{ odd}}}\fii^{-i}=-\frac{\fii^{-3}}{1-\fii^{-2}}=-\fii^{-2}=\fii^{-1}-1, \end{align*} which shows $(*)$.