#LyX 2.4 created this file. For more info see https://www.lyx.org/ \lyxformat 620 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \input defs \usepackage{amsmath} \end_preamble \use_default_options true \maintain_unincluded_children no \language english \language_package default \inputencoding utf8 \fontencoding auto \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_roman_osf false \font_sans_osf false \font_typewriter_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \float_placement class \float_alignment class \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_formatted_ref 0 \use_minted 0 \use_lineno 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style english \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tablestyle default \tracking_changes false \output_changes false \change_bars false \postpone_fragile_content false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \docbook_table_output 0 \docbook_mathml_prefix 1 \end_header \begin_body \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash exerc1[10] \end_layout \end_inset What is the answer to Leonardo Fibonacci's original problem: How many pairs of rabbits are present after a year? \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset After one month there are \begin_inset Formula $F_{3}=2$ \end_inset pairs of rabbits, after two months there are \begin_inset Formula $F_{4}=3$ \end_inset , etc., therefore after a year there are \begin_inset Formula $F_{14}=377$ \end_inset pairs of rabbits. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc2[20] \end_layout \end_inset In view of Eq. (15), what is the approximate value of \begin_inset Formula $F_{1000}$ \end_inset ? (Use logarithms found in Appendix A.) \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset \begin_inset Formula \begin{align*} F_{1000} & \approx\frac{\phi^{1000}}{\sqrt{5}}=\frac{10^{\log\phi^{1000}}}{\sqrt{5}}=\frac{10^{1000(\ln\phi/\ln10)}}{\sqrt{5}}\cong\frac{10^{1000\cdot0.48121...\cdot0.43429...}}{2.23606...}\cong\frac{10^{208.9876..}}{2.23606...}\\ & \cong\frac{10^{0.9876}}{2.23606}\cdot10^{208}\cong4.3\cdot10^{208}. \end{align*} \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc4[14] \end_layout \end_inset Find all \begin_inset Formula $n$ \end_inset for which \begin_inset Formula $F_{n}=n$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset \begin_inset Formula $F_{0}=0$ \end_inset , \begin_inset Formula $F_{1}=1$ \end_inset . Then \begin_inset Formula $F_{2}=1$ \end_inset , \begin_inset Formula $F_{3}=2$ \end_inset , \begin_inset Formula $F_{4}=3$ \end_inset , \begin_inset Formula $F_{5}=5$ \end_inset , and from here \begin_inset Formula $F_{n}$ \end_inset grows strictly faster than \begin_inset Formula $n$ \end_inset so there are no more such numbers. Thus only 0, 1, and 5 meet this condition. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc7[15] \end_layout \end_inset If \begin_inset Formula $n$ \end_inset is not a prime number, \begin_inset Formula $F_{n}$ \end_inset is not a prime number (with one exception). Prove this and find the exception. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset The exception is \begin_inset Formula $F_{4}=3$ \end_inset . For the general rule, let \begin_inset Formula $r,s\in\mathbb{Z}$ \end_inset with \begin_inset Formula $r\geq3$ \end_inset and \begin_inset Formula $s\geq2$ \end_inset , by Eq. (6), \end_layout \begin_layout Standard \begin_inset Formula \begin{align*} F_{rs} & =F_{r+r(s-1)}=F_{r(s-1)}F_{r+1}+F_{r(s-1)-1}F_{r}=F_{r}(F_{r(s-1)}+F_{r(s-1)-1})+F_{r-1}F_{r(s-1)}\\ & =F_{r}\left(F_{r(s-1)+1}+F_{r-1}{\textstyle \frac{F_{r(s-1)}}{F_{r}}}\right), \end{align*} \end_inset where the fraction in the last part is an integer. If \begin_inset Formula $r>2$ \end_inset , then \begin_inset Formula $F_{r}>1$ \end_inset and, since \begin_inset Formula $F_{r(s-1)+1}>1$ \end_inset , we have a decomposition of \begin_inset Formula $F_{rs}$ \end_inset as a compound number. Every compound number other than 4 can be expressed as a product of integers \begin_inset Formula $rs$ \end_inset with \begin_inset Formula $r\geq3$ \end_inset and \begin_inset Formula $s\geq2$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc13[M22] \end_layout \end_inset Express the following sequences in terms of the Fibonacci numbers, when \begin_inset Formula $r$ \end_inset , \begin_inset Formula $s$ \end_inset , and \begin_inset Formula $c$ \end_inset are given constants: \end_layout \begin_layout Enumerate \begin_inset Formula $a_{0}=r$ \end_inset , \begin_inset Formula $a_{1}=s$ \end_inset ; \begin_inset Formula $a_{n+2}=a_{n+1}+a_{n}$ \end_inset , for \begin_inset Formula $n\geq0$ \end_inset . \end_layout \begin_layout Enumerate \begin_inset Formula $b_{0}=0$ \end_inset , \begin_inset Formula $b_{1}=1$ \end_inset ; \begin_inset Formula $b_{n+2}=b_{n+1}+b_{n}+c$ \end_inset , for \begin_inset Formula $n\geq0$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset \end_layout \begin_layout Enumerate We have \begin_inset Formula \[ \binom{a_{n+1}}{a_{n}}=\begin{pmatrix}1 & 1\\ 1 & 0 \end{pmatrix}\begin{pmatrix}a_{n}\\ a_{n-1} \end{pmatrix}=\dots=\begin{pmatrix}1 & 1\\ 1 & 0 \end{pmatrix}^{n}\begin{pmatrix}s\\ r \end{pmatrix}=\begin{pmatrix}F_{n+1}s+F_{n}r\\ F_{n}s+F_{n-1}r \end{pmatrix}, \] \end_inset so in general \begin_inset Formula $a_{n}=F_{n-1}r+F_{n}s$ \end_inset , using the convention that \begin_inset Formula $F_{-1}=1$ \end_inset . \end_layout \begin_layout Enumerate We have \begin_inset Formula \[ \begin{pmatrix}b_{n+1}\\ b_{n}\\ 1 \end{pmatrix}=\begin{pmatrix}1 & 1 & c\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix}b_{n}\\ b_{n-1}\\ 1 \end{pmatrix}=\dots=\begin{pmatrix}1 & 1 & c\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}^{n}\begin{pmatrix}1\\ 0\\ 1 \end{pmatrix}. \] \end_inset By playing a bit with this matrix, we come to the conclusion that \begin_inset Formula \[ \begin{pmatrix}1 & 1 & c\\ 1\\ & & 1 \end{pmatrix}^{n}=\begin{pmatrix}F_{n+1} & F_{n} & (F_{n+2}-1)c\\ F_{n} & F_{n-1} & (F_{n+1}-1)c\\ & & 1 \end{pmatrix} \] \end_inset and therefore \begin_inset Formula \[ b_{n}=F_{n}+(F_{n+1}-1)c. \] \end_inset For \begin_inset Formula $n=0$ \end_inset and \begin_inset Formula $n=1$ \end_inset , this is easy to check. For \begin_inset Formula $n\geq2$ \end_inset , \begin_inset Formula \[ b_{n}=b_{n-1}+b_{n-2}+c=F_{n-1}+(F_{n}-1)c+F_{n-2}+(F_{n-1}-1)c+c=F_{n}+(F_{n+1}-1)c. \] \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc16[M20] \end_layout \end_inset Fibonacci numbers appear implicitly in Pascal's triangle if it is viewed from the right angle. Show that the following sum of binomial coefficients is a Fibonacci number: \begin_inset Formula \[ \sum_{k=0}^{n}\binom{n-k}{k}. \] \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset We prove by induction that this sum is precisely \begin_inset Formula $F_{n+1}$ \end_inset . For \begin_inset Formula $n=0$ \end_inset and \begin_inset Formula $n=1$ \end_inset , this is a simple check. For \begin_inset Formula $n>1$ \end_inset , \begin_inset Formula \begin{align*} \sum_{k=0}^{n}\binom{n-k}{k} & =\sum_{k=0}^{n}\binom{n-k-1}{k}+\sum_{k=0}^{n}\binom{n-k-1}{k-1}\\ & =\sum_{k=0}^{n}\binom{n-k-1}{k}+\sum_{k=-1}^{n-1}\binom{n-k-2}{k}\\ & =\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{k=0}^{n-2}\binom{(n-2)-k}{k}=F_{n}+F_{n-1}=F_{n+1}. \end{align*} \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc22[M20] \end_layout \end_inset Show that \begin_inset Formula $\sum_{k}\binom{n}{k}F_{m+k}$ \end_inset is a Fibonacci number. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset We prove by induction on \begin_inset Formula $n$ \end_inset that this sum is \begin_inset Formula $F_{m+2n}$ \end_inset . For \begin_inset Formula $n=0$ \end_inset and \begin_inset Formula $n=1$ \end_inset , this is a simple check. For \begin_inset Formula $n>1$ \end_inset , \begin_inset Formula \begin{align*} \sum_{k}\binom{n}{k}F_{m+k} & =\sum_{k}\binom{n-1}{k}F_{m+k}+\sum_{k}\binom{n-1}{k-1}F_{m+k}\\ & =F_{m+2(n-1)}+\sum_{k}\binom{n-1}{k}F_{m+1+k}\\ & =F_{m+2(n-1)}+F_{m+1+2(n-1)}=F_{m+2+2(n-1)}=F_{m+2n}. \end{align*} \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc26[M20] \end_layout \end_inset Using the previous exercise, show that \begin_inset Formula $F_{p}=5^{(p-1)/2}\pmod p$ \end_inset if \begin_inset Formula $p$ \end_inset is an odd prime. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset The previous exercise tells us that \begin_inset Formula \[ 2^{n}F_{n}=2\sum_{k\text{ odd}}\binom{n}{k}5^{(k-1)/2}. \] \end_inset Now, if \begin_inset Formula $n=p$ \end_inset is prime, \begin_inset Formula $\binom{p}{k}=\frac{p(p-1)\cdots(p-k+1)}{1\cdots k}$ \end_inset is a multiple of \begin_inset Formula $p$ \end_inset for \begin_inset Formula $k\in\{1,\dots,p-1\}$ \end_inset , and \begin_inset Formula $k=0$ \end_inset is not odd, so \begin_inset Formula \[ 2^{p-1}F_{p}=\sum_{k\text{ odd}}\binom{p}{k}5^{(k-1)/2}\equiv\binom{p}{p}5^{(p-1)/2}=5^{(p-1)/2}\pmod p, \] \end_inset but by Fermat's theorem, \begin_inset Formula $2^{p-1}\equiv1\pmod p$ \end_inset , so this simplifies to the desired result. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc29[M23] \end_layout \end_inset ( \emph on Fibonomial coefficients. \emph default ) Édouard Lucas defined the quantities \begin_inset Formula \[ \binom{n}{k}_{{\cal F}}=\frac{F_{n}F_{n-1}\cdots F_{n-k+1}}{F_{k}F_{k-1}\cdots F_{1}}=\prod_{j=1}^{k}\left(\frac{F_{n-k+j}}{F_{j}}\right) \] \end_inset in a manner analogous to binomial coefficients. \end_layout \begin_layout Enumerate Make a table of \begin_inset Formula $\binom{n}{k}_{{\cal F}}$ \end_inset for \begin_inset Formula $0\leq k\leq n\leq6$ \end_inset . \end_layout \begin_layout Enumerate Show that \begin_inset Formula $\binom{n}{k}_{{\cal F}}$ \end_inset is always an integer because we have \begin_inset Formula \[ \binom{n}{k}_{{\cal F}}=F_{k-1}\binom{n-1}{k}_{{\cal F}}+F_{n-k+1}\binom{n-1}{k-1}_{{\cal F}}. \] \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset \end_layout \begin_layout Enumerate \begin_inset Note Note status open \begin_layout Plain Layout \end_layout \end_inset \end_layout \begin_deeper \begin_layout Standard \align center \begin_inset Tabular \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $n$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $\binom{n}{0}$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $\binom{n}{1}$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $\binom{n}{2}$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $\binom{n}{3}$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $\binom{n}{4}$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $\binom{n}{5}$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \begin_inset Formula $\binom{n}{6}$ \end_inset \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 0 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 2 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 3 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 2 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 2 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 4 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 3 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 6 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 3 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 5 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 5 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 15 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 15 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 5 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 6 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 8 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 40 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 60 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 40 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 8 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 1 \end_layout \end_inset \end_inset \end_layout \end_deeper \begin_layout Enumerate We have \begin_inset Formula \begin{multline*} F_{k-1}\binom{n-1}{k}_{{\cal F}}+F_{n-k+1}\binom{n-1}{k-1}_{{\cal F}}=\\ =F_{k-1}\prod_{j=1}^{k}\frac{F_{n-k+j-1}}{F_{j}}+F_{n-k+1}\prod_{j=1}^{k-1}\frac{F_{n-k+j}}{F_{j}}=\\ =\frac{1}{F_{k}}\left(\prod_{j=1}^{k-1}\frac{F_{n-k+j}}{F_{j}}\right)(F_{k-1}F_{n-k}+F_{n-k+1}F_{k}), \end{multline*} \end_inset where the last identity is better read backwards, and by Eq. (6), \begin_inset Formula \[ F_{n}=F_{(n-k)+k}=F_{k}F_{n-k+1}+F_{k-1}F_{n-k}, \] \end_inset so the above simplifies precisely to \begin_inset Formula $\binom{n}{k}_{{\cal F}}$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc34[M24] \end_layout \end_inset ( \emph on The Fibonacci number system. \emph default ) Let the notation \begin_inset Formula $k\gg m$ \end_inset mean that \begin_inset Formula $k\geq m+2$ \end_inset . Show that every positive integer \begin_inset Formula $n$ \end_inset has a \emph on unique \emph default representation \begin_inset Formula $n=F_{k_{1}}+F_{k_{2}}+\dots+F_{k_{r}}$ \end_inset , where \begin_inset Formula $k_{1}\gg k_{2}\gg\cdots\gg k_{r}\gg0$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset If \begin_inset Formula $n\leq3$ \end_inset , this is easy to check. Otherwise, let \begin_inset Formula $k$ \end_inset be the greatest number such that \begin_inset Formula $n\geq F_{k}$ \end_inset . If \begin_inset Formula $n=F_{k}$ \end_inset , we're done. Otherwise \begin_inset Formula $n>3$ \end_inset and \begin_inset Formula $k\geq4$ \end_inset , and \begin_inset Formula $n-F_{k}F_{j_{1}}\geq2$ \end_inset , and we want to prove that \begin_inset Formula \[ F_{j_{2}}+\dots+F_{j_{s}}\leq F_{j_{1}-2}+\dots+F_{\lfloor j_{1}\bmod2\rfloor+2}\leq F_{j_{1}-1}\leq F_{k_{1}}-F_{j_{1}}. \] \end_inset The first inequality comes from the highest value that \begin_inset Formula $F_{j_{2}}+\dots+F_{j_{s}}$ \end_inset could possibly have, and the last one from the highest value that \begin_inset Formula $F_{j_{1}}+F_{j_{1}-1}$ \end_inset could. For the middle one we use induction. For \begin_inset Formula $j_{1}\in\{2,3\}$ \end_inset , the left hand side is 0. Otherwise \begin_inset Formula \[ F_{j_{1}-2}+F_{j_{1}-4}+\dots+F_{\lfloor j_{1}\bmod2\rfloor+2}\leq F_{j_{1}-2}+F_{j_{1}-3}=F_{j_{1}-1}. \] \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc41[M25] \end_layout \end_inset (Yuri Matiyasevich, 1990.) Let \begin_inset Formula $f(x)=\lfloor x+\phi^{-1}\rfloor$ \end_inset . Prove that if \begin_inset Formula $n=F_{k_{1}}+\dots+F_{k_{r}}$ \end_inset is the representation of \begin_inset Formula $n$ \end_inset in the Fibonacci number system of exercise 34, then \begin_inset Formula $F_{k_{1}+1}+\dots+F_{k_{r}+1}=f(\phi n)$ \end_inset . Find a similar formula for \begin_inset Formula $F_{k_{1}-1}+\dots+F_{k_{r}-1}$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset Using that each \begin_inset Formula $F_{k_{i}}=\frac{1}{\sqrt{5}}(\phi^{k_{i}}+\hat{\phi}^{k_{i}})$ \end_inset , let \begin_inset Formula $m\coloneqq F_{k_{1}+1}+\dots+F_{k_{r}+1}$ \end_inset , since \begin_inset Formula $m\in\mathbb{Z}$ \end_inset , \begin_inset Formula \begin{align*} f(\phi n)-m & =\left\lfloor \frac{1}{\sqrt{5}}\left(\sum_{i}\phi^{k_{i}+1}+\sum_{i}\hat{\phi}^{k_{i}-1}\right)-\hat{\phi}\right\rfloor -\frac{1}{\sqrt{5}}\left(\sum_{i}\phi^{k_{i}+1}-\sum_{i}\hat{\phi}^{k_{i}+1}\right)\\ & =\left\lfloor \frac{1}{\sqrt{5}}\sum_{i}(\hat{\phi}^{k_{i}-1}+\hat{\phi}^{k_{i}+1})-\hat{\phi}\right\rfloor =\left\lfloor \frac{1+\hat{\phi}^{2}}{\sqrt{5}}\sum_{i}\hat{\phi}^{k_{i}-1}-\hat{\phi}\right\rfloor . \end{align*} \end_inset Here, when \begin_inset Formula $k_{i}$ \end_inset is even, \begin_inset Formula $\hat{\phi}^{k_{i}-1}$ \end_inset is negative, and when it's odd, \begin_inset Formula $\hat{\phi}^{k_{i}-1}$ \end_inset is positive, so the value of this sum is strictly lower than \begin_inset Formula $\sum_{k\geq1}\hat{\phi}^{2k}=\frac{\hat{\phi}^{2}}{1-\hat{\phi}^{2}}$ \end_inset , and strictly greater than \begin_inset Formula $\sum_{k\geq1}\hat{\phi}^{2k-1}=\frac{\hat{\phi}}{1-\hat{\phi}^{2}}$ \end_inset . Now, \begin_inset Formula $\hat{\phi}^{2}=\frac{1}{4}(1-\sqrt{5})^{2}=\frac{1}{4}(6-2\sqrt{5})=\frac{1}{2}(3-\sqrt{5})$ \end_inset , so \begin_inset Formula $1-\hat{\phi}^{2}=\frac{1}{2}(2-3+\sqrt{5})=-\frac{1}{2}(1-\sqrt{5})=-\hat{\phi}$ \end_inset and therefore the lower bound of what is inside the brackets above is \begin_inset Formula \[ \frac{1+\hat{\phi}^{2}}{\sqrt{5}}\frac{\hat{\phi}}{1-\hat{\phi}^{2}}-\hat{\phi}=-\frac{1+\hat{\phi}^{2}}{\sqrt{5}}-\hat{\phi}=-\frac{5-\sqrt{5}}{2\sqrt{5}}-\frac{1-\sqrt{5}}{2}=-\frac{5-\sqrt{5}+\sqrt{5}-5}{2\sqrt{5}}=0, \] \end_inset and the upper bound is \begin_inset Formula \[ -\hat{\phi}\frac{1+\hat{\phi}^{2}}{\sqrt{5}}-\hat{\phi}=-\hat{\phi}\left(\frac{5-\sqrt{5}}{2\sqrt{5}}+1\right)=-\hat{\phi}\left(\frac{5+\sqrt{5}}{2\sqrt{5}}\right)=-\hat{\phi}\phi=1, \] \end_inset and since these bounds are never reached, the property has been proven. A similar argument can be made to prove that \begin_inset Formula $F_{k_{1}-1}+\dots+F_{k_{r}-1}=f(n/\phi)$ \end_inset . \end_layout \end_body \end_document