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$.
-
1Great, it looks like everyone has pretty much done the OP's homework... :-/ – 2012-11-02
6 Answers
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$.
-
0@Lucas: You’re welcome. – 2012-11-02
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$
-
0Alternatively, $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. – 2012-11-02
$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$
-
0@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)$. $\ $ – 2012-11-02
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.
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