Proof by mathematical induction that, for all non-negative integers $n$, $7^{2n+1} + 5^{n+3}$ is divisible by $44$. I have been trying to solve this problem, but I have not been able to figure it out using any simple techniques. Would someone give me the ropes please?
Prove for $n=1$
$7^3 + 5^4 = 968 = 44(22)$ 
Assume $F(k)$ is true and try $F(k+1)+-F(k)$
$F(k) = 7^{2k+1} + 5^{k+3}$
$F(k+1) = 7^{2k+3} + 5^{k+4}$
$49*7^{2k+1} + 5*5^{k+3} +- [7^{2k+1} + 5^{k+3}]$
Neither addition nor subtraction gives us a chance to take $44$ in front of the bracket, the best approach it has come to my mind is to subtract $F(k)$ which gives us:
$4[12*7^{2k+1} + 5^{5+3}]$
And now we need to prove that the inside is divisible by $11$. I have not been able to do so.
 A: The arithmetical essence is clarified if we use modular arithmetic as below, which reveals that the inductive step boils down to scaling $\,P(n)\,$ by $\,7^2\equiv 5\,$ using the Congruence Product Rule 
$$\begin{align}\!\!\!\!\!\bmod 44\!:\qquad\quad\
 7^{\large 2} &\equiv\, 5\\[.2em]
\times \ \ \ 7^{\large 2n+1}&\equiv\, -5^{\large n+3}\quad {\rm i.e.}\ \ P(n)_{\phantom{I_{I_I}}}\\[.2em]
\hline
\Rightarrow\ \ 7^{\large 2n+3}&\equiv -5^{\large n+4}\ \quad {\rm i.e.}\ \ P(n+1)\phantom{I^{I^{I^I}}}
\end{align}\qquad\!\!  $$
Remark $ $ Even if you don't know congruences you can still take advantage of these arithmetical simplifications by using a version of the Product Rule in divisibility form as below
$$\begin{align} \bmod m\!:\, A\equiv a,\, B\equiv b&\ \ \,\Longrightarrow\,\ \ AB\equiv ab\qquad\text{Congruence Product Rule}\\[3pt]
m\mid \color{#0a0}{A-a,\ B-b}&\,\Rightarrow\, m\mid AB-ab\qquad\text{Divisibility Product Rule}\\[4pt] 
{\bf Proof}\qquad (\color{#0a0}{A-a})B+a(\color{#0a0}B&\color{#0a0}{-b})\ =\ AB-ab\end{align}$$
Notice that $\,m\,$ divides the $\rm\color{#0a0}{green}$ terms by hypothesis.
You can find further discussion in many prior posts.
A: Base case : n=1✓
Hypothesis : $44$ divides $7^{2n+1} +5^{n+3}$.
Step $n+1$:
$7^{2(n+1)+1}+ 5^{(n+1)+1}=$
$7^{2n+1}7^2+ 5^{n+1}5=$
$7^{2n+1}(44+5)+5^{n+1}5=$
$(44)7^{2n+1} +5(7^{2n+1}+5^{n+1}).$
First term divisible by $44$, so is the second term by hypothesis.
A: Basis
Satisfies for $n=0$($44\Big|132$)
Induction hypothesis
$\exists m\in \mathbb N $ such that $7^{2k+1}+5^{k+3}=44m$
Inductive step
$$7^{2k+3}+5^{k+4} =49(7^{2k+1})+5(5^{k+3})$$
$$=49(44m-5^{k+3})+5(5^{k+3})$$
$$=44(49m-5^{k+3})$$
which is clearly divisible by $44$.
Hope it helps:)
A: For $n=1$ is true.
Now, assume that is true for $k\geq1$ and let's see what is true for $k+1$. Our hypothesis is that $7^{2k+1}+5^{k+3}\equiv0\mod 44$
$7^{2k+3}+5^{k+4}=49.7^{2k+1}+5.5^{k+3}\equiv 5.7^{2k+1}+5.5^{k+3}=5(7^{2k+1}+5^{k+3})\equiv0\mod 44$
A: A simple direct proof (without induction)
$$
7\times(44+5)^n+125\times 5^n = k\times 44 + 7\times 5^n+125\times 5^n = k\times 44 + 44\times 3\times 5^n\equiv 0 \mod 44
$$
A: Here is another take.
Write $x_n=7^{2n+1} + 5^{n+3}= 7 \cdot 49^n + 125 \cdot 5^n$.
Thus, $x_n$ is a linear combination of two geometric sequences and so satisfies a second-order recurrence:
$$x_{n+2} = (49+5) x_{n+1} - (49\cdot 5) x_{n} = 54 x_{n+1} - 245 x_{n}$$
The results follows at once by induction, since $x_0=3\cdot 44$ and $x_1=22\cdot 44$.
