#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
\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
\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[00]
\end_layout

\end_inset

How many ways are there to shuffle a 52-card deck?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\begin_inset Formula $52!=80658175170943878571660636856403766975289505440883277824000000000000$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc2[10]
\end_layout

\end_inset

In the notation of Eq.
 (2),
 show that 
\begin_inset Formula $p_{n(n-1)}=p_{nn}$
\end_inset

,
 and explain why this happens.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\begin_inset Formula $p_{n(n-1)}=n(n-1)\cdots(n-(n-1)+1)=n(n-1)\cdots2=n(n-1)\cdots1=p_{nn}$
\end_inset

.
 This is because 
\begin_inset Formula $p_{n(n-1)}$
\end_inset

 is the number of ways to take and arrange 
\begin_inset Formula $n-1$
\end_inset

 objects out 
\begin_inset Formula $n$
\end_inset

 and 
\begin_inset Formula $p_{nn}$
\end_inset

 is the number of ways to take and arrange the 
\begin_inset Formula $n$
\end_inset

 objects,
 which consists of first arranging 
\begin_inset Formula $n-1$
\end_inset

 objects out of the 
\begin_inset Formula $n$
\end_inset

 objects and then adding the one remaining.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc3[10]
\end_layout

\end_inset

What permutations of 
\begin_inset Formula $\{1,2,3,4,5\}$
\end_inset

 would be constructed from the permutation 
\begin_inset Formula $3\,1\,2\,4$
\end_inset

 using Methods 1 and 2,
 respectively?
\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

\series bold
Method 1:

\series default
 
\begin_inset Formula $5\,3\,1\,2\,4$
\end_inset

,
 
\begin_inset Formula $3\,5\,1\,2\,4$
\end_inset

,
 
\begin_inset Formula $3\,1\,5\,2\,4$
\end_inset

,
 
\begin_inset Formula $3\,1\,2\,5\,4$
\end_inset

,
 
\begin_inset Formula $3\,1\,2\,4\,5$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Method 2:

\series default
 
\begin_inset Formula $4\,2\,3\,5\,1$
\end_inset

,
 
\begin_inset Formula $4\,1\,3\,5\,2$
\end_inset

,
 
\begin_inset Formula $4\,1\,2\,5\,3$
\end_inset

,
 
\begin_inset Formula $3\,1\,2\,5\,4$
\end_inset

,
 
\begin_inset Formula $3\,1\,2\,4\,5$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc4[13]
\end_layout

\end_inset

Given the fact that 
\begin_inset Formula $\log_{10}1000!=2567.60464...$
\end_inset

,
 determine exactly how many decimal digits are present in the number 
\begin_inset Formula $1000!$
\end_inset

.
 What is the 
\emph on
most significant
\emph default
 digit?
 What is the 
\emph on
least significant
\emph default
 digit?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Given a number 
\begin_inset Formula $x$
\end_inset

 with 
\begin_inset Formula $n+1$
\end_inset

 digits 
\begin_inset Formula $x_{n}x_{n-1}\cdots x_{1}x_{0}$
\end_inset

,
 we have 
\begin_inset Formula $x_{n}10^{n}\leq x<(x_{n}+1)10^{n}$
\end_inset

 and therefore 
\begin_inset Formula $n+\log_{10}x_{n}\leq\log x<n+\log_{10}(x_{n}+1)$
\end_inset

,
 with 
\begin_inset Formula $0\leq\log_{10}X_{n}<\log_{10}(x_{n}+1)\leq1$
\end_inset

.
 Thus,
 
\begin_inset Formula $1000!$
\end_inset

 has 2568 digits and the most significant digit is 4,
 since 
\begin_inset Formula $\log_{10}4=0.60205...$
\end_inset

 and 
\begin_inset Formula $\log_{10}5=0.69897...$
\end_inset

.
 Furthermore,
 since 
\begin_inset Formula $10\mid1000!$
\end_inset

,
 the least significant digit is 0.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc6[17]
\end_layout

\end_inset

Using Eq.
 (8),
 write 
\begin_inset Formula $20!$
\end_inset

 as a product of prime factors.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Numbers up to 20 have prime factors up to 20,
 so the prime factors are 2,
 3,
 5,
 7,
 11,
 13,
 17,
 and 19.
 For the multiplicities,
\begin_inset Formula 
\begin{align*}
\mu_{2} & =\sum_{k\geq1}\left\lfloor \frac{20}{2^{k}}\right\rfloor =10+5+2+1=18, & \mu_{11} & =\sum_{k\geq1}\left\lfloor \frac{20}{11^{k}}\right\rfloor =1,\\
\mu_{3} & =\sum_{k\geq1}\left\lfloor \frac{20}{3^{k}}\right\rfloor =6+2=8, & \mu_{13} & =\sum_{k\geq1}\left\lfloor \frac{20}{13^{k}}\right\rfloor =1,\\
\mu_{5} & =\sum_{k\geq1}\left\lfloor \frac{20}{5^{k}}\right\rfloor =4, & \mu_{17} & =\sum_{k\geq1}\left\lfloor \frac{20}{17^{k}}\right\rfloor =1,\\
\mu_{7} & =\sum_{k\geq1}\left\lfloor \frac{20}{7^{k}}\right\rfloor =2, & \mu_{19} & =\sum_{k\geq1}\left\lfloor \frac{20}{19^{k}}\right\rfloor =1,
\end{align*}

\end_inset

so 
\begin_inset Formula $20!=2^{18}3^{8}5^{4}7^{2}\cdot11\cdot13\cdot17\cdot19$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc7[M10]
\end_layout

\end_inset

Show that the 
\begin_inset Quotes eld
\end_inset

generalized termial
\begin_inset Quotes erd
\end_inset

 function in Eq.
 (10) satisfies the identity 
\begin_inset Formula $x?=x+(x-1)?$
\end_inset

 for all real numbers 
\begin_inset Formula $x$
\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 $x+(x-1)?=x+\frac{1}{2}(x-1)x=\frac{1}{2}2x+\frac{1}{2}(x-1)x=\frac{1}{2}(x+1)x=x?$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc9[M10]
\end_layout

\end_inset

Determine the values of 
\begin_inset Formula $\Gamma(\frac{1}{2})$
\end_inset

 and 
\begin_inset Formula $\Gamma(-\frac{1}{2})$
\end_inset

,
 given that 
\begin_inset Formula $(\frac{1}{2})!=\sqrt{\pi}/2$
\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 
\begin{align*}
(\tfrac{1}{2})!=\tfrac{1}{2}\Gamma(\tfrac{1}{2}) & \implies\Gamma(\tfrac{1}{2})=2(\tfrac{1}{2})!=\sqrt{\pi},\\
-\tfrac{1}{2}\Gamma(-\tfrac{1}{2})=\Gamma(\tfrac{1}{2}) & \implies\Gamma(-\tfrac{1}{2})=-2\Gamma(\tfrac{1}{2})=-2\sqrt{\pi}.
\end{align*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc10[HM20]
\end_layout

\end_inset

Does the identity 
\begin_inset Formula $\Gamma(x+1)=x\Gamma(x)$
\end_inset

 hold for all real numbers 
\begin_inset Formula $x$
\end_inset

?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

No,
 as it doesn't hold when 
\begin_inset Formula $\Gamma(x)$
\end_inset

 or 
\begin_inset Formula $\Gamma(x+1)$
\end_inset

 are not defined.
 However,
 when they are defined,
\begin_inset Formula 
\begin{align*}
x\Gamma(x) & =x\lim_{m}\frac{m^{x}m!}{\prod_{i=0}^{m}(x+i)}=\lim_{m}\frac{m^{x}m!}{\prod_{i=1}^{m}(x+i)}=\lim_{m}\frac{(m+1)^{x}(m+1)!}{\prod_{i=1}^{m+1}(x+i)}=\\
 & =\lim_{m}\frac{(m+1)^{x+1}m!}{\prod_{i=0}^{m}(x+1+i)}=\lim_{m}\left(\frac{m^{x+1}m!}{\prod_{i=0}^{m}((x+1)+i)}\left(\frac{m+1}{m}\right)^{x+1}\right)=\Gamma(x+1)\cdot1.
\end{align*}

\end_inset

Note that,
 if 
\begin_inset Formula $x\in\mathbb{Z}^{-}$
\end_inset

,
 then the terms from 
\begin_inset Formula $m=-x$
\end_inset

 onward are not defined,
 so this is not the scenario we are dealing with.
 For ant other value,
 this holds.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc11[M15]
\end_layout

\end_inset

Let the representation of 
\begin_inset Formula $n$
\end_inset

 in the binary system be 
\begin_inset Formula $n=2^{e_{1}}+2^{e_{2}}+\dots+2^{e_{r}}$
\end_inset

,
 where 
\begin_inset Formula $e_{1}>e_{2}>\dots>e_{r}\geq0$
\end_inset

.
 Show that 
\begin_inset Formula $n!$
\end_inset

 is divisible by 
\begin_inset Formula $2^{n-r}$
\end_inset

 but not by 
\begin_inset Formula $2^{n-r+1}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

This is exactly to say that,
 for 
\begin_inset Formula $p=2$
\end_inset

,
 
\begin_inset Formula $\mu=n-r$
\end_inset

.
 But 
\begin_inset Formula $r$
\end_inset

 is the sum of all bits of 
\begin_inset Formula $n$
\end_inset

 in base 2,
 so by Exercise 12,
 
\begin_inset Formula $\mu=\frac{1}{2-1}(n-r)=n-r$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc12[M22]
\end_layout

\end_inset

(A.
 Legendre,
 1808.) Generalizing the result of the previous exercise,
 let 
\begin_inset Formula $p$
\end_inset

 be a prime number,
 and let the representation of 
\begin_inset Formula $n$
\end_inset

 in the 
\begin_inset Formula $p$
\end_inset

-ary number system be 
\begin_inset Formula $n=a_{k}p^{k}+a_{k-1}p^{k-1}+\dots+a_{1}p+a_{0}$
\end_inset

.
 Express the number 
\begin_inset Formula $\mu$
\end_inset

 of Eq.
 (8) in a simple formula involving 
\begin_inset Formula $n$
\end_inset

,
 
\begin_inset Formula $p$
\end_inset

,
 and 
\begin_inset Formula $a$
\end_inset

's.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The question makes sense for 
\begin_inset Formula $n\in\mathbb{N}^{*}$
\end_inset

.
 Then,
 given that the previous exercise showed that,
 for 
\begin_inset Formula $p=2$
\end_inset

,
 
\begin_inset Formula $\mu=n-r$
\end_inset

,
 where 
\begin_inset Formula $r\coloneqq|\{k\in\mathbb{N}\mid a_{k}\neq0\}|=\sum_{k}a_{k}$
\end_inset

,
 a guess is that 
\begin_inset Formula $\mu=n-\sum_{k}a_{k}$
\end_inset

 for any other positive prime integer 
\begin_inset Formula $p$
\end_inset

 as well,
 that is,
 
\begin_inset Formula $n-\mu=\sum_{k}a_{k}$
\end_inset

.
 To prove this,
\begin_inset Formula 
\[
\mu=\sum_{j\geq1}\left\lfloor \frac{n}{p^{j}}\right\rfloor =\sum_{j=1}^{k}\sum_{i=j}^{k}a_{i}p^{i-j}=\sum_{1\leq j\leq i\leq k}a_{i}p^{i-j}=\sum_{i=1}^{k}a_{i}\left(\sum_{j=0}^{i-1}p^{j}\right)=\sum_{i=1}^{k}\frac{a_{i}(p^{i}-1)}{p-1},
\]

\end_inset

where the latter identity is because of the cyclotomic formula.
 Then,
\begin_inset Formula 
\begin{align*}
\sum_{i=1}^{k}\frac{a_{i}(p^{i}-1)}{p-1} & =\frac{1}{p-1}\left(\sum_{i=1}^{k}a_{i}p^{i}-\sum_{i=1}^{k}a_{i}\right)=\frac{1}{p-1}\left((n-a_{0})-\sum_{i\geq1}a_{i}\right)\\
 & =\frac{1}{p-1}\left(n-\sum_{i\geq0}a_{i}\right).
\end{align*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc22[HM20]
\end_layout

\end_inset

Try to put yourself in Euler's place,
 looking for a way to generalize 
\begin_inset Formula $n!$
\end_inset

 to noninteger values of 
\begin_inset Formula $n$
\end_inset

.
 Since 
\begin_inset Formula $(n+\frac{1}{2})!/n!$
\end_inset

 times 
\begin_inset Formula $((n+\frac{1}{2})+\frac{1}{2})!/(n+\frac{1}{2})!$
\end_inset

 equals 
\begin_inset Formula $(n+1)!/n!=n+1$
\end_inset

,
 it seems natural that 
\begin_inset Formula $(n+\frac{1}{2})!/n!$
\end_inset

 should be approximately 
\begin_inset Formula $\sqrt{n}$
\end_inset

.
 Similarly,
 
\begin_inset Formula $(n+\frac{1}{3})!/n!$
\end_inset

 should be 
\begin_inset Formula $\approx\sqrt[3]{n}$
\end_inset

.
 Invent a hypothesis about the ratio 
\begin_inset Formula $(n+x)!/n!$
\end_inset

 as 
\begin_inset Formula $n$
\end_inset

 approaches infinity.
 Is your hypothesis correct when 
\begin_inset Formula $x$
\end_inset

 is an integer?
 Does it tell anything about the appropriate value of 
\begin_inset Formula $x!$
\end_inset

 when 
\begin_inset Formula $x$
\end_inset

 is not an integer?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The previous examples show 
\begin_inset Formula $\frac{(n+\frac{1}{m})!}{n!}\approx\sqrt[m]{n}=n^{\frac{1}{m}}$
\end_inset

,
 which is to say that 
\begin_inset Formula $\frac{(n+x)!}{n!}\approx n^{x}$
\end_inset

 for 
\begin_inset Formula $x=\frac{1}{m}$
\end_inset

.
 As 
\begin_inset Formula $n$
\end_inset

 gets bigger,
 the approximation should probably be more accurate for the same value of 
\begin_inset Formula $x$
\end_inset

,
 so we could see that 
\begin_inset Formula $(n+x)!\approx n^{x}n!$
\end_inset

.
 For a non-negative integer 
\begin_inset Formula $x$
\end_inset

,
 
\begin_inset Formula $(n+x)!=(n+1)\cdots(n+x)\cdot n!$
\end_inset

,
 so as 
\begin_inset Formula $n$
\end_inset

 gets bigger the approximation is more and more precise,
 and in fact,
\begin_inset Formula 
\[
\lim_{n}\frac{n^{x}n!}{(n+x)!}=\lim_{n}\frac{n^{x}}{(n+1)\cdots(n+x)}=\lim_{n}\prod_{k=1}^{x}\frac{n}{n+k}=1.
\]

\end_inset

Multiplying by 
\begin_inset Formula $x!$
\end_inset

,
\begin_inset Formula 
\[
x!=\lim_{n}\frac{n^{x}x!n!}{(n+x)!}=\lim_{n}(n^{x}n!)\frac{x!}{(n+x)!}=\lim_{n}\frac{n^{x}n!}{(x+1)\cdots(x+n)},
\]

\end_inset

which is Euler's factorial formula.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc24[HM21]
\end_layout

\end_inset

Prove the handy inequalities
\begin_inset Formula 
\begin{align*}
\frac{n^{n}}{\text{e}^{n-1}} & \leq n!\leq\frac{n^{n+1}}{\text{e}^{n-1}}, & \text{integer }n & \geq1.
\end{align*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\begin_inset Note Greyedout
status open

\begin_layout Plain Layout
(Looking at the answers.) 
\end_layout

\end_inset

We have
\begin_inset Formula 
\begin{align*}
\frac{n^{n}}{n!} & =\prod_{k=1}^{n}\frac{n}{k}=\prod_{k=1}^{n-1}\frac{n}{k}=\prod_{k=1}^{n-1}\prod_{j=k}^{n-1}\frac{j+1}{j}=\prod_{1\leq k\leq j<n}\frac{j+1}{j}=\prod_{j=1}^{n-1}\left(\frac{j+1}{j}\right)^{j}=\\
 & =\prod_{j=1}^{n-1}\left(1+\frac{1}{j}\right)^{j}\leq\prod_{j=1}^{n-1}\left(\text{e}^{1/j}\right)^{j}=\text{e}^{n-1},
\end{align*}

\end_inset

where for the inequality we use that 
\begin_inset Formula $1+x\leq\text{e}^{x}$
\end_inset

 for all real 
\begin_inset Formula $x$
\end_inset

.
 Likewise,
\begin_inset Formula 
\begin{align*}
\frac{n^{n+1}}{n!} & =n\frac{n^{n}}{n!}=n\prod_{j=1}^{n-1}\left(\frac{j+1}{j}\right)^{j}=\prod_{j=1}^{n-1}\frac{j+1}{j}\prod_{j=1}^{n-1}\left(\frac{j+1}{j}\right)^{j}=\prod_{j=1}^{n-1}\left(\frac{j+1}{j}\right)^{j+1}=\\
 & =\prod_{j=2}^{n}\left(\frac{j}{j-1}\right)^{j}=\prod_{j=2}^{n}\left(1-\frac{1}{j}\right)^{-j}\geq\prod_{j=2}^{n}\left(\text{e}^{-1/j}\right)^{-j}=\text{e}^{n-1}.
\end{align*}

\end_inset


\end_layout

\end_body
\end_document