From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001 From: Juan Marín Noguera Date: Fri, 16 May 2025 22:18:44 +0200 Subject: Changed layout for more manageable volumes --- 1.2.8.lyx | 1852 ------------------------------------------------------------- 1 file changed, 1852 deletions(-) delete mode 100644 1.2.8.lyx (limited to '1.2.8.lyx') 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 - - - - - - - - - - - - -\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 -- cgit v1.2.3