1 files changed, 1852 insertions, 0 deletions
diff --git a/vol1/1.2.8.lyx b/vol1/1.2.8.lyx
new file mode 100644
index 0000000..23e44dc
--- /dev/null
+++ b/vol1/1.2.8.lyx
@@ -0,0 +1,1852 @@
+#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
+<lyxtabular version="3" rows="8" columns="8">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" bottomline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $n$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{0}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{2}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{3}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{4}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{5}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\binom{n}{6}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+0
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+6
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+8
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+40
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+60
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+40
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+8
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\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_{k-1}$
+\end_inset
+
+ (otherwise 
+\begin_inset Formula $F_{k+1}\leq n\#$
+\end_inset
+
+),
+ and it can be expressed this way by induction.
+ 
+\end_layout
+
+\begin_layout Standard
+To see that this representation is unique,
+ let 
+\begin_inset Formula $n=F_{k_{1}}+\dots+F_{k_{r}}=F_{j_{1}}+\dots+F_{j_{s}}$
+\end_inset
+
+.
+ If 
+\begin_inset Formula $n\leq3$
+\end_inset
+
+,
+ this is easy to check.
+ Otherwise,
+ if 
+\begin_inset Formula $F_{k_{1}}=F_{j_{1}}$
+\end_inset
+
+ we use induction;
+ otherwise assume 
+\begin_inset Formula $F_{k_{1}}>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