Changed layout for more manageable volumes

1 files changed, 0 insertions, 1852 deletions

diff --git a/1.2.8.lyx b/1.2.8.lyx
deleted file mode 100644
index 23e44dc..0000000
--- a/1.2.8.lyx
+++ /dev/null
@@ -1,1852 +0,0 @@
-#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