Mathematical induction involving inequalities and congruences

Question

I have the following two problems:

"Prove each of the following statements by induction for all positive integers $n$:"

1. $2\cdot7^n \equiv 2^n\cdot(2+5n) \bmod 25 \quad$ <-- I have been going at this question for a couple of hours and can't seem to come up with an answer.
2. $\frac{(2n)!}{(n!)^2} \leq 4^n \quad$ <-- This one I have an answer to, but I am curious if it's valid!

I'll attach a picture to show my work, but I would really like some help with question 1; I'm having a lot of trouble with that one.

Answer 1

$\underline{\text{Problem 1:}}$ For each positive integer $n$, let $M(n)$ be the statement that $$ 2\cdot 7^n \equiv 2^n\cdot(2+5n)\pmod{25}. $$

Base step: $M(1)$ says that $14\equiv 14 \pmod{25}$, which is true.

Inductive step: Fix $k\geq 1$ and assume that $$ M(k):\; 2\cdot 7^k \equiv 2^k\cdot(2+5k)\pmod{25} $$ holds. It remains to show that $$ M(k+1):\; 2\cdot 7^{k+1} \equiv 2^{k+1}\cdot(2+5(k+1))\pmod{25} $$ follows. One can show this using just modular arithmetic; however, being a bit more pedantic, a few more steps may be added for clarity. Since $M(k)$ holds, we have the following: $$ 2\cdot 7^k \equiv 2^k\cdot(2+5k)\pmod{25} \Longleftrightarrow 2\cdot 7^k=2^k\cdot(2+5k) + 25\ell, $$ where $\ell\in\mathbb{Z}$. Thus, we have the following: \begin{align} 2\cdot 7^{k+1} &= (2\cdot 7^k)\cdot 7\\ &= (2^k\cdot(2+5k)+25\ell)\cdot 7\\ &= 7\cdot 2^k(2+5k)+7\cdot25\ell\\ &= 7\cdot 2^{k+1}+35k\cdot2^k+7\cdot 25\ell\\ &= 7\cdot 2^{k+1}+(25+2\cdot 5)k\cdot2^k+7\cdot 25\ell\\ &= 7\cdot 2^{k+1}+25k\cdot 2^k+5k\cdot2^{k+1}+7\cdot 25\ell\\ &= 2^{k+1}\cdot(7+5k)+25(7\ell+k\cdot2^k)\\ &\equiv 2^{k+1}\cdot(7+5k) \pmod{25}\\ &\equiv 2^{k+1}\cdot(2+5(k+1)) \pmod{25}, \end{align} as desired, completing the proof of $M(k+1)$, and hence the inductive step. By mathematical induction, for each $n\geq 1$, the statement $M(n)$ holds.

---

$\underline{\text{Problem 2:}}$ Start by noting that we can use a strict inequality (i.e., $<$) here rather than $\leq$. Also note that $$ \frac{(2n)!}{(n!)^2} < 4^n \Longleftrightarrow (2n)!<2^{2n}(n!)^2. $$ There is nothing special about the equivalent expression on the right-hand side, but I find it to be a more natural expression to deal with; thus, I am going to prove this second problem with that expression in mind.

With that in mind, for each positive integer $n$, let $M(n)$ be the statement that $$ (2n)!<2^{2n}(n!)^2. $$ Base step: $M(1)$ says that $2<4$, which is true.

Inductive step: Fix $k\geq 1$ and assume that $$ M(k):\;(2k)!<2^{2k}(k!)^2 $$ holds. It remains to show that $$ M(k+1):\; [2(k+1)]!<2^{2(k+1)}[(k+1)!]^2 $$ follows. Beginning with the left side of $M(k+1)$, \begin{align} [2(k+1)]! &= (2k+2)!\\ &= (2k+2)(2k+1)(2k!)\\ &< (2k+2)(2k+1)[2^{2k}(k!)^2]\tag{ind. hyp.}\\ &< (2k+2)^2[2^{2k}(k!)^2]\tag{$2k+1 < 2k+2$}\\ &= [2(k+1)]^2\cdot[2^{2k}(k!)^2]\\ &= 2^2\cdot (k+1)^2\cdot 2^{2k}\cdot (k!)^2\\ &= 2^{2(k+1)}[(k+1)!]^2, \end{align} which is the right side of $M(k+1)$. By mathematical induction, for each $n\geq 1$, the statement $M(n)$ holds.

Answer 2

$% Predefined Typography \newcommand{\paren} [1]{\left({#1}\right)} \newcommand{\bparen}[1]{\bigg({#1}\bigg)} \newcommand{\brace} [1]{\left\{{#1}\right\}} \newcommand{\bbrace}[1]{\bigg\{{#1}\bigg\}} \newcommand{\floor} [1]{\left\lfloor{#1}\right\rfloor} \newcommand{\bfloor}[1]{\bigg\lfloor{#1}\bigg\rfloor} \newcommand{\mag} [1]{\left\lVert{#1}\right\rVert} \newcommand{\bmag} [1]{\bigg\Vert{#1}\bigg\Vert} \newcommand{\abs} [1]{\left\vert{#1}\right\vert} \newcommand{\babs} [1]{\bigg\vert{#1}\bigg\vert} % \newcommand{\labelt}[2]{\underbrace{#1}_{\text{#2}}} \newcommand{\label} [2]{\underbrace{#1}_{#2}} % \newcommand{\setcomp}[2]{\left\{{#1}~~\middle \vert~~ {#2}\right\}} \newcommand{\bsetcomp}[2]{\bigg\{{#1}~~\bigg \vert~~ {#2}\bigg\}} % \newcommand{\iint}[2]{\int {#1}~{\rm d}{#2}} \newcommand{\dint}[4]{\int_{#3}^{#4}{#1}~{\rm d}{#2}} \newcommand{\pred}[2]{\frac{\rm d}{{\rm d}{#2}}#1} \newcommand{\ind} [2]{\frac{{\rm d} {#1}}{{\rm d}{#2}}} \newcommand{\predp}[2]{\frac{\partial}{\partial {#2}}#1} \newcommand{\indp} [2]{\frac{{\partial} {#1}}{\partial {#2}}} \newcommand{\predn}[3]{\frac{\rm d}^{#3}{{\rm d}{#2}^{#3}}#1} \newcommand{\indn} [3]{\frac{{\rm d}^{#3} {#1}}{{\rm d}{#2}^{#3}}} % \newcommand{\ii}{{\rm i}} \newcommand{\ee}{{\rm e}} \newcommand{\exp}[1] { {\rm e}^{\large{#1}} } % \newcommand{\red} [1]{\color{red}{#1}} \newcommand{\blue} [1]{\color{blue}{#1}} \newcommand{\green}[1]{\color{green}{#1}} $

For part (2) , the relation you want is:

$$x \le 1 ~\land~ a < b \quad \Longrightarrow \quad xa< b$$

For you, $x = \frac{2k+1}{2(k+1)}$, $a = \frac{(2k)!}{k!^2}$, $b = 4^k$.

For part (1), $\quad 13 \cdot 2 \equiv 26 \equiv 1 \pmod {25}\quad $, so apply the inductive hypothesis then multiply by $13^{k+1}$ to cancel the exponents:

$$\begin{align} 2 \cdot 7^{k+1} &\equiv 2^{k+1}(2+5(k+1)) &\pmod{ 25 } \\ 7 \cdot 2 \cdot 7^{k} &\equiv 2^{k+1}(7+5k) &\pmod{ 25 } \\ 7 \cdot 2^k(2+5k) &\equiv 2^{k+1}(7+5k) &\pmod{ 25 } \\ 13\cdot 13^k \cdot 7 \cdot 2^k(2+5k) &\equiv 13^{k+1}2^{k+1}(7+5k) &\pmod{ 25 } \\ 13 \cdot 7 (2+5k) &\equiv (7+5k) &\pmod{ 25 } \\ \end{align}$$

And from here it is straightforward.

Answer 3

Hint $(1)$ follows by applying the Binomial Theorem to $\,2 \cdot 7^n = 2(2 + 5)^n $ and noting that only the first two terms of the binomial expansion survive mod $25.$ If you need an explicit inductive proof then you can present the above proof as here. Or, more directly, here is the inductive step

$$ 2\cdot 7^n\cdot 7 \,\overset{\rm induct}= 2^n (2\!+\!5n)\cdot 7\,\equiv\, 2^n(14+\!\!\!\overbrace{\color{#c00}{10}\,n}^{\large \color{#c00}{35\,\equiv\, 10}}\!\!\!)\, =\, 2^{n+1}\overbrace{(7+5n)}^{\large 2+5(n+1)}\pmod{\color{#c00}{25}}\qquad$$