Can someone post a solution to this question along with an explanation please? I got a test tomorrow and im having trouble understanding this.

Prove by induction:

4^n+1 + 5^n-1 is divisible by 21 ∀ n ∈ N,n>=1

Printable View

- July 9th 2014, 08:22 PMmathman11induction help
Can someone post a solution to this question along with an explanation please? I got a test tomorrow and im having trouble understanding this.

Prove by induction:

4^n+1 + 5^n-1 is divisible by 21 ∀ n ∈ N,n>=1 - July 9th 2014, 09:04 PMromsekRe: induction help
I'm guessing you mean

$4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$

But maybe not since

$n=1 \Rightarrow 4^2+1=17 \neq 21k$

$n=2 \Rightarrow 4^3+5 = 69 \neq 21k$

I show that in general your statement is incorrect.

Could you repost the correct statement you're trying to prove? - July 9th 2014, 09:59 PMmathman11Re: induction help
- July 9th 2014, 10:17 PMJeffMRe: induction help
Romsek has given

**TWO**examples showing that what you are trying to prove is false.

In particular, he has shown that your base case is false. Let's go over it again.

$n = 1 \implies 4^{(n + 1)} = 4^2 = 16\ and \ 5^{(n - 1)} = 5^0 = 1 \implies$

$4^{(n + 1)} + 5^{(n - 1)} = 16 + 1 = 17,$ which is clearly not divisible by 21.

Perhaps if you showed how you "proved" it true if n = 1, we could figure out what the problem actually is. - July 10th 2014, 08:39 AMmathman11Re: induction help
- July 10th 2014, 10:28 AMHallsofIvyRe: induction help
Okay so the "inductive hypothesis" is that for some integer m.

Then

Can you finish from here? - July 10th 2014, 11:16 AMmathman11Re: induction help
- July 10th 2014, 12:38 PMJeffMRe: induction help
- July 10th 2014, 12:46 PMmathman11Re: induction help
- July 10th 2014, 12:49 PMJeffMRe: induction help
He separated $25 * 5^{(2k - 1)}\ into\ 4 * 5^{(2k - 1)} + 21 * 5^{(2k - 1)}.$

The general idea is this $25a = 4a + 21a.$ In this case the $a = 5^{(2k - 1)}.$ - July 10th 2014, 01:07 PMmathman11Re: induction help
- July 10th 2014, 01:52 PMJeffMRe: induction help
I am going to give you this one so you see the logic of a proof by induction. As for finding a proof of any kind, there is no rule book: it takes creativity.

$H\ is\ the\ set\ such\ that\ n \in H \implies n \in\ \mathbb N,\ n \ge 1,\ and\ \dfrac{4^{n + 1} + 5^{2n - 1}}{21} \in \mathbb N.$ But H may be the empty set.

$1 \in \mathbb N,\ and\ 1 \ge 1,\ and\ \dfrac{4^{1 + 1} + 5^{2 * 1 - 1}}{21} = \dfrac{4^2 + 5^1}{21} = \dfrac{16 + 5}{21} = \dfrac{21}{21} = 1 \in \mathbb N.$

This is just arithmetic and you got it but it implies something very important, namely:

$\therefore 1 \in H.$ You have proved that H is not empty.

Now we choose an arbitrary member of H and call it k. This is called an inductive hypothesis for reasons that elude me because we have proved that at least one such number exists.

$Let\ k\ be\ an\ arbitrary\ member\ of\ H \implies k \in\ \mathbb N,\ k \ge 1,\ and\ \dfrac{4^{k + 1} + 5^{2k - 1}}{21} \in \mathbb N.$

$Let\ m = \dfrac{4^{k + 1} + 5^{2k - 1}}{21} \implies m \in \mathbb N\ and\ 4^{k + 1} + 5^{2k - 1} = 21m.$ With me to here?

Now we want to prove that k + 1 is also a member of H. It's trivially obvious that k + 1 is a natural number greater than or equal to 1 because those things are true of k. So the trick is to prove that the third condition for membership in H is met by k + 1. Very generally, you do that by finding out a way to reduce that third condition for k + 1 into something related to that same condition for k. This may require virtually no creativity or a lot of it. It is what makes proofs an art. Halls of Ivy came up with this bit of creativity starting from setting up the relevant expression for k + 1.

$\dfrac{4^{(k + 1) + 1} + 5^{2(k + 1) - 1}}{21} = \dfrac{4^{k + 2} + 5^{2k + 1}}{21} = \dfrac{4\left(4^{k + 1}\right) + 25\left(5^{2k - 1}\right)}{21} = \dfrac{4\left(4^{k + 1}\right) + 4\left(5^{2k - 1}\right) + 21\left(5^{2k - 1}\right)}{21} = $

$\dfrac{4\left(4^{k + 1} + 5^{2k - 1}\right) + 21\left(5^{2k - 1}\right)}{21} = \dfrac{4\left(21m\right) + 21\left(5^{2k - 1}\right)}{21} = \dfrac{21\left(4m + 5^{2k - 1}\right)}{21} = 4m + 5^{2k - 1}.$

$But\ 4m\ and\ 5^{2k - 1} \in \mathbb N \implies 4m + 5^{2k - 1} \in \mathbb N \implies \dfrac{4^{(k + 1) + 1} + 5^{2(k + 1) - 1}}{21} \in \mathbb N.$

So the third condition is met for k + 1.

$\therefore k + 1 \in H.$

$THUS, H = \mathbb N.$ - July 10th 2014, 07:04 PMmathman11Re: induction help
thanks for the help folks!