0
$\begingroup$

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

  • 0
    Do you have to use induction - it can be done without.2012-11-02
  • 2
    Hint: $25 = 4 + 21$2012-11-02
  • 0
    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.2012-11-02
  • 1
    Great, it looks like everyone has pretty much done the OP's homework... :-/2012-11-02

6 Answers 6

5

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
    Thanks, your answer is easier to understand.2012-11-02
  • 0
    @Lucas: You’re welcome.2012-11-02
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$

  • 0
    Wow!! Nice!! thanks2012-11-02
  • 0
    @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.2012-11-02
  • 0
    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.2012-11-02
2

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

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$

  • 0
    Nice hint, but I suspect the OP's task is (was) to use induction on n.2012-11-02
  • 1
    @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.2012-11-02
  • 0
    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...2012-11-02
  • 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
0

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.

0

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