Induction: Prove that $4^{n+1}+5^{2 n - 1}$ is divisible by 21 for all $n \geq 1$.

Question

Induction: Prove that $4^{n+1}+5^{2 n - 1}$ is divisible by 21 for all $n \geq 1$.

Answer 1

HINT: Let $f(n)=4^{n+1}+5^{2n-1}$; you want to show that $f(n)$ is divisible by $21$ for all $n\ge 1$.

Presumably the base case, proving that $f(1)$ is divisible by $21$, causes no trouble. For your induction step you want to show that if $f(n)$ is divisible by $21$ for some $n\ge 1$, then $f(n+1)$ is divisible by $21$. Note that this will be true if and only if $f(n+1)-f(n)$ is divisible by $21$, so you ought to look at

$$\begin{align*} f(n+1)-f(n)&=\left(4^{n+2}+5^{2n+1}\right)-\left(4^{n+1}-5^{2n-1}\right)\\ &=\left(4^{n+2}-4^{n+1}\right)+\left(5^{2n+1}-5^{2n-1}\right)\\ &=4^{n+1}(4-1)+5^{2n-1}\left(25^2-1\right)\;.\tag{1} \end{align*}$$

Now see if you can rearrange $(1)$ to get something that is demonstrably a multiple of $21$.

Answer 2

Hint $ $ Times $5$ it's $\rm\, 25^n\!+20\cdot 4^n\equiv\, 4^n\!- 4^n\equiv\, 0 \!\pmod{21}\ $ (easily proved by induction if need be)

Remark $\ $ More generally $\rm\: a^3\equiv -1\:\Rightarrow\: (a^2)^{n+1}\!+a^{2n-1}\! =\, a^{2n-1}(a^3+1)\equiv 0$

Answer 3

Ostensibly, it can be easily established using congruence.

But as induction is required,it can be done as follows:

If $f(m)=4^{m+1}+5^{2m-1}$

$f(m+1)-f(m)$

$=4^{m+2}+5^{2m+1}-(4^{m+1}+5^{2m-1})$

$=4^{m+1}(4-1)+5^{2m-1}(5^2-1)$

$=3(4^{m+1}+5^{2m-1})+21\cdot 5^{2m-1}$

$f(m+1)=21\cdot 5^{2m-1}+4\cdot f(m)$

Now, $f(1)=4^2+5^1=21,f(2)=4^3+5^3=189$

So using induction,we can show that $21\mid f(n)$ if $n\ge 1$

---

Alternatively, let $f(m)=a^{2m-1}+b^{m+1}$

So, $f(m+1)-f(m)=a^{2m+1}+b^{m+2}-(a^{2m-1}+b^{m+1})$ $=(b-1)(a^{2m-1}+b^{m+1})+(a^2-b)a^{2m-1}$

$\implies f(m+1)=b(a^{2m-1}+b^{m+1})+(a^2-b)a^{2m-1}=f(m)+(a^2-b)a^{2m-1}$

No,w $f(1)=(a+b^2)$

So if $(a^2-b)\mid(a+b^2), (a^2-b)\mid f(n)$ if $n\ge 1$

Here $a=5,b=4\implies a^2-b=25-4=21$ and $a+b^2=5+4^2=21$

Answer 4

$5^{2n-1} = 5 \cdot 25^{n-1}$. Hence, $$5^{2n-1} \equiv 5 \cdot (21+4)^{n-1} \pmod{21} \equiv 5 \cdot 4^{n-1} \pmod{21}$$

Hence, $$4^{n+1} + 5^{2n-1} \equiv 4^{n+1} + 5 \cdot 4^{n-1} \pmod{21} \equiv 21 \cdot 4^{n-1} \pmod{21} \equiv 0 \pmod{21}$$

For a proof by induction, note that if $f(n) = 4^{n+1} + 5^{2n-1}$, then $$f(n+1) - 4f(n) = 4^{n+2} + 5^{2n+1} - 4^{n+2} - 4 \cdot 5^{2n-1} = 21 \cdot 5^{2n-1}$$

Hence, $$f(n+1) = 4f(n) + 21 \cdot 5^{2n-1}$$

Answer 5

Another way of doing this is to reverse engineer a recurrence relation of the form $f(n+1)=pf(n)+qf(n-1)$ - not so different from what Marvis has done, but illustrating some different techniques and possibilities.

Such a recurrence is linear, so given solutions $f(n)$ and $g(n)$, $af(n)+bg(n)$ is also a solution, and that gives enough scope to fit two initial conditions (eg the values of f(0) and f(1)).

This kind of recurrence has solutions of the form $f(n)=\alpha^n$, which can be used as a basis for the solution space, and substituting in to the recurrence we find that $\alpha^2-p\alpha-q = 0$. Since the solution is determined by $f(0)$ and $f(1)$ it is easy to prove that the two solutions to the quadratic form a basis. The only complication is if the quadratic has equal roots, which doesn't apply in this case.

We are given a function which combines multiples of $4^n$ and $25^n$ so we want the solutions of the quadratic to be 4 and 25. Hence $p=29, q=-100$.

More importantly, provided $p$ and $q$ and $f(n)$ are integers, any integer which is a divisor of $f(n-1)$ and $f(n)$ will also be a divisor of $f(n+1)$.

The recurrence can therefore be used to give a simple inductive step. NB this method might be disallowed in some contexts as insufficiently elementary.

Answer 6

Here is a simple solution.
Step 1: Prove for n=1
Step 2: Assuming the result is true when n=k where k is an integer

$$4^{n+1}+5^{2n−1}=21p$$

Step 3: We must prove that this also true when n=(k+1)

$$4^{n+1+1}+5^{2(n+1)−1}$$ $$=4^{n+1+1}+5^{2n+2−1}$$ $$=4.4^{n+1}+5^2.5^{2n−1}$$ $$=4.4^{n+1}+25.5^{2n−1}$$ $$=4.4^{n+1}+(21+4).5^{2n−1}$$ $$=4.4^{n+1}+21.5^{2n−1}+4.5^{2n−1}$$ $$=4(4^{n+1}+5^{2n−1})+21.5^{2n−1}$$ By Inductive Hypothesis in Step 1 $$=4(21P)+21.5^{2n−1}$$ Finally
$$=21(P+5^{2n−1})$$ Let $$P+5^{2n−1}=m$$ Therefore $$=21m$$ Proved