Proof by mathematical induction that, for all non-negative integers $n$, $7^{2n+1} + 5^{n+3}$ is divisible by $44$.

Question

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.

Answer 1

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:)

Answer 2

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.

Answer 3

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$

Answer 4

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

Answer 5

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

Answer 6

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.