Vrftsjtryk

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.

Basis

Satisfies for $n=0$($44Big|132$)

Induction hypothesis

$exists min 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:)

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 simple direct proof (without induction)

$$
7times(44+5)^n+125times 5^n = ktimes 44 + 7times 5^n+125times 5^n = ktimes 44 + 44times 3times 5^nequiv 0 mod 44
$$

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^2equiv 5,$ using the Congruence Product Rule

$$begin{align}!!!!!bmod 44!:qquadquad
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!:, Aequiv a,, Bequiv b& ,Longrightarrow, ABequiv abqquadtext{Congruence Product Rule}\[3pt]
mmid color{#0a0}{A-a, B-b}&,Rightarrow, mmid AB-abqquadtext{Divisibility Product Rule}\[4pt]
{bf Proof}qquad (color{#0a0}{A-a})B+a(color{#0a0}B&color{#0a0}{-b}) = AB-abend{align}$$

Notice that $,m,$ divides the $rmcolor{#0a0}{green}$ terms by hypothesis.

You can find further discussion in many prior posts.

For $n=1$ is true.

Now, assume that is true for $kgeq1$ and let's see what is true for $k+1$. Our hypothesis is that $7^{2k+1}+5^{k+3}equiv0mod 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})equiv0mod 44$

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} - (49cdot 5) x_{n} = 54 x_{n+1} - 245 x_{n}$$

The results follows at once by induction, since $x_0=3cdot 44$ and $x_1=22cdot 44$.