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

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

-
What have you tried? –  JavaMan Nov 2 '12 at 18:39
Do you have to use induction - it can be done without. –  Mark Bennet Nov 2 '12 at 18:41
Hint: $25 = 4 + 21$ –  Dilip Sarwate Nov 2 '12 at 18:44
What is your base case? Is the assertion true for $n=1$? Then proceed with your inductive hypothesis (assume true for n)...then show it is true for n+1. –  amWhy Nov 2 '12 at 18:48
Great, it looks like everyone has pretty much done the OP's homework... :-/ –  amWhy Nov 2 '12 at 18:50

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

-
+1 for not providing an entirely complete answer. –  amWhy Nov 2 '12 at 18:52
Thanks, your answer is easier to understand. –  Lucas Nov 2 '12 at 19:12
@Lucas: You’re welcome. –  Brian M. Scott Nov 2 '12 at 19:14

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$

-
Wow!! Nice!! thanks –  Lucas Nov 2 '12 at 19:00
@Lucas, welcome anytime. may have a look into the modified answer. Unless otherwise specified, I think, induction should be the last resort in such problems. –  lab bhattacharjee Nov 2 '12 at 19:14
Alternatively, $$f(m+1)=4\cdot 4^{m+1}+25\cdot 5^{2m-1} = 4\cdot 4^{m+1}+(4+21)\cdot 5^{2m-1}=4f(m)+21\cdot 5^{2m-1}$$ is a multiple of $21$ since $f(m)$ is a multiple of $21$ by the induction hypothesis. –  Dilip Sarwate Nov 2 '12 at 20:32

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

-

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$

-
Nice hint, but I suspect the OP's task is (was) to use induction on n. –  amWhy Nov 2 '12 at 18:53
@amWhy One can use induction to prove $\rm\:-4^n + 4^n\! \equiv 0,\:$ though it's rather trivial. But that's the point, i.e. to transform the problem to a form where the induction is obvious. This is the key to many induction problems. –  Bill Dubuque Nov 2 '12 at 18:57
Bill, I think you know exactly what I was getting at; pedagogically, if the point of an exercise is to develop students' facility with proof by induction, the object is not to teach ways to "avoid" proof by induction. I've said enough about this problem... –  amWhy Nov 2 '12 at 20:49
@amWhy Induction is not avoided above; rather is is simplified to the trivial induction that $\rm\:f(n) = 4^n\! - 4^n \equiv 0.\:$ Hint: the induction step arises from $\rm\:f(n\!+\!1) = 4\,f(n)$. $\$ –  Bill Dubuque Nov 2 '12 at 21:26

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.

-