Changed layout for more manageable volumes

1 files changed, 1097 insertions, 0 deletions

diff --git a/vol1/1.2.5.lyx b/vol1/1.2.5.lyx
new file mode 100644
index 0000000..d379269
--- /dev/null
+++ b/vol1/1.2.5.lyx
@@ -0,0 +1,1097 @@
+#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