# induction help

• Jul 9th 2014, 07:22 PM
mathman11
induction 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
• Jul 9th 2014, 08:04 PM
romsek
Re: induction help
Quote:

Originally Posted by mathman11
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

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?
• Jul 9th 2014, 08:59 PM
mathman11
Re: induction help
Quote:

Originally Posted by romsek
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?

this is the correct statement
$4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$
i proved the base case for n=1 to be divisible by 21. and its true. If you can do the other part of the solution id appreciate it very much.
• Jul 9th 2014, 09:17 PM
JeffM
Re: induction help
Quote:

Originally Posted by mathman11
this is the correct statement
$4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$
i proved the base case for n=1 to be divisible by 21. and its true. If you can do the other part of the solution id appreciate it very much.

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.
• Jul 10th 2014, 07:39 AM
mathman11
Re: induction help
Quote:

Originally Posted by JeffM
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.

I missed out an n term. The statement supposed to read:
4^{(n + 1)} + 5^{(2n - 1)} is divisible by 21.

Base Case: n=1

4^{(1 + 1)} + 5^{(2(1) - 1)}
4^{(2)} + 5^{(2 - 1)}
4^{(2)} + 5^{(1)}
16 + 5 = 21 --> divisible by 21
• Jul 10th 2014, 09:28 AM
HallsofIvy
Re: induction help
Okay so the "inductive hypothesis" is that $\displaystyle 4^{k+1}+ 5^{2k-1}= 21m$ for some integer m.

Then $\displaystyle 4^{(k+1)+ 1}+ 5^{2(k+1)- 1}= 4(4^{k+1})+ 25(5^{2k-1})= 4(4^{k+1}+ 5^{2k-1})+ 21(5^{2k-1})$

Can you finish from here?
• Jul 10th 2014, 10:16 AM
mathman11
Re: induction help
Quote:

Originally Posted by HallsofIvy
Okay so the "inductive hypothesis" is that $\displaystyle 4^{k+1}+ 5^{2k-1}= 21m$ for some integer m.

Then $\displaystyle 4^{(k+1)+ 1}+ 5^{2(k+1)- 1}= 4(4^{k+1})+ 25(5^{2k-1})= 4(4^{k+1}+ 5^{2k-1})+ 21(5^{2k-1})$

Can you finish from here?

yes i think i can do it from here but can you explain to me how you got 21(5^2k -1)?
thanks
• Jul 10th 2014, 11:38 AM
JeffM
Re: induction help
Quote:

Originally Posted by mathman11
yes i think i can do it from here but can you explain to me how you got 21(5^2k -1)?
thanks

$4\left(4^{(k+1)}\right) + 25\left(5^{(2k - 1)}\right) = 4\left(4^{(k+1)}\right) + 4\left(5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right) =4\left(4^{(k+1)}\ + 5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right)$
• Jul 10th 2014, 11:46 AM
mathman11
Re: induction help
Quote:

Originally Posted by JeffM
$4\left(4^{(k+1)}\right) + 25\left(5^{(2k - 1)}\right) = 4\left(4^{(k+1)}\right) + 4\left(5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right) =4\left(4^{(k+1)}\ + 5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right)$

i still dont see how or where 21 came from.
• Jul 10th 2014, 11:49 AM
JeffM
Re: 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)}.$
• Jul 10th 2014, 12:07 PM
mathman11
Re: induction help
Quote:

Originally Posted by JeffM
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)}.$

ok but how does one prove for (k+1) from that.
• Jul 10th 2014, 12:52 PM
JeffM
Re: 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.$
• Jul 10th 2014, 06:04 PM
mathman11
Re: induction help
thanks for the help folks!