Mathematical induction involving inequalities and congruences I have the following two problems:
"Prove each of the following statements by induction for all positive integers $n$:"


*

*$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.

*$\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.


 A: $\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.
A: $% 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.
A: 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$$
