\(% Differentiation % https://tex.stackexchange.com/a/60546/ \newcommand{\Diff}{\mathop{}\!\mathrm{d}} \newcommand{\DiffFrac}[2]{\frac{\Diff #1}{\Diff #2}} \newcommand{\DiffOp}[1]{\frac{\Diff}{\Diff #1}} \newcommand{\Ndiff}[1]{\mathop{}\!\mathrm{d}^{#1}} \newcommand{\NdiffFrac}[3]{\frac{\Ndiff{#1} #2}{\Diff {#3}^{#1}}} \newcommand{\NdiffOp}[2]{\frac{\Ndiff{#1}}{\Diff {#2}^{#1}}} % Evaluation \newcommand{\LEvalAt}[2]{\left.#1\right\vert_{#2}} \newcommand{\SqEvalAt}[2]{\left[#1\right]_{#2}} % Epsilon & Phi \renewcommand{\epsilon}{\varepsilon} \renewcommand{\phi}{\varphi} % Sets \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\PP}{\mathbb{P}} \renewcommand{\emptyset}{\varnothing} % Probabililty \DeclareMathOperator{\Cov}{Cov} \DeclareMathOperator{\Corr}{Corr} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\Expt}{E} \DeclareMathOperator{\Prob}{P} % Distribution \DeclareMathOperator{\Binomial}{B} \DeclareMathOperator{\Poisson}{Po} \DeclareMathOperator{\Normal}{N} \DeclareMathOperator{\Exponential}{Exp} \DeclareMathOperator{\Geometric}{Geo} \DeclareMathOperator{\Uniform}{U} % Complex Numbers \DeclareMathOperator{\im}{Im} \DeclareMathOperator{\re}{Re} % Missing Trigonometric & Hyperbolic functions \DeclareMathOperator{\arccot}{arccot} \DeclareMathOperator{\arcsec}{arcsec} \DeclareMathOperator{\arccsc}{arccsc} \DeclareMathOperator{\sech}{sech} \DeclareMathOperator{\csch}{csch} \DeclareMathOperator{\arsinh}{arsinh} \DeclareMathOperator{\arcosh}{arcosh} \DeclareMathOperator{\artanh}{artanh} \DeclareMathOperator{\arcoth}{arcoth} \DeclareMathOperator{\arsech}{arsech} \DeclareMathOperator{\arcsch}{arcsch} % UK Notation \DeclareMathOperator{\cosec}{cosec} \DeclareMathOperator{\arccosec}{arccosec} \DeclareMathOperator{\cosech}{cosech} \DeclareMathOperator{\arcosech}{arcosech} % Paired Delimiters \DeclarePairedDelimiter{\ceil}{\lceil}{\rceil} \DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor} \DeclarePairedDelimiter{\abs}{\lvert}{\rvert} \DeclarePairedDelimiter{\ang}{\langle}{\rangle} % Vectors \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\bvect}[1]{\overrightarrow{#1}} % https://tex.stackexchange.com/a/28213 % \DeclareMathSymbol{\ii}{\mathalpha}{letters}{"10} % \DeclareMathSymbol{\jj}{\mathalpha}{letters}{"11} % \newcommand{\ihat}{\vect{\hat{\ii}}} % \newcommand{\jhat}{\vect{\hat{\jj}}} \newcommand{\ihat}{\textbf{\^{ı}}} \newcommand{\jhat}{\textbf{\^{ȷ}}} \newcommand{\khat}{\vect{\hat{k}}} % Other Functions \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\tr}{tr} % Other Math Symbols \DeclareMathOperator{\modulo}{mod} \newcommand{\divides}{\mid} \newcommand{\notdivides}{\nmid} \newcommand{\LHS}{\text{LHS}} \newcommand{\RHS}{\text{RHS}} \newcommand{\degree}{^{\circ}}\)
By the binomial theorem, we have \[ (1 + x)^{2m + 1} = \sum _{k = 0}^{2m + 1} \binom {2m + 1}{k} x^k. \]
If we let \(x = 1\), we have \[ 2^{2m + 1} = \sum _{k = 0}^{2m + 1} \binom {2m + 1}{k}. \]
Since \(\binom {2m + 1}{m}\) is a part of the sum, and all the other terms are positive, and there are other terms which are not \(\binom {2m + 1}{m}\) (e.g. \(\binom {2m + 1}{0} = 1\)), we therefore must have \[ \binom {2m + 1}{m} < 2^{2m + 1}. \]
Notice that \begin {align*} \binom {2m + 1}{m} & = \frac {(2m + 1)!}{m! (m + 1)!} \\ & = \frac {(2m + 1)(2m)(2m - 1) \cdots (m + 2)}{m!} \\ \end {align*}
A number theory argument follows. First, notice that all terms in the product \(P_{m + 1, 2m + 1}\) are within the numerator. Therefore, we must have \[ P_{m + 1, 2m + 1} \divides (2m + 1)(2m)(2m - 1) \cdots (m + 2). \]
Next, since all the terms in the product are primes, none of the terms will therefore have factors between \(1\) and \(m\). This means that \[ \gcd \left (P_{m + 1, 2m + 1}, m!\right ) = 1, \] i.e. \(P_{m + 1, 2m + 1}\) are co-prime.
Therefore, given that \(\binom {2m + 1}{m} = \frac {(2m + 1)(2m)(2m - 1) \cdots (m + 2)}{m!}\) is an integer, we must therefore have \[ P_{m + 1, 2m + 1} \divides \binom {2m + 1}{m}, \] and hence \[ P_{m + 1, 2m + 1} \leq \binom {2m + 1}{m} < 2^{2m}, \] as desired.
Notice that \begin {align*} P_{1, 2m + 1} & = P_{1, m + 1} \cdot P_{m + 1, 2m + 1} \\ & < 4^{m + 1} \cdot 2^{2m} \\ & = 4^{m + 1} \cdot 4^m \\ & = 4^{2m + 1}, \end {align*}
as desired.
First we look at the base case when \(n = 2\).
\(P_{1, 2} = 2\), \(4^2 = 16\), the original statement holds when \(n = 2\).
Now, we use strong induction. Suppose the statement holds up to some \(n = k \geq 2\).
If \(k = 2m\) is even, the induction step for \(2m \to 2m + 1\) is already shown in the previous part.
If \(k = 2m + 1\) is odd, we must have that \(k + 1\) is even. The only even prime is \(2\), but since \(k \geq 2\), \(k + 1 \neq 2\), and \(k + 1\) must be composite.
Therefore, \(P_{1, k + 1} = P_{1, k} < 4^{k} < 4^{k + 1}\). This completes the induction step.
Therefore, by strong induction, the statement \(P_{1, n} < 4^n\) holds for all \(n \geq 2\).